DNA Fragment Assembly Using Multi-Objective Genetic Algorithms

Manisha Rathee and T. V. Vijay Kumar
Additional contact information
Manisha Rathee: School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi, India
T. V. Vijay Kumar: School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi, India

International Journal of Applied Evolutionary Computation (IJAEC), 2014, vol. 5, issue 3, 84-108

Abstract: DNA Fragment Assembly Problem (FAP) is concerned with the reconstruction of the target DNA, using the several hundreds (or thousands) of sequenced fragments, by identifying the right order and orientation of each fragment in the layout. Several algorithms have been proposed for solving FAP. Most of these have solely dwelt on the single objective of maximizing the sum of the overlaps between adjacent fragments in order to optimize the fragment layout. This paper aims to formulate this FAP as a bi-objective optimization problem, with the two objectives being the maximization of the overlap between the adjacent fragments and the minimization of the overlap between the distant fragments. Moreover, since there is greater desirability for having lesser number of contigs, FAP becomes a tri-objective optimization problem where the minimization of the number of contigs becomes the additional objective. These problems were solved using the multi-objective genetic algorithm NSGA-II. The experimental results show that the NSGA-II-based Bi-Objective Fragment Assembly Algorithm (BOFAA) and the Tri-Objective Fragment Assembly Algorithm (TOFAA) are able to produce better quality layouts than those generated by the GA-based Single Objective Fragment Assembly Algorithm (SOFAA). Further, the layouts produced by TOFAA are also comparatively better than those produced using BOFAA.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/ijaec.2014070105 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jaec00:v:5:y:2014:i:3:p:84-108

Access Statistics for this article

International Journal of Applied Evolutionary Computation (IJAEC) is currently edited by Sukhpal Singh Gill

More articles in International Journal of Applied Evolutionary Computation (IJAEC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().