{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T03:25:33Z","timestamp":1764905133358},"reference-count":11,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,5,1]],"date-time":"2001-05-01T00:00:00Z","timestamp":988675200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4460,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2001,5]]},"DOI":"10.1016\/s0304-3975(99)00324-2","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T11:05:41Z","timestamp":1027595141000},"page":"63-79","source":"Crossref","is-referenced-by-count":71,"title":["The complexity of multiple sequence alignment with SP-score that is a metric"],"prefix":"10.1016","volume":"259","author":[{"given":"Paola","family":"Bonizzoni","sequence":"first","affiliation":[]},{"given":"Gianluca Della","family":"Vedova","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(99)00324-2_BIB1","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0304-3975(97)00023-6","article-title":"Approximation algorithms for multiple sequence alignment","volume":"182","author":"Bafna","year":"1997","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(99)00324-2_BIB2","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1137\/0148063","article-title":"The multiple sequence alignment in biology","volume":"48","author":"Carrillo","year":"1988","journal-title":"SIAM J. Appl. Math."},{"issue":"4","key":"10.1016\/S0304-3975(99)00324-2_BIB3","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/BF02459635","article-title":"A survey of multiple sequence comparison methods","volume":"54","author":"Chan","year":"1992","journal-title":"Bull. Math. Biol."},{"issue":"3","key":"10.1016\/S0304-3975(99)00324-2_BIB4","first-page":"713","article-title":"Letter to the editor: Commentary on the letter by Ward C. Wheeler","volume":"10","author":"Fitch","year":"1993","journal-title":"Mol. Biol. Evol."},{"key":"10.1016\/S0304-3975(99)00324-2_BIB5","unstructured":"M.R. Garey, D.S.Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, CA, 1979."},{"key":"10.1016\/S0304-3975(99)00324-2_BIB6","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02460299","article-title":"Efficient methods for multiple sequence alignment with guaranteed error bounds","volume":"55","author":"Gusfield","year":"1993","journal-title":"Bull. Math. Biol."},{"key":"10.1016\/S0304-3975(99)00324-2_BIB7","doi-asserted-by":"crossref","unstructured":"R.M. Karp, Mapping the genome: some combinatorial problems arising in molecular biology, ACM Symp. on Theory of Computing, 1993, pp. 278\u2013285.","DOI":"10.1145\/167088.167170"},{"key":"10.1016\/S0304-3975(99)00324-2_BIB8","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation and complexity classes","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J. Comput. System Sci."},{"issue":"4","key":"10.1016\/S0304-3975(99)00324-2_BIB9","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","article-title":"On the complexity of multiple sequence alignment","volume":"1","author":"Wang","year":"1994","journal-title":"J. Comput. Biol."},{"issue":"4","key":"10.1016\/S0304-3975(99)00324-2_BIB10","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1089\/cmb.1995.2.509","article-title":"A simplified proof of the NP- and MAX SNP-hardness of multiple sequence tree alignments","volume":"2","author":"Todd Wareham","year":"1995","journal-title":"J. Comput. Biol."},{"issue":"3","key":"10.1016\/S0304-3975(99)00324-2_BIB11","first-page":"707","article-title":"Letter to the editor: the triangle inequality and character analysis","volume":"10","author":"Wheeler","year":"1993","journal-title":"Mol. Biol. Evol."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599003242?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599003242?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T06:51:01Z","timestamp":1556779861000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397599003242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,5]]},"references-count":11,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,5]]}},"alternative-id":["S0304397599003242"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00324-2","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2001,5]]}}}