{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:25:48Z","timestamp":1787495148610,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540580942","type":"print"},{"value":"9783540484509","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58094-8_4","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:12:25Z","timestamp":1330251145000},"page":"43-53","source":"Crossref","is-referenced-by-count":12,"title":["Approximation algorithms for multiple sequence alignment"],"prefix":"10.1007","author":[{"given":"Vineet","family":"Bafna","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eugene L.","family":"Lawler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pavel A.","family":"Pevzner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1137\/0149012","volume":"49","author":"S.F. Altschul","year":"1989","unstructured":"Altschul S.F., Lipman D.J., Trees, stars, and multiple biological sequence alignment. SIAM J. Appl. Math., 49, (1989), pp. 197\u2013209.","journal-title":"SIAM J. Appl. Math."},{"key":"4_CR2","first-page":"91","volume-title":"Infinite and Finite Sets","author":"Z. Baranyai","year":"1975","unstructured":"Baranyai, Z., On the factorization of the complete uniform hypergraph, Infinite and Finite Sets, A. Hajnal, T. Rado, V. T. S\u00f3s, eds., North-Holland, Amsterdam, (1975), pp. 91\u2013108."},{"key":"4_CR3","unstructured":"B\u00f3sak, J., Decompositions of Graphs, Kluwer Academic Publishers, (1990)."},{"key":"4_CR4","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J.L. Carter","year":"1979","unstructured":"Carter J.L., Wegman M.N., Universal classes of hash functions, Journal of Computer and System Sciences, 18(1979), pp. 143\u2013154.","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR5","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/BF02459635","volume":"54","author":"S.C. Chan","year":"1992","unstructured":"Chan S.C., Wong A.K.C., Chiu D.K.Y., A survey of multiple sequence comparison methods, Bull. Math. Biol., 54(1992), pp. 563\u2013598.","journal-title":"Bull. Math. Biol."},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02603120","volume":"25","author":"D. Feng","year":"1987","unstructured":"Feng D., Doolittle R., Progressive sequence alignment as a prerequisite to correct phylogenetic trees, Journal of Molec. Evol., 25(1987), pp. 351\u2013360.","journal-title":"Journal of Molec. Evol."},{"key":"4_CR7","volume-title":"Tech. Report","author":"D. Gusfield","year":"1991","unstructured":"Gusfield, D., Efficient methods for multiple sequence alignment with guaranteed error bounds. Tech. Report, Computer Science Division, Uiversity of California, Davis, CSE-91-4, (1991)."},{"key":"4_CR8","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02460299","volume":"55","author":"D. Gusfield","year":"1993","unstructured":"Gusfield, D., Efficient methods for multiple sequence alignment with guaranteed error bounds, Bulletin of Mathematical Biology, 55(1993), pp. 141\u2013154.","journal-title":"Bulletin of Mathematical Biology"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Kececioglu J., The maximum weight trace alignment problem in multiple sequence alignment, eds. A. Apostolico, M. Crochemore, Z. Galil, U. Manber, Combinatorial Pattern matching 93, Padova, Italy, June 1993, LNCS 684, 106\u2013119.","DOI":"10.1007\/BFb0029800"},{"key":"4_CR10","doi-asserted-by":"crossref","first-page":"4412","DOI":"10.1073\/pnas.86.12.4412","volume":"86","author":"D.J. Lipman","year":"1989","unstructured":"Lipman D.J., Altschul S.F., Kececioglu J.D., A tool for multiple sequence alignment, Proc. Natl. Acad. Sci. USA, 86(1989), pp. 4412\u20134415.","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"4_CR11","unstructured":"Lorimer, P., Finite Projective Planes and Sharply 2-transitive Subsets of Finite Groups, Proc. Second Internat. Conf. Theory of Groups, Canberra, (1973), pp. 432\u2013436."},{"key":"4_CR12","doi-asserted-by":"crossref","first-page":"1763","DOI":"10.1137\/0152101","volume":"52","author":"P. Pevzner","year":"1992","unstructured":"Pevzner, P., Multiple Alignment, Communication Cost, and Graph Matching, SIAM J. Applied Math., 52, (1992), pp. 1763\u20131779.","journal-title":"SIAM J. Applied Math."},{"key":"4_CR13","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D. Sankoff","year":"1975","unstructured":"Sankoff D., Minimum mutation tree of sequences, SIAM J. Appl. Math., 28, (1975), pp. 35\u201342.","journal-title":"SIAM J. Appl. Math."},{"key":"4_CR14","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D. Sankoff","year":"1985","unstructured":"Sankoff D., Simultaneous solution of the RNA folding, alignment and protosequence problems, SIAM J. Appl. Math., 45 (1985), pp. 810\u2013825.","journal-title":"SIAM J. Appl. Math."},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Schmidt J., Siegel A., The analysis closed hashing under limited randomness, Proceedings of the 22nd ACM Symposium on Theory of Computing, (1990), pp. 224\u2013234.","DOI":"10.1145\/100216.100245"},{"key":"4_CR16","unstructured":"Wang L., Jiang, T., On the Complexity of Multiple Sequence Alignment, 1993, J. of Comp. Biol. (to appear)."},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0001-8708(76)90202-4","volume":"20","author":"M.S. Waterman","year":"1976","unstructured":"Waterman M.S., Smith T.F., Beyer W.A., Some biological sequence metrics. Adv. in Math., 20(1976), pp. 367\u2013387.","journal-title":"Adv. in Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58094-8_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:16:57Z","timestamp":1605629817000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58094-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540580942","9783540484509"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-58094-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}