DocumentCode :
445459
Title :
Assembling DNA fragments with parallel algorithms
Author :
Alba, Enrique ; Luque, Gabriel ; Khuri, Sami
Author_Institution :
Dept. de Lenguajes y Ciencias de la Computacion, E.T.S.I. Informatica, Malaga
Volume :
1
fYear :
2005
fDate :
5-5 Sept. 2005
Firstpage :
57
Abstract :
As more research centers embark on sequencing new genomes, the problem of DNA fragment assembly for shotgun sequencing is growing in importance and complexity. Accurate and fast assembly is a crucial part of any sequencing project and since the DNA fragment assembly problem is NP-hard, exact solutions are very difficult to obtain. Various heuristics, including genetic algorithms, were designed for solving the fragment assembly problem. While the sequential genetic algorithm has given good results, it is unable to sequence very large DNA molecules. In this work, we present two parallel methods, a distributed genetic algorithm and a parallel simulated annealing, to solve problem instances that are 77K base pairs long accurately
Keywords :
DNA; biology computing; genetic algorithms; parallel algorithms; simulated annealing; DNA fragment assembly problem; DNA molecules; NP-hard problem; distributed genetic algorithm; genomes; parallel algorithms; parallel methods; parallel simulated annealing; shotgun sequencing; Algorithm design and analysis; Assembly; Bioinformatics; DNA; Genetic algorithms; Genomics; Packaging; Parallel algorithms; Sequences; Simulated annealing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Evolutionary Computation, 2005. The 2005 IEEE Congress on
Conference_Location :
Edinburgh, Scotland
Print_ISBN :
0-7803-9363-5
Type :
conf
DOI :
10.1109/CEC.2005.1554667
Filename :
1554667
Link To Document :
بازگشت