2-3 September 2021
Publication Links
IJACSA
Special Issues
Article Details
Copyright Statement: This is an open access article licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, even commercially as long as the original work is properly cited.
An Investigative Study of Genetic Algorithms to Solve the DNA Assembly Optimization Problem
Digital Object Identifier (DOI) : 10.14569/IJACSA.2020.0111019
Article Published in International Journal of Advanced Computer Science and Applications(IJACSA), Volume 11 Issue 10, 2020.
Abstract: 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.
Keywords: Genetic Algorithms; Traveling Salesman Problem; Quadratic Assignment Problem; DNA fragments assembly problem
Hachemi Bennaceur, Meznah Almutairy and Nora Alqhtani, “An Investigative Study of Genetic Algorithms to Solve the DNA Assembly Optimization Problem” International Journal of Advanced Computer Science and Applications(IJACSA), 11(10), 2020. http://dx.doi.org/10.14569/IJACSA.2020.0111019
@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},
doi = {10.14569/IJACSA.2020.0111019},
url = {http://dx.doi.org/10.14569/IJACSA.2020.0111019},
year = {2020},
publisher = {The Science and Information Organization},
volume = {11},
number = {10},
author = {Hachemi Bennaceur and Meznah Almutairy and Nora Alqhtani}
}
