×

Modified classical graph algorithms for the DNA fragment assembly problem. (English) Zbl 1461.68159

Summary: DNA fragment assembly represents an important challenge to the development of efficient and practical algorithms due to the large number of elements to be assembled. In this study, we present some graph theoretical linear time algorithms to solve the problem. To achieve linear time complexity, a heap with constant time operations was developed, for the special case where the edge weights are integers and do not depend on the problem size. The experiments presented show that modified classical graph theoretical algorithms can solve the DNA fragment assembly problem efficiently.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68W05 Nonnumerical algorithms
92D20 Protein sequences, DNA sequences

Software:

GAGE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Watson, J.D.; Crick, F.H.; Molecular structure of nucleic acids; Nature: 1953; Volume 171 ,737-738.
[2] Sanger, F.; Nicklen, S.; Coulson, A.R.; DNA sequencing with chain-terminating inhibitors; Proc. Natl. Acad. Sci.: 1977; Volume 74 ,5463-5467.
[3] Staden, R.; A strategy of DNA sequencing employing computer programs; Nucl. Acid. Res.: 1979; Volume 6 ,2601-2610.
[4] Van Belkum, A.; Scherer, S.; van Alphen, L.; Verbrugh, H.; Short-sequence DNA repeats in prokaryotic genomes; Microbiol. Mol. Biol. Rev.: 1998; Volume 62 ,275-293.
[5] Salzberg, S.L.; Phillippy, A.M.; Zimin, A.; Puiu, D.; Magoc, T.; Koren, S.; Yorke, J.A.; GAGE: A critical evaluation of genome assemblies and assembly algorithms; Gen. Res.: 2012; Volume 22 ,557-567.
[6] Shendure, J.; Ji, H.; Next-generation DNA sequencing; Nat. Biotechnol.: 2008; Volume 26 ,1135-1145.
[7] Pevzner, P.A.; Tang, H.; Waterman, M.S.; An Eulerian path approach to DNA fragment assembly; Proc. Natl. Acad. Sci.: 2001; Volume 98 ,9748-9753. · Zbl 0993.92018
[8] Parsons, R.J.; Forrest, S.; Burks, C.; Genetic algorithms for DNA sequence assembly; Proceedings of the First International Conference on Intelligent Systems for Molecular Biology (ISMB): ; ,310-318.
[9] Krause, J.; Cordeiro, J.; Parpinelli, R.S.; Lopes, H.S.; A Survey of Swarm Algorithms Applied to Discrete Optimization Problems; Swarm Intelligence and Bio-inspired Computation: Theory and Applications: Amsterdam, The Netherlands 2013; .
[10] Alba, E.; Luque, G.; A new local search algorithm for the DNA fragment assembly problem; Evolutionary Computation in Combinatorial Optimization: Berlin/Heidelberg, Germany 2007; ,1-12.
[11] Luque, G.; Alba, E.; Metaheuristics for the DNA fragment assembly problem; Int. J. Comput. Intel. Res.: 2005; Volume 1 ,98-108.
[12] Firoz, J.S.; Rahman, M.S.; Saha, T.K.; Bee algorithms for solving DNA fragment assembly problem with noisy and noiseless data; Proceedings of the 14th ACM Annual Conference on Genetic and Evolutionary Computation: ; ,201-208.
[13] Mallen-Fullerton, G.M.; Fernandez-Anaya, G.; DNA fragment assembly using optimization; Proceedings of the 2013 IEEE Congress on Evolutionary Computation (CEC): ; ,1570-1577. · Zbl 1461.92076
[14] Gallant, J.; Maier, D.; Astorer, J.; On finding minimal length superstrings; J. Comput. Syst. Sci.: 1980; Volume 20 ,50-58. · Zbl 0436.68043
[15] Prim, R.C.; Shortest connection networks and some generalizations; Bell Syst. Tech. J.: 1957; Volume 36 ,1389-1401.
[16] Kruskal, J.B.; On the shortest spanning subtree of a graph and the traveling salesman problem; Proc. Am. Math. Soc.: 1956; Volume 7 ,48-50. · Zbl 0070.18404
[17] Hopcroft, J.E.; Ullman, J.D.; Set merging algorithms; SIAM J. Comput.: 1973; Volume 2 ,294-303. · Zbl 0253.68003
[18] Bonfield, J.K.; Smith, K.; Staden, R.; A new DNA sequence assembly program; Nucl. Acid. Res.: 1995; Volume 23 ,4992-4999.
[19] Mallén-Fullerton, G.M.; Hughes, J.A.; Houghten, S.; Fernández-Anaya, G.; Benchmark datasets for the DNA fragment assembly problem; Int. J. Bio-Inspir. Comput.: 2013; Volume 5 ,384-394.
[20] Staphylococcus aureus subsp. aureus MW2 DNA, complete genome, GenBank: BA000033.2; ; .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.