Recentering and Restarting Genetic Algorithm variations for DNA Fragment Assembly

Author

Hughes, John ; Houghten, Sheridan ; Mallen-Fullerton, Guillermo M. ; Ashlock, Daniel

Author_Institution

Comput. Sci., Brock Univ., St. Catharines, ON, Canada

fYear

2014

fDate

21-24 May 2014

Firstpage

1

Lastpage

8

Abstract

The Fragment Assembly Problem is a major component of the DNA sequencing process that is identified as being NP-Hard. A variety of approaches to this problem have been used, including overlap-layout-consensus, de Bruijn graphs, and greedy graph based algorithms. The overlap-layout-consensus approach is one of the more popular strategies which has been studied on a collection of heuristics and metaheuristics. In this study heuristics and Genetic Algorithm variations are combined to exploit their respective benefits. These algorithms were able to produce results that surpassed the best results obtained by a collection of state-of-the-art metaheuristics on ten of sixteen popular benchmark data sets.

Keywords

DNA; benchmark testing; bioinformatics; genetic algorithms; graphs; greedy algorithms; molecular biophysics; molecular configurations; DNA fragment assembly problem; DNA sequencing process; NP-Hard; de Bruijn graphs; genetic algorithm variation recentering; genetic algorithm variation restarting; greedy graph based algorithms; heuristics collection; overlap-layout-consensus; popular benchmark data sets; state-of-the-art metaheuristics collection; Assembly; Biological cells; DNA; Genetic algorithms; Sequential analysis; Sociology; Statistics; Bioinformatics; DNA Fragment Assembly; Evolutionary Algorithms; Genetic Algorithms; Island Model; Recentering-Restarting; Representation; Ring Species;

fLanguage

English

Publisher

ieee

Conference_Titel

Computational Intelligence in Bioinformatics and Computational Biology, 2014 IEEE Conference on

Conference_Location

Honolulu, HI

Type

conf

DOI

10.1109/CIBCB.2014.6845500

Filename

6845500