A fast algorithm for the partial digest problem
A fast algorithm for the partial digest problem
复制标题
一种解决部分摘要问题的快速算法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Ganjtabesh
中科院分区：
文献类型：
--
作者：
R. Nadimi;H. Fathabadi;M. Ganjtabesh
计算生物学中的一个基本问题是限制性内切位点的映射。当一种特定的限制性内切酶被添加到DNA中时，DNA链在特定的限制性内切位点被切断。限制性内切酶位点图谱的目标是确定给定酶的每个位点的位置。利用凝胶电泳，可以找到每对酶切位点之间的距离。在部分消化问题（PDP）中，我们给出了仅使用一种酶的消化实验产生的这些距离，并要求我们计算所有限制性内切位点的位置。为了解决这一问题，人们提出了伪多项式时间算法和回溯算法。本文针对这一问题提出了一个新的模型。在此模型的基础上，提出了一种求解部分摘要问题的分支定界算法。与Skiena提出的回溯算法相比，新算法的搜索树非常小，因此效率很高。通过在不同类型的实例上执行该算法，验证了该算法的有效性和优越性。存在一些PDP实例，其中Skiena的算法需要指数级的运行时间来解决它们。对于这类问题实例，也证明了算法的有效性。
A fundamental problem in computational biology is the restriction site mapping. When a particular restriction enzyme is added to a DNA, the DNA strand is cut at particular restriction sites. The goal of the restriction site mapping is to determine the location of every site for a given enzyme. Using gel electrophoresis, one can find the distance between each pair of restriction sites. In the partial digest problem (PDP), we are given these distances arising from digestion experiments by using only one enzyme, and we are asked to compute the locations of all restriction sites. Several approaches, including pseudo-polynomial time algorithm and backtracking algorithm have been proposed to tackle this problem. In this paper we propose a new model for this problem. Based on this model, we present a new branch and bound algorithm for partial digest problem. In comparison with the backtracking algorithm presented by Skiena, the new algorithm has very small search tree and so it is very efficient. The efficiency and advantages of this algorithm are also demonstrated by executing it on different types of instances. There exist some instances of PDP, where the Skiena’s algorithm requires exponential running time to solve them. The efficiency of our algorithm is also presented for these kind of problem instances.