Ahrabian Hayedeh, Ganjtabesh Mohammad, Nowzari-Dalini Abbas, Razaghi-Moghadam-Kashani Zahra
School of Mathematics, Statistics and Computer Science, University of Tehran, Tehran, Iran.
Int J Bioinform Res Appl. 2013;9(6):584-94. doi: 10.1504/IJBRA.2013.056622.
One of the fundamental problems in computational biology is the construction of physical maps of chromosomes from the hybridisation experiments between unique probes and clones of chromosome fragments. Before introducing the shotgun sequencing method, Partial Digest Problem (PDP) was an intractable problem used to construct the physical maps of DNA sequence in molecular biology. In this paper, we develop a novel Genetic Algorithm (GA) for solving the PDP. This algorithm is implemented and compared with well-known existing algorithms on different types of random and real instances data, and the obtained results show the efficiency of our algorithm. Also, our GA is adapted to handle the erroneous data and their efficiency is presented for the large instances of this problem.
计算生物学中的一个基本问题是根据独特探针与染色体片段克隆之间的杂交实验构建染色体的物理图谱。在引入鸟枪法测序方法之前，部分酶切问题（PDP）是分子生物学中用于构建DNA序列物理图谱的一个棘手问题。在本文中，我们开发了一种用于解决PDP的新型遗传算法（GA）。该算法在不同类型的随机和实际实例数据上实现，并与现有的知名算法进行比较，所得结果表明了我们算法的有效性。此外，我们的遗传算法适用于处理错误数据，并展示了其在该问题大型实例上的效率。
