SAX: a new and efficient assembler for solving DNA Fragment Assembly Problem

In the past, the Fragment Assembly Problem has been solved efficiently by many metaheuristics. In this work, we propose a new one, called SAX, which consists in combining two metaheuristics: a trajectory method as Simulated Annealing and a population-based method as Genetic Algorithm. We also analyze the relative advantages of this hybridization against other assemblers from literature. From this analysis, we conclude that SAX improves the quality results found by other metaheuristic and non-metaheuristic assemblers for solving 100% of the largest instances for this problem.Sociedad Argentina de Informática e Investigación Operativ