nach oben

Soft Computing

Erschienen in:

12.10.2015 | Methodologies and Application

An improved problem aware local search algorithm for the DNA fragment assembly problem

verfasst von: Abdelkamel Ben Ali, Gabriel Luque, Enrique Alba, Kamal E. Melkemi

Erschienen in: Soft Computing | Ausgabe 7/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

DNA fragment assembly is a critical and essential early task in a genome project. This task leads to an NP-hard combinatorial optimization problem, and thus, efficient approximate algorithms are required to tackle large problem instances. The Problem Aware Local Search (PALS) is one of the most efficient heuristics for this problem in the literature. PALS gives fairly good solutions but the probability of premature convergence to local optima is significant. In this paper, we propose two modifications to the PALS heuristic in order to ameliorate its performance. The first modification enables the algorithm to improve the tentative solutions in a more appropriate and beneficial way. The second modification permits a significant reduction in the computational demands of the algorithm without significant accuracy loss. Computational experiments confirm that our proposals lead to a more efficient and robust assembler, improving both accuracy and efficiency.

Vorheriger Artikel Predicting agent-based financial time series model on lattice fractal with random Legendre neural network

Nächster Artikel Optimal estimation of power system harmonics using a hybrid Firefly algorithm-based least square method

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

http://www.ncbi.nlm.nih.gov/.

Alba E, Dorronsoro B (2009) Cellular genetic algorithms, vol 42, chap 15—Bioinformatics: The DNA fragment assembly problem. Springer, Berlin, pp 203–210

Alba E, Luque G (2007) A new local search algorithm for the DNA fragment assembly problem. In: Cotta C, van Hemert J (eds) Evolutionary computation in combinatorial optimization: EvoCOP’07, LNCS, vol 4446, Springer, Valencia, Spain, pp 1–12

Alba E, Luque G (2008) A hybrid genetic algorithm for the dna fragment assembly problem. In: Cotta C, van Hemert J (eds) Recent Advances in Evolutionary Computation for Combinatorial Optimization, Studies in Computational Intelligence, vol 153, Springer, pp 101–112

Burks C, Engle M, Forrest S, Parsons R, Soderlund C, Stolorz P (1994) Stochastic optimization tools for genomic sequence assembly. Automated DNA sequencing and analysis. Academic Press, London, pp 249–259

Chen T, Skiena SS (1997) Trie-based data structures for sequence assembly. In: Proceedings of the 8th annual symposium on combinatorial pattern matching. Springer, Berlin, pp 206–223

Dorronsoro B, Alba E, Luque G, Bouvry P (2008) A self-adaptive cellular memetic algorithm for the DNA fragment assembly problem. In: Proceedings of IEEE congress on evolutionary computation, pp 2651–2658

Engle ML, Burks C (1993) Artificially generated data sets for testing DNA sequence assembly algorithms. Genomics 16(1):286–288CrossRef

Firoz JS, Rahman MS, Saha TK (2012) Bee algorithms for solving DNA fragment assembly problem with noisy and noiseless data. In: Proceedings of the 14th annual conference on genetic and evolutionary computation, ACM, New York, pp 201–208

Green P (1994) Phrap, http://www.phrap.org

Huang KW, Chen JL, Yang CS, Tsai CW (2015) A memetic particle swarm optimization algorithm for solving the DNA fragment assembly problem. Neural Comput Appl 26(3):495–506CrossRef

Huang X, Madan A (1999) CAP3: a DNA sequence assembly program. Genome Res 9(9):868–877CrossRef

Kubalik J, Buryan P, Wagner L (2010) 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, ACM, New York, pp 213–214

Li L, Khuri S (2004) A comparison of DNA fragment assembly algorithms. METMBS 4:329–335

Luque G, Alba E, Khuri S (2006) Parallel Algorithms for bioinformatics. Assembling DNA fragments with a distributed genetic algorithm, chapter 16. Wiley, New York

Mallén-Fullerton GM, Hughes JA, Houghten S, Fernández-Anaya G (2013) Benchmark datasets for the DNA fragment assembly problem. Int J Bio-Inspired Comput 5(6):384–394CrossRef

Meksangsouy P, Chaiyaratana N (2003) DNA fragment assembly using an ant colony system algorithm. In: Evolutionary computation, 2003. CEC’03. The 2003 Congress, IEEE, vol 3, pp 1756–1763

Minetti G, Alba E, Luque G (2008) Seeding strategies and recombination operators for solving the DNA fragment assembly problem. Inf Process Lett 108(3):94–100MathSciNetCrossRefMATH

Minetti G, Leguizamón G, Alba E (2014) An improved trajectory-based hybrid metaheuristic applied to the noisy DNA fragment assembly problem. Inf Sci 277:273–283MathSciNetCrossRef

Myers EW (1995) Toward simplifying and accurately formulating fragment assembly. J Comput Biol 2(2):275–290MathSciNetCrossRef

Nebro AJ, Luque G, Luna F, Alba E (2008) DNA fragment assembly using a grid-based genetic algorithm. Comput Op Res 35(9):2776–2790CrossRefMATH

Parsons RJ, Forrest S, Burks C (1995) Genetic algorithms, operators, and DNA fragment assembly. Mach Learn 21(1–2):11–33

Pevzner P (2000) Computational molecular biology: an algorithmic approach. MIT Press, CambridgeMATH

Pop M (2004) Shotgun sequence assembly. Adv Comput 60:193–248CrossRef

Setubal JC, Meidanis J (1997) Introduction to computational molecular biology. Fragment assembly of DNA, Chap 4. University of Campinas, Brazil, pp 105–139

Sutton GG, White O, Adams MD, Kerlavage AR (1995) TIGR assembler: a new tool for assembling large shotgun sequencing projects. Genome Sci Technol 1(1):9–19CrossRef

Titel: An improved problem aware local search algorithm for the DNA fragment assembly problem
verfasst von: Abdelkamel Ben Ali
Gabriel Luque
Enrique Alba
Kamal E. Melkemi
Publikationsdatum: 12.10.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 7/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-015-1875-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 7/2017

Analysing and characterising optimization problems using length scale

Differential evolution dynamics analysis by complex networks

Computational evaluation of a MIP model for multi-port stowage planning problems

Similarity of binary relations based on complete Boolean lattices and related results

Predicting agent-based financial time series model on lattice fractal with random Legendre neural network

Image reduction method based on the F-transform