Title: Genetic algorithm solution for partial digest problem

Authors: Hayedeh Ahrabian; Mohammad Ganjtabesh; Abbas Nowzari-Dalini; Zahra Razaghi-Moghadam-Kashani

Addresses: School of Mathematics, Statistics and Computer Science, University of Tehran, Tehran, Iran ' School of Mathematics, Statistics and Computer Science, University of Tehran, Tehran, Iran; Laboratoire d'Informatics (LIX), Ecole Polytechnique, Palaiseau CEDEX, 91128, France ' School of Mathematics, Statistics and Computer Science, University of Tehran, Tehran, Iran ' Institute of Biochemistry and Biophysics (IBB), University of Tehran, Tehran, Iran

Abstract: 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.

Keywords: bioinformatics; PDP; partial digest problem; GAs; genetic algorithms; DNA sequencing.

DOI: 10.1504/IJBRA.2013.056622

International Journal of Bioinformatics Research and Applications, 2013 Vol.9 No.6, pp.584 - 594

Accepted: 04 Jan 2012
Published online: 18 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article