An Investigative Study of Genetic Algorithms to Solve the DNA Assembly Optimization Problem

This paper aims to highlight the motivations for investigating genetic algorithms to solve the DNA Fragments Assembly problem (DNA_FA). DNA_FA is an optimization problem that attempts to reconstruct the original DNA sequence by finding the shortest DNA sequence from a given set of fragments. We showed that the DNA_FA optimization problem is a special case of the two well-known optimization problems: The Traveling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP). TSP and QAP are important problems in the field of combinatorial optimization and for which there exists an abundant literature. Genetic Algorithms (GA) applied to these problems have led to very satisfactory results in practice. In the perspective of designing efficient genetic algorithms to solve DNA_FA we showed the existence of a polynomial-time reduction of DNA-FA into TSP and QAP enabling us to point out some technical similarities in terms of solutions and search space complexity. We then conceptually designed a genetic algorithm platform for solving the DNA-FA problem inspired from the existing efficient genetic algorithms in the literature solving TSP and QAP problems. This platform offers several ingredients enabling us to create several variants of GA solvers for the DNA assembly optimization problems.

@article{Bennaceur2020,
  title     = {An Investigative Study of Genetic Algorithms to Solve the DNA Assembly Optimization Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {11},
  number    = {10},
  year      = {2020},
  publisher = {The Science and Information Organization},
  author    = {Hachemi Bennaceur and Meznah Almutairy and Nora Alqhtani},
  doi       = {10.14569/IJACSA.2020.0111019},
  url       = {https://doi.org/10.14569/IJACSA.2020.0111019}
}