{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:56Z","timestamp":1725664136509},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600442"},{"type":"electronic","value":"9783540494126"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60044-2_39","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:34:39Z","timestamp":1330259679000},"page":"128-143","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Making the shortest-paths approach to sum-of-pairs multiple sequence alignment more space efficient in practice"],"prefix":"10.1007","author":[{"given":"Sandeep K.","family":"Gupta","sequence":"first","affiliation":[]},{"given":"John D.","family":"Kececioglu","sequence":"additional","affiliation":[]},{"given":"Alejandro A.","family":"Sch\u00e4ffer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/S0022-5193(89)80196-1","volume":"138","author":"S. F. Altschul","year":"1989","unstructured":"S. F. Altschul. Gap costs for multiple sequence alignment. J. Theor. Biol., 138:297\u2013309, 1989.","journal-title":"J. Theor. Biol."},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1016\/0022-2836(89)90234-9","volume":"207","author":"S. F. Altschul","year":"1989","unstructured":"S. F. Altschul, Raymond J. Carroll, and David J. Lipman. Weights for data related by a tree. J. Molecular Biology, 207:647\u2013653, 1989.","journal-title":"J. Molecular Biology"},{"key":"10_CR3","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0022-2836(87)90316-0","volume":"198","author":"G. J. Barton","year":"1987","unstructured":"G. J. Barton and M. J. E. Sternberg. Evaluation and improvements in the automatic alignment of protein sequences. J. Mol. Biol., 198:327\u2013337, 1987.","journal-title":"J. Mol. Biol."},{"key":"10_CR4","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1093\/protein\/1.2.89","volume":"1","author":"G. J. Barton","year":"1987","unstructured":"G. J. Barton and M. J. E. Sternberg. A strategy for the rapid multiple alignment of protein sequences. Protein Engineering, 1:89\u201394, 1987.","journal-title":"Protein Engineering"},{"key":"10_CR5","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/3-540-58094-8_2","volume":"807","author":"H. Bodlaender","year":"1994","unstructured":"H. Bodlaender, R. G. Downey, M. R. Fellows, and H. T. Wareham. The parameterized complexity of sequence alignment and consensus. In Proc. of the 5th Symp. on Combinatorial Pattern Matching, Lecture Notes Comp. Sci. 807, pages 15\u201330, 1994.","journal-title":"Lecture Notes Comp. Sci."},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"H. Carrillo","year":"1988","unstructured":"H. Carrillo and D. Lipman. The multiple sequence alignment problem in biology. SLAM J. Appl. Math., 48:1073\u20131082, 1988.","journal-title":"SLAM J. Appl. Math."},{"key":"10_CR7","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1016\/S0092-8240(05)80077-1","volume":"54","author":"S. C. Chan","year":"1992","unstructured":"S. C. Chan, A. K. C. Wong, and D. K. Y. Chiu. A survey of multiple sequence comparison methods. Bulletin of Mathematical Biology, 54:563\u2013598, 1992.","journal-title":"Bulletin of Mathematical Biology"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269\u2013271, 1959.","journal-title":"Numerische Mathematik"},{"key":"10_CR9","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","volume":"25","author":"D. Feng","year":"1987","unstructured":"D. Feng and R. Doolittle. Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J. Molecular Evol., 25:351\u2013360, 1987.","journal-title":"J. Molecular Evol."},{"key":"10_CR10","first-page":"189","volume":"8","author":"D. G. Higgins","year":"1992","unstructured":"D. G. Higgins, A. J. Bleasby, and R. Fuchs. Clustal v: improved software for multiple sequence alignment. CABIOS, 8:189\u2013191, 1992.","journal-title":"CABIOS"},{"key":"10_CR11","unstructured":"J. Kececioglu. Notes on an approach of Carrillo and Lipman to minimum sum of pairs multiple sequence alignment. Unpublished notes, 1989."},{"key":"10_CR12","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/BFb0029800","volume":"684","author":"J. Kececioglu","year":"1993","unstructured":"J. Kececioglu. The maximum weight trace problem in multiple sequence alignment. In Proc. of the 4th Symp. on Combinatorial Pattern Matching, Springer-Verlag Lecture Notes in Comp. Sci. 684, pages 106\u2013119, 1993.","journal-title":"Springer-Verlag Lecture Notes in Comp. Sci."},{"key":"10_CR13","doi-asserted-by":"crossref","first-page":"4412","DOI":"10.1073\/pnas.86.12.4412","volume":"86","author":"D. J. Lipman","year":"1989","unstructured":"D. J. Lipman, S. F. Altschul, and J. D. Kececioglu. A tool for multiple sequence alignment. Proc. Natl. Acad. Sci. USA., 86:4412\u20134415, 1989.","journal-title":"Proc. Natl. Acad. Sci. USA."},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"D. Maier. The complexity of some problems on subsequences and supersequences. J. ACM, 25:322\u2013336, 1978.","journal-title":"J. ACM"},{"key":"10_CR15","first-page":"571","volume":"11","author":"M. A. McClure","year":"1994","unstructured":"M. A. McClure, T. K. Vasi, and W. M. Fitch. Comparative analysis of multiple protein-sequence alignment methods. Mol. Biol. Evol., 11:571\u2013592, 1994.","journal-title":"Mol. Biol. Evol."},{"key":"10_CR16","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1016\/0022-2836(89)90592-5","volume":"209","author":"S. Subbiah","year":"1989","unstructured":"S. Subbiah and S. C. Harrison. A method for multiple sequence alignment with gaps. J. Mol. Biol., 209:539\u2013548, 1989.","journal-title":"J. Mol. Biol."},{"key":"10_CR17","first-page":"81","volume":"3","author":"W. R. Taylor","year":"1987","unstructured":"W. R. Taylor. Multiple sequence alignment by a pairwise algorithm. CABIOS, 3:81\u201387, 1987.","journal-title":"CABIOS"},{"key":"10_CR18","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF02143508","volume":"28","author":"W. R. Taylor","year":"1988","unstructured":"W. R. Taylor. A flexible method to align large numbers of biological sequences. Journal of Molecular Evolution, 28:161\u2013169, 1988.","journal-title":"Journal of Molecular Evolution"},{"key":"10_CR19","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"L. Wang","year":"1994","unstructured":"L. Wang and T. Jiang. On the complexity of multiple sequence alignment. J. Computational Biology, 1:337\u2013348, 1994.","journal-title":"J. Computational Biology"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60044-2_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T21:19:45Z","timestamp":1578518385000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60044-2_39"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600442","9783540494126"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-60044-2_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}