Seeding strategies and recombination operators for solving the DNA fragment assembly problem

The fragment assembly problem consists in building the DNA sequence from several hundreds (or even, thousands) of fragments obtained by biologists in the laboratory. This is an important task in any genome project since the rest of the phases depend on the accuracy of the results of this stage. Therefore, accurate and efficient methods for handling this problem are needed. Genetic Algorithms (GAs) have been proposed to solve this problem in the past but a detailed analysis of their components is needed if we aim to create a GA capable of working in industrial applications. In this paper, we take a first step in this direction, and focus on two components of the GA: the initialization of the population and the recombination operator. We propose several alternatives for each one and analyze the behavior of the different variants. Results indicate that using a heuristically generated initial population and the Edge Recombination (ER) operator is the best approach for constructing accurate and efficient GAs to solve this problem. (C) 2008 Elsevier B.V. All rights reserved.