{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:52:00Z","timestamp":1773273120421,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[1995,2,1]],"date-time":"1995-02-01T00:00:00Z","timestamp":791596800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,2]]},"DOI":"10.1007\/bf01188580","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T21:03:45Z","timestamp":1108674225000},"page":"7-51","source":"Crossref","is-referenced-by-count":158,"title":["Combinatorial algorithms for DNA sequence assembly"],"prefix":"10.1007","volume":"13","author":[{"given":"J. D.","family":"Kececioglu","sequence":"first","affiliation":[]},{"given":"E. W.","family":"Myers","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01188580_CR1","doi-asserted-by":"crossref","unstructured":"Blum, A., T. Jiang, M. Li, J. Tromp, and M. Yannakakis. Linear approximation of shortest superstrings.Proceedings of the 23rd ACM Symposium on Theory of Computation, pp. 328\u2013336, 1991.","DOI":"10.1145\/103418.103455"},{"key":"BF01188580_CR2","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1002\/net.3230090403","volume":"9","author":"P. Camerini","year":"1979","unstructured":"Camerini, P., L. Fratta, and F. Maffioli. A note on finding optimum branchings.Networks 9, 309\u2013312, 1979.","journal-title":"Networks"},{"key":"BF01188580_CR3","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1002\/net.3230100202","volume":"10","author":"P. Camerini","year":"1980","unstructured":"Camerini, P., L. Fratta, and F. Maffioli. Thek best spanning arborescences of a network.Networks 10, 91\u2013110, 1980.","journal-title":"Networks"},{"key":"BF01188580_CR4","doi-asserted-by":"crossref","unstructured":"Chang, W. and E. Lawler. Approximate string matching in sublinear expected time.Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pp. 118\u2013124, 1990. To appear inAlgorithmica.","DOI":"10.1109\/FSCS.1990.89530"},{"key":"BF01188580_CR5","doi-asserted-by":"crossref","first-page":"306","DOI":"10.2307\/3212444","volume":"12","author":"V. Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V., and D. Sankoff. Longest common subsequences of two random sequences.Journal of Applied Probability 12, 306\u2013315, 1975.","journal-title":"Journal of Applied Probability"},{"key":"BF01188580_CR6","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1007\/978-1-4613-9323-8_13","volume-title":"Sequences II: Methods in Communication, Security, and Computer Science","author":"P. Cull","year":"1993","unstructured":"Cull, P. and J. Holloway. Reconstructing sequences from shotgun data. InSequences II: Methods in Communication, Security, and Computer Science, R. Capocelli, A. De Santis, and U. Vaccaro, eds., Springer-Verlag, New York, pp. 166\u2013188, 1993."},{"key":"BF01188580_CR7","volume-title":"Technical Report 812","author":"D. Foulser","year":"1990","unstructured":"Foulser, D. A linear time algorithm for DNA sequencing. Technical Report 812, Department of Computer Science, Yale University, New Haven, CT 06520, 1990."},{"key":"BF01188580_CR8","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"M. Fredman","year":"1986","unstructured":"Fredman, M., R. Sedgewick, D. Sleator, and R. Tarjan. The pairing heap: a new form of self-adjusting heap.Algorithmica 1, 111\u2013129, 1986.","journal-title":"Algorithmica"},{"issue":"3","key":"BF01188580_CR9","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. Fredman","year":"1987","unstructured":"Fredman, M., and R. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms.Journal of the Association for Computing Machinery 34(3), 596\u2013615, 1987.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"2","key":"BF01188580_CR10","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1137\/0206011","volume":"6","author":"H. Gabow","year":"1977","unstructured":"Gabow, H. Two algorithms for generating weighted spanning trees in order.SIAM Journal on Computing 6(2), 139\u2013150, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"BF01188580_CR11","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"H. Gabow","year":"1986","unstructured":"Gabow, H., Z. Galil, T. Spencer, and R. Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.Combinatorica 6, 109\u2013122, 1986.","journal-title":"Combinatorica"},{"key":"BF01188580_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-5193(83)90270-9","volume":"101","author":"J. Gallant","year":"1983","unstructured":"Gallant, J. The complexity of the overlap method for sequencing biopolymers.Journal of Theoretical Biology 101, 1\u201317, 1983.","journal-title":"Journal of Theoretical Biology"},{"issue":"1","key":"BF01188580_CR13","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J. Gallant","year":"1980","unstructured":"Gallant, J., D. Maier, and J. Storer. On finding minimal length superstrings.Journal of Computer and System Sciences 20(1), 50\u201358, 1980.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"BF01188580_CR14","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1093\/nar\/7.2.529","volume":"7","author":"T. Gingeras","year":"1979","unstructured":"Gingeras, T., J. Milazzo, D. Sciaky, and R. Roberts. Computer programs for the assembly of DNA sequences.Nucleic Acids Research 7(2), 529\u2013545, 1979.","journal-title":"Nucleic Acids Research"},{"key":"BF01188580_CR15","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0020-0190(92)90176-V","volume":"41","author":"D. Gusfield","year":"1992","unstructured":"Gusfield, D., G. Landau, and B. Schieber. An efficient algorithm for the all pairs suffix-prefix problem.Information Processing Letters 41, 181\u2013185, 1992.","journal-title":"Information Processing Letters"},{"key":"BF01188580_CR16","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/S0888-7543(05)80277-0","volume":"14","author":"X. Huang","year":"1992","unstructured":"Huang, X. A contig assembly program based on sensitive detection of fragment overlaps.Genomics 14, 18\u201325, 1992.","journal-title":"Genomics"},{"key":"BF01188580_CR17","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1007\/BF02476636","volume":"31","author":"G. Hutchinson","year":"1969","unstructured":"Hutchinson, G. Evaluation of polymer sequence fragments data using graph theory.Bulletin of Mathematical Biophysics 31, 541\u2013562, 1969.","journal-title":"Bulletin of Mathematical Biophysics"},{"key":"BF01188580_CR18","series-title":"Technical Report","volume-title":"Ph.D. dissertation","author":"J. Kececioglu","year":"1991","unstructured":"Kececioglu, J. Exact and approximation algorithms for DNA sequence reconstruction. Ph.D. dissertation, Technical Report 91-26, Department of Computer Science, The University of Arizona, Tucson, AZ 85721, 1991."},{"key":"BF01188580_CR19","series-title":"Technical Report","volume-title":"A procedural interface for a fragment assembly tool","author":"J. Kececioglu","year":"1989","unstructured":"Kececioglu, J., and E. Myers. A procedural interface for a fragment assembly tool. Technical Report 89-5, Department of Computer Science, The University of Arizona, Tucson, AZ 85721, 1989."},{"key":"BF01188580_CR20","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1287\/mnsc.18.7.401","volume":"18","author":"E. Lawler","year":"1972","unstructured":"Lawler, E. A procedure for computing thek best solutions to discrete optimization problems and its application to the shortest path problem.Management Science 18, 401\u2013405, 1972.","journal-title":"Management Science"},{"key":"BF01188580_CR21","doi-asserted-by":"crossref","unstructured":"Li, M. Towards a DNA sequencing theory.Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pp. 125\u2013134, 1990.","DOI":"10.1109\/FSCS.1990.89531"},{"key":"BF01188580_CR22","unstructured":"Manber, U. and G. Myers. Suffix arrays: A new method for on-line string searches.Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 319\u2013327, 1990. To appear inSIAM Journal on Computing."},{"key":"BF01188580_CR23","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0022-2836(89)90362-8","volume":"205","author":"J. Margot","year":"1989","unstructured":"Margot, J., G. W. Demers, and R. Hardison. Complete nucleotide sequence of the rabbit\u03b2-like globin gene cluster: analysis of intergenic sequences and comparison with the human\u03b2-like globin gene cluster.Journal of Molecular Biology 205, 15\u201340, 1989.","journal-title":"Journal of Molecular Biology"},{"key":"BF01188580_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms, Vol. 1","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.Data Structures and Algorithms, Vol. 1. Springer-Verlag, Berlin, 1984."},{"key":"BF01188580_CR25","series-title":"Technical Report 86-2","volume-title":"Incremental alignment algorithms and their applications","author":"E. Myers","year":"1986","unstructured":"Myers, E. Incremental alignment algorithms and their applications. Technical Report 86-2, Department of Computer Science, The University of Arizona, Tucson, AZ 85721, 1986."},{"key":"BF01188580_CR26","unstructured":"Peltola, H., H. S\u00f6derlund, J. Tarhio, and E. Ukkonen. Algorithms for some string matching problems arising in molecular genetics.Proceedings of the 9th IFIP World Computer Congress, pp. 59\u201364, 1983."},{"issue":"1","key":"BF01188580_CR27","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1093\/nar\/12.1Part1.307","volume":"12","author":"H. Peltola","year":"1984","unstructured":"Peltola, H., H. S\u00f6derlund, and E. Ukkonen. SEQAID: a DNA sequence assembly program based on a mathematical model.Nucleic Acids Research 12(1), 307\u2013321, 1984.","journal-title":"Nucleic Acids Research"},{"key":"BF01188580_CR28","volume-title":"Numerical Recipes in C: The Art of Scientific Computing","author":"W. Press","year":"1988","unstructured":"Press, W., B. Flannery, S. Teukolsky, and W. Vetterling.Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, New York, 1988."},{"issue":"1","key":"BF01188580_CR29","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D. Sankoff","year":"1975","unstructured":"Sankoff, D. Minimal mutation trees of sequences.SIAM Journal on Applied Mathematics 28(1), 35\u201342, 1975.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"BF01188580_CR30","first-page":"353","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence comparison","author":"D. Sankoff","year":"1983","unstructured":"Sankoff, D. and V. Chv\u00e1tal. An upper bound technique for lengths of common subsequences. InTime Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence comparison, D. Sankoff and J. Kruskal, eds., Addison-Wesley, Reading, MA, pp. 353\u2013357, 1983."},{"key":"BF01188580_CR31","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","year":"1983","unstructured":"Sankoff, D. and J. Kruskal, eds.Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, MA, 1983."},{"key":"BF01188580_CR32","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/321420.321431","volume":"14","author":"M. Shapiro","year":"1967","unstructured":"Shapiro, M. An algorithm for reconstructing protein and RNA sequences.Journal of the Association for Computing Machinery 14, 720\u2013731, 1967.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF01188580_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02547921","volume":"41","author":"Y. Smetani\u010d","year":"1979","unstructured":"Smetani\u010d, Y., and R. Polozov. On the algorithms for determining the primary structure of biopolymers.Bulletin of Mathematical Biology 41, 1\u201320, 1979.","journal-title":"Bulletin of Mathematical Biology"},{"key":"BF01188580_CR34","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T. F. Smith","year":"1981","unstructured":"Smith, T. F., and M. S. Waterman. Identification of common molecular subsequences.Journal of Molecular Biology 147, 195\u2013197, 1981.","journal-title":"Journal of Molecular Biology"},{"issue":"7","key":"BF01188580_CR35","doi-asserted-by":"crossref","first-page":"2601","DOI":"10.1093\/nar\/6.7.2601","volume":"6","author":"R. Staden","year":"1979","unstructured":"Staden, R. A strategy of DNA sequencing employing computer programs.Nucleic Acids Research 6(7), 2601\u20132610, 1979.","journal-title":"Nucleic Acids Research"},{"key":"BF01188580_CR36","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","volume":"57","author":"J. Tarhio","year":"1988","unstructured":"Tarhio, J. and E. Ukkonen. A greedy approximation algorithm for constructing shortest common superstrings.Theoretical Computer Science 57, 131\u2013145, 1988.","journal-title":"Theoretical Computer Science"},{"key":"BF01188580_CR37","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230070103","volume":"7","author":"R. Tarjan","year":"1977","unstructured":"Tarjan, R. Finding optimum branchings.Networks 7, 25\u201335, 1977.","journal-title":"Networks"},{"key":"BF01188580_CR38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","volume":"83","author":"J. Turner","year":"1989","unstructured":"Turner, J. Approximation algorithms for the shortest common superstring problem.Information and Computation 83, 1\u201320, 1989.","journal-title":"Information and Computation"},{"key":"BF01188580_CR39","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/BF01840391","volume":"5","author":"E. Ukkonen","year":"1990","unstructured":"Ukkonen, E. A linear algorithm for finding approximate shortest common superstrings.Algorithmica 5, 313\u2013323, 1990.","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188580.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01188580\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188580","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T11:31:45Z","timestamp":1734953505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01188580"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,2]]},"references-count":39,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1995,2]]}},"alternative-id":["BF01188580"],"URL":"https:\/\/doi.org\/10.1007\/bf01188580","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,2]]}}}