research-article

Bee algorithms for solving DNA fragment assembly problem with noisy and noiseless data

Authors:

Jesun Sahariar Firoz,

M. Sohel Rahman,

Tanay Kumar SahaAuthors Info & Claims

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

Pages 201 - 208

https://doi.org/10.1145/2330163.2330192

Published: 07 July 2012 Publication History

Abstract

DNA fragment assembly problem is one of the crucial challenges faced by computational biologists where, given a set of DNA fragments, we have to construct a complete DNA sequence from them. As it is an NP-hard problem, accurate DNA sequence is hard to find. Moreover, due to experimental limitations, the fragments considered for assembly are exposed to additional errors while reading the fragments. In such scenarios, meta-heuristic based algorithms can come in handy. We analyze the performance of two swarm intelligence based algorithms namely Artificial Bee Colony (ABC) algorithm and Queen Bee Evolution Based on Genetic Algorithm (QEGA) to solve the fragment assembly problem and report quite promising results. Our main focus is to design meta-heuristic based techniques to efficiently handle DNA fragment assembly problem for noisy and noiseless data.

References

[1]

http://ab.inf.uni-tuebingen.de/teaching/ss07/albi2/script/readsim_2July2007.pdf. {Online; accessed 16-November-2011}.

[2]

http://www.ncbi.nlm.nih.gov/nuccore/178817?report=fasta(M15421.1). {Online; accessed 20-November-2011}.

[3]

http://www.ncbi.nlm.nih.gov/nuccore/34645?report=fasta(X60189.1. {Online; accessed 20-November-2011}.

[4]

http://www.ncbi.nlm.nih.gov/nuccore/215104?report=fasta(J02459.1. {Online; accessed 20-November-2011}.

[5]

http://0-www.ncbi.nlm.nih.gov.ilsprod.lib.neu.edu/Traces/wgs/?hide\_master\\*=\&val=ACIN02000001\#9(ACIN\_ALL). {Online; accessed20-November-2011}.

[6]

E. Alba and G. Luque. A new local search algorithm for the DNA fragment assembly problem. In Evolutionary Computation in Combinatorial Optimization, EvoCOP'07, Lecture Notes in Computer Science 4446, pages 1--12, Valencia, Spain, April 2007. Springer.

Digital Library

[7]

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

Digital Library

[8]

B. Dorronsoro, E. Alba, G. Luque, and P. Bouvry. A self-adaptive cellular memetic algorithm for the DNA fragment assembly problem. In IEEE Congress on Evolutionary Computation, pages 2651--2658, 2008.

[9]

M. L. Engle and C. Burks. Artificially generated data sets for testing DNA sequence assembly algorithms. Genomics, 16(1):286--8, 1993.

[10]

M. M. et al. Genome sequencing in microfabricated high-density picolitre reactors. Nature, 437(7057):376--80, 2005.

[11]

J. S. Firoz, M. S. Rahman, and T. k. Saha. Analyzing memetic algorithm behavior in DNA fragment assembly problem for noisy data. In 4th International Conference on Bioinformatics and Computational Biology (BICoB),Las Vegas, Nevada, USA, 2012.

[12]

P. Green. Phrap. http://www.phrap.org/. {Online; accessed 20-November-2011}.

[13]

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

[14]

C. G. Hur. Fasim: Fragments assembly simulation using biased-sampling model and assembly simulation for microbial genome shotgun sequencing.

[15]

S. H. Jung. Queen-bee evolution for genetic algorithms. Electronics Letters, 39:575--576, March 2003.

[16]

D. Karaboga and B. Basturk. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (abc) algorithm. J. of Global Optimization, 39:459--471, November 2007.

Digital Library

[17]

J. Kubalik, P. Buryan, and L. Wagner. Solving the dna fragment assembly problem efficiently using iterative optimization with evolved hypermutations. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, GECCO '10, pages 213--214, New York, NY, USA, 2010. ACM.

Digital Library

[18]

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

[19]

M. Margulies, M. Egholm, W. E. Altman, S. Attiya, J. S. Bader, L. A. Bemben, J. Berka, M. S. Braverman, Y.-J. Chen, Z. Chen, and et al. Genome sequencing in microfabricated high-density picolitre reactors. Nature, 437(7057):376--380, 2005.

[20]

P. Meksangsouy and N. Chaiyaratana. DNA fragment assembly using an ant colony system algorithm. In Proceedings of Congress on Evolutionary Computation, volume 3, pages 1756--1763, 2003.

[21]

D. Meldrum. Automation for genomics, part one: Preparation for sequencing. Genome Research, 10(8):1081--1092, 2000.

[22]

D. Meldrum. Automation for genomics, part two: Sequencers, microarrays, and future trends. Genome Research, 10(9):1288--1303, 2000.

[23]

G. Minetti and E. Alba. Metaheuristic assemblers of DNA strands: Noiseless and noisy cases. In IEEE Congress on Evolutionary Computation'10, pages 1--8, 2010.

[24]

E. W. Myers. Toward simplifying and accurately formulating fragment assembly. Journal of Computational Biology, 2:275--290, 1995.

[25]

G. Myers. A dataset generator for whole genome shotgun sequencing. In Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, pages 202--210. AAAI Press, 1999.

Digital Library

[26]

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

[27]

L. Qin, Q. Jiang, Z. Zou, and Y. Cao. A queen-bee evolution based on genetic algorithm for economic power dispatch. In 39th International Universities Power Engineering Conference, volume 1, pages 453--456, September 2004.

[28]

D. R and Bentley. Whole-genome re-sequencing. Current Opinion in Genetics and Development, 16(6):545 -- 552, 2006.

