期刊名称：International Journal of Advanced Computer Science and Applications(IJACSA)
印刷版ISSN：2158-107X
电子版ISSN：2156-5570
出版年度：2020
卷号：11
期号：10
DOI：10.14569/IJACSA.2020.0111019
出版社：Science and Information Society (SAI)
摘要：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.
关键词：Genetic Algorithms; Traveling Salesman Problem; Quadratic Assignment Problem; DNA fragments assembly problem
