Article

A new local search algorithm for the DNA fragment assembly problem

Authors:

Enrique Alba,

Gabriel LuqueAuthors Info & Claims

EvoCOP'07: Proceedings of the 7th European conference on Evolutionary computation in combinatorial optimization

Pages 1 - 12

Published: 11 April 2007 Publication History

Abstract

In this paper we propose and study the behavior of a new heuristic algorithm for the DNA fragment assembly problem: PALS. The DNA fragment assembly is a problem to be solved in the early phases of the genome project and thus is very important since the other steps depend on its accuracy. This is an NP-hard combinatorial optimization problem which is growing in importance and complexity as more research centers become involved on sequencing new genomes. Various heuristics, including genetic algorithms, have been designed for solving the fragment assembly problem, but since this problem is a crucial part of any sequencing project, better assemblers are needed. Our proposal is a very efficient assembler that allows to find optimal solutions for large instances of this problem, considerably faster than its competitors and with high accuracy.

References

[1]

J. Setubal and J. Meidanis. Introduction to Computational Molecular Biology, chapter 4 - Fragment Assembly of DNA, pages 105-139. University of Campinas, Brazil, 1997.

Google Scholar

[2]

P. Green. Phrap. http://www.mbt.washington.edu/phrap.docs/phrap.html.

Google Scholar

[3]

G. G. Sutton, O. White, M. D. Adams, and A. R. Kerlavage. TIGR Assembler: A new tool for assembling large shotgun sequencing projects. Genome Science & Technology, pages 9-19, 1995.

Crossref

Google Scholar

[4]

T. Chen and S. S. Skiena. Trie-based data structures for sequence assembly. In The Eighth Symposium on Combinatorial Pattern Matching, pages 206-223, 1998.

Digital Library

Google Scholar

[5]

X. Huang and A. Madan. CAP3: A DNA sequence assembly program. Genome Research, 9:868-877, 1999.

Crossref

Google Scholar

[6]

E. W. Myers. Towards simplifying and accurately formulating fragment assembly. Journal of Computational Biology, 2(2):275-290, 2000.

Crossref

Google Scholar

[7]

P. A. Pevzner. Computational molecular biology: An algorithmic approach. The MIT Press, London, 2000.

Google Scholar

[8]

G Luque and E. Alba. Metaheuristics for the DNA Fragment Assembly Problem. International Journal of Computational Intelligence Research, 1(2):98-108, January 2006.

Google Scholar

[9]

R. Parsons, S. Forrest, and C. Burks. Genetic algorithms, operators, and DNA fragment assembly. Machine Learning, 21:11-33, 1995.

Digital Library

Google Scholar

[10]

L. Li and S. Khuri. A comparison of DNA fragment assembly algorithms. In International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences, pages 329-335, 2004.

Google Scholar

[11]

S. Lin and B.W. Kernighan. An effective heuristic algorithm for TSP. Operations Research, 21:498-516, 1973.

Digital Library

Google Scholar

[12]

M. L. Engle and C. Burks. Artificially generated data sets for testing DNA fragment assembly algorithms. Genomics, 16, 1993.

Google Scholar

[13]

Y. Jing and S. Khuri. Exact and heuristic algorithms for the DNA fragment assembly problem. In Proceedings of the IEEE Computer Society Bioinformatics Conference, pages 581-2, Stanford Univeristy, August 2003. IEEE Press.

Digital Library

Google Scholar

Cited By

View all

Firoz JRahman MSaha TMoore J(2012)Bee algorithms for solving DNA fragment assembly problem with noisy and noiseless dataProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330192(201-208)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330192
Dorronsoro BBouvry PAlba E(2010)Iterated local search for de novo genomic sequencingProceedings of the 10th international conference on Artifical intelligence and soft computing: Part II10.5555/1876119.1876175(428-436)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.5555/1876119.1876175
Kubalik JBuryan PWagner LPelikan MBranke J(2010)Solving the DNA fragment assembly problem efficiently using iterative optimization with evolved hypermutationsProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830522(213-214)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830522

Recommendations

A hybrid crow search algorithm for solving the DNA fragment assembly problem

An adaptation of the crow search algorithm to solve the DNA fragment assembly problem is proposed.A combination of CSA and a PALS based local search allowed superior performances.Generating new solutions is based on a modified ordered crossover operator ...
DNA fragment assembly: an ant colony system approach
EuroGP'06: Proceedings of the 2006 international conference on Applications of Evolutionary Computing

This paper presents the use of an ant colony system (ACS) algorithm in DNA fragment assembly. The assembly problem generally arises during the sequencing of large strands of DNA where the strands are needed to be shotgun-replicated and broken into ...
A memetic gravitation search algorithm for solving DNA fragment assembly problems

The DNA fragment assembly (DFA) problem is among the most critical problems in computational biology. Being NP-hard, it can be efficiently solved via meta-heuristic algorithms, such as the gravitation search algorithm (GSA). GSA is a state-of-the-art ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EvoCOP'07: Proceedings of the 7th European conference on Evolutionary computation in combinatorial optimization

April 2007

240 pages

ISBN:9783540716143

Editors:
Carlos Cotta
Universidad de Málaga, Dept. Lenguajes y Ciencias de la Computación, ETSI Informática, Málaga, Spain
,
Jano Van Hemert
University of Edinburgh, National e-Science Institute, Edinburgh, UK

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 11 April 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Firoz JRahman MSaha TMoore J(2012)Bee algorithms for solving DNA fragment assembly problem with noisy and noiseless dataProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330192(201-208)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330192
Dorronsoro BBouvry PAlba E(2010)Iterated local search for de novo genomic sequencingProceedings of the 10th international conference on Artifical intelligence and soft computing: Part II10.5555/1876119.1876175(428-436)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.5555/1876119.1876175
Kubalik JBuryan PWagner LPelikan MBranke J(2010)Solving the DNA fragment assembly problem efficiently using iterative optimization with evolved hypermutationsProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830522(213-214)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830522

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

A hybrid crow search algorithm for solving the DNA fragment assembly problem

DNA fragment assembly: an ant colony system approach

A memetic gravitation search algorithm for solving DNA fragment assembly problems

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations