International Journal of Computational Intelligence Research (IJCIR)

Volume 1, Number 2 (2005)


Metaheuristics for the DNA Fragment Assembly Problem


Gabriel Luque, Enrique Alba
Dpto. de Lenguajes y Ciencias de la Computación, 

E.T.S.I. Informática, 

Campus Teatinos 29071, Málaga, SPAIN


As more research centers embark on sequencing new genomes, the problem of DNA fragment assembly for shotgun sequencing is growing in importance and complexity. Accurate and fast assembly is a crucial part of any sequencing project and since the DNA fragment assembly problem is NPhard, exact solutions are very difficult to obtain. Various heuristics were designed for solving the fragment assembly problem. But, in general, they are unable to sequence very large DNA molecules. In this work, we present several methods, a canonical genetic algorithm, a CHC method, a scatter search algorithm, and a simulated annealing, to solve accurately problem instances that are 77K base pairs long.

Key words
DNA Fragment Assembly, Genetic Algorithm, Scatter Search, Simulated Annealing, CHC.