[29]

D. C. Richter, F. Ott, A. F. Auch, R. Schmid, and D. H. Huson. Metasim:a sequencing simulator for genomics and metagenomics. PLoS ONE, 3(10):e3373+, 2008.

[30]

J. Setubal and J. Meidanis. Fragment assembly of DNA. Introduction to Computational Molecular Biology, pages 105--139, 1997.

[31]

J. C. Setubal and J. Meidanis. Introduction to Computational Molecular Biology. PWS Publishing Company, 1997.

[32]

G. Sutton, W. O., A. M.D., and K. A.R. Tigr assembler: A new tool for assembling large shotgun sequencing projects. Genome Science and Tech, pages 9--19, 1995.

[33]

E. G. Talbi. Metaheuristics from design to implementation. WILEY, 2009.

Digital Library

Cited By

G. RU. S(2023)Fragment Assembly Based Fast and Optimal DNA SequencingResearch Anthology on Bioinformatics, Genomics, and Computational Biology10.4018/979-8-3693-3026-5.ch030(633-649)Online publication date: 29-Dec-2023
https://doi.org/10.4018/979-8-3693-3026-5.ch030
G. RU. S(2023)Fragment Assembly Based Fast and Optimal DNA SequencingStructural and Functional Aspects of Biocomputing Systems for Data Processing10.4018/978-1-6684-6523-3.ch003(57-78)Online publication date: 20-Jan-2023
https://doi.org/10.4018/978-1-6684-6523-3.ch003
Rathee MDilip KRathee R(2021)DNA Fragment Assembly Using Quantum-Inspired Genetic AlgorithmResearch Anthology on Advancements in Quantum Technology10.4018/978-1-7998-8593-1.ch009(228-245)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-8593-1.ch009
Show More Cited By

Index Terms

Bee algorithms for solving DNA fragment assembly problem with noisy and noiseless data
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem

Determining the sequence of a long DNA chain first requires dividing it into subset fragments. The DNA fragment assembly (DFA) approach is then used for reassembling the fragments as an NP-hard problem that is the focus of increasing attention from ...
Bee colony optimization for the p-center problem

Bee colony optimization (BCO) is a relatively new meta-heuristic designed to deal with hard combinatorial optimization problems. It is biologically inspired method that explores collective intelligence applied by the honey bees during nectar collecting ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

July 2012

1396 pages

ISBN:9781450311779

DOI:10.1145/2330163

Editor:
Terence Soule
University of Idaho, USA
,
General Chair:
Jason H. Moore
Dartmouth College, USA

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '12

Sponsor:

SIGEVO

GECCO '12: Genetic and Evolutionary Computation Conference

July 7 - 11, 2012

Pennsylvania, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
291
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

G. RU. S(2023)Fragment Assembly Based Fast and Optimal DNA SequencingResearch Anthology on Bioinformatics, Genomics, and Computational Biology10.4018/979-8-3693-3026-5.ch030(633-649)Online publication date: 29-Dec-2023
https://doi.org/10.4018/979-8-3693-3026-5.ch030
G. RU. S(2023)Fragment Assembly Based Fast and Optimal DNA SequencingStructural and Functional Aspects of Biocomputing Systems for Data Processing10.4018/978-1-6684-6523-3.ch003(57-78)Online publication date: 20-Jan-2023
https://doi.org/10.4018/978-1-6684-6523-3.ch003
Rathee MDilip KRathee R(2021)DNA Fragment Assembly Using Quantum-Inspired Genetic AlgorithmResearch Anthology on Advancements in Quantum Technology10.4018/978-1-7998-8593-1.ch009(228-245)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-8593-1.ch009
Rathee MDilip KRathee R(2021)DNA Fragment Assembly Using Quantum-Inspired Genetic AlgorithmResearch Anthology on Multi-Industry Uses of Genetic Programming and Algorithms10.4018/978-1-7998-8048-6.ch041(811-828)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-8048-6.ch041
Abdel-Basset MMohamed RSallam KChakrabortty RRyan M(2020)An Efficient-Assembler Whale Optimization Algorithm for DNA Fragment Assembly Problem: Analysis and ValidationsIEEE Access10.1109/ACCESS.2020.30448578(222144-222167)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3044857
Rathee MDilip KRathee R(2019)DNA Fragment Assembly Using Quantum-Inspired Genetic AlgorithmExploring Critical Approaches of Evolutionary Computation10.4018/978-1-5225-5832-3.ch005(80-98)Online publication date: 2019
https://doi.org/10.4018/978-1-5225-5832-3.ch005
(2018)CS-ABCInternational Journal of Data Mining and Bioinformatics10.5555/3302691.330269521:2(145-168)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3302691.3302695
Vidal POlivera A(2018)Ensamblado de fragmentos de ADN utilizando un novedoso algoritmo de luciérnaga en GPUDYNA10.15446/dyna.v85n204.6007885:204(108-116)Online publication date: 1-Jan-2018
https://doi.org/10.15446/dyna.v85n204.60078
Ben Ali ALuque GAlba EMelkemi K(2017)An improved problem aware local search algorithm for the DNA fragment assembly problemSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1875-221:7(1709-1720)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s00500-015-1875-2
Bucur D(2017)De Novo DNA Assembly with a Genetic Algorithm Finds Accurate Genomes Even with Suboptimal FitnessApplications of Evolutionary Computation10.1007/978-3-319-55849-3_5(67-82)Online publication date: 25-Mar-2017
https://doi.org/10.1007/978-3-319-55849-3_5
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents