{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:40:09Z","timestamp":1787496009441,"version":"build-2736575974"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1996,9,1]],"date-time":"1996-09-01T00:00:00Z","timestamp":841536000000},"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":[[1996,9]]},"DOI":"10.1007\/bf01955679","type":"journal-article","created":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T11:15:58Z","timestamp":1122894958000},"page":"302-315","source":"Crossref","is-referenced-by-count":45,"title":["Approximation algorithms for tree alignment with a given phylogeny"],"prefix":"10.1007","volume":"16","author":[{"given":"Lusheng","family":"Wang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"E. L.","family":"Lawler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01955679_CR1","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1137\/0149012","volume":"49","author":"S. Altschul","year":"1989","unstructured":"S. Altschul and D. Lipman, Trees, stars, and multiple sequence alignment,SIAM J. Appl. Math.,49 (1989), 197\u2013209.","journal-title":"SIAM J. Appl. Math."},{"key":"BF01955679_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems,Proc. 33rd IEEE Symp. on Foundations of Computer Science, 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"BF01955679_CR3","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"M. Bern and P. Plassmann, The Steiner problem with edge lengths 1 and 2,Inform. Process. Lett.,32 (1989), 171\u2013176.","journal-title":"Inform. Process. Lett."},{"key":"BF01955679_CR4","doi-asserted-by":"crossref","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,SIAM J. Appl. Math.,48 (1988), 1073\u20131082.","journal-title":"SIAM J. Appl. Math."},{"issue":"4","key":"BF01955679_CR5","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/BF02459635","volume":"54","author":"S. C. Chan","year":"1992","unstructured":"S. C. Chan, A. K. C. Wong, and D. K. T. Chiu, A survey of multiple sequence comparison methods,Bull. Math. Biol.,54(4) (1992), 563\u2013598.","journal-title":"Bull. Math. Biol."},{"key":"BF01955679_CR6","doi-asserted-by":"crossref","unstructured":"D. Z. Du, Y. Zhang, and Q. Feng, On better heuristic for Euclidean Steiner minimum trees,Proc. 32nd IEEE Symp. on Foundations of Computer Science, 1991, pp. 431\u2013439.","DOI":"10.1109\/SFCS.1991.185402"},{"key":"BF01955679_CR7","doi-asserted-by":"crossref","first-page":"83","DOI":"10.2307\/2412028","volume":"19","author":"J. S. Farris","year":"1970","unstructured":"J. S. Farris, Methods for computing Wagner trees,Systematic Zoology,19 (1970), 83\u201392.","journal-title":"Systematic Zoology"},{"key":"BF01955679_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979."},{"key":"BF01955679_CR9","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02460299","volume":"55","author":"D. Gusfield","year":"1993","unstructured":"D. Gusfield, Efficient methods for multiple sequence alignment with guaranteed error bounds,Bull. Math. Biol.,55 (1993), 141\u2013154.","journal-title":"Bull. Math. Biol."},{"issue":"6","key":"BF01955679_CR10","first-page":"669","volume":"6","author":"J. J. Hein","year":"1989","unstructured":"J. J. Hein, A tree reconstruction method that is economical in the number of pairwise comparisons used,Mol. Biol. Evol.,6(6) (1989), 669\u2013684.","journal-title":"Mol. Biol. Evol."},{"issue":"6","key":"BF01955679_CR11","first-page":"649","volume":"6","author":"J. J. Hein","year":"1989","unstructured":"J. J. Hein, A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phytogeny is given,Mol. Biol. Evol.,6(6) (1989), 649\u2013668.","journal-title":"Mol. Biol. Evol."},{"key":"BF01955679_CR12","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/net.3230220105","volume":"22","author":"F. K. Hwang","year":"1992","unstructured":"F. K. Hwang and D. S. Richards, Steiner tree problems,Networks,22 (1992), 55\u201389.","journal-title":"Networks"},{"key":"BF01955679_CR13","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1016\/0196-6774(92)90050-M","volume":"13","author":"F. K. Hwang","year":"1992","unstructured":"F. K. Hwang and J. F. Weng, The shortest network under a given topology,J. Algorithms,13 (1992), 468\u2013488.","journal-title":"J. Algorithms"},{"key":"BF01955679_CR14","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"R. M. Karp","year":"1977","unstructured":"R. M. Karp, Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane,Math. Oper. Res.,2 (1977), 209\u2013224.","journal-title":"Math. Oper. Res."},{"key":"BF01955679_CR15","doi-asserted-by":"crossref","unstructured":"R. M. Karp, Mapping the genome: some combinatorial problems arising in molecular biology,Proc. ACM Symp. on Theory of Computing, 1993, pp. 278\u2013285.","DOI":"10.1145\/167088.167170"},{"issue":"11","key":"BF01955679_CR16","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/125490.125491","volume":"34","author":"E. S. Lander","year":"1991","unstructured":"E. S. Lander, R. Langridge, and D. M. Saccocio, Mapping and interpreting biological information,Comm. ACM,34(11) (1991), 33\u201339.","journal-title":"Comm. ACM"},{"key":"BF01955679_CR17","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes,J. Comput. System Sci.,43 (1991), 425\u2013440.","journal-title":"J. Comput. System Sci."},{"key":"BF01955679_CR18","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF01739097","volume":"8","author":"D. Penny","year":"1976","unstructured":"D. Penny, Criteria for optimising phylogenetic trees and the problem of determining the root of a tree,J. Mol. Evol.,8 (1976), 95\u2013116.","journal-title":"J. Mol. Evol."},{"issue":"1","key":"BF01955679_CR19","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D. Sankoff","year":"1975","unstructured":"D. Sankoff, Minimal mutation trees of sequences,SIAM J. Appl. Math.,28(1) (1975), 35\u201342.","journal-title":"SIAM J. Appl. Math."},{"key":"BF01955679_CR20","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/BF01681346","volume":"9","author":"D. Sankoff","year":"1975","unstructured":"D. Sankoff and P. Rousseau, Locating the vertices of a Steiner tree in an arbitrary metric space,Math. Programming,9 (1975), 240\u2013246.","journal-title":"Math. Programming"},{"key":"BF01955679_CR21","first-page":"253","volume-title":"Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison","author":"D. Sankoff","year":"1983","unstructured":"D. Sankoff and R. Cedergren, Simultaneous comparisons of three or more sequences related by a tree, in D. Sankoff and J. Kruskal (eds.),Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison, pp. 253\u2013264, Addison-Wesley, Reading, MA, 1983."},{"key":"BF01955679_CR22","volume-title":"Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison","year":"1983","unstructured":"D. Sankoff and J. Kruskal (eds.),Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, MA, 1983."},{"key":"BF01955679_CR23","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01732471","volume":"7","author":"D. Sankoff","year":"1976","unstructured":"D. Sankoff, R. Cedergren, and G. Lapalme, Frequency of insertion-deletion, transversion, and transition in the evolution of 5S ribosomal RNA,J. Mol. Evol.,7 (1976), 133\u2013149.","journal-title":"J. Mol. Evol."},{"issue":"4","key":"BF01955679_CR24","first-page":"406","volume":"4","author":"N. Saitou","year":"1987","unstructured":"N. Saitou and M. Nei, The neighbor-joining method: a new method for reconstructing phylogenetic trees,Mol. Biol. Evol.,4(4) (1987), 406\u2013425.","journal-title":"Mol. Biol. Evol."},{"issue":"4","key":"BF01955679_CR25","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. Computat. Biol.,1(4) (1994), 337\u2013348.","journal-title":"J. Computat. Biol."},{"key":"BF01955679_CR26","first-page":"53","volume-title":"Mathematical Methods for DNA Sequences","author":"M. S. Waterman","year":"1989","unstructured":"M. S. Waterman, Sequence alignments, in M. S. Waterman (ed.),Mathematical Methods for DNA Sequences, CRC, Boca Raton, FL, 1989, pp. 53\u201392."},{"key":"BF01955679_CR27","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1007\/BF02459504","volume":"46","author":"M. S. Waterman","year":"1984","unstructured":"M. S. Waterman and M. D. Perlwitz, Line geometries for sequence comparisons.Bull. Math. Biol.,46 (1984), 567\u2013577.","journal-title":"Bull. Math. Biol."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01955679.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01955679\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01955679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T13:21:03Z","timestamp":1557753663000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01955679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["BF01955679"],"URL":"https:\/\/doi.org\/10.1007\/bf01955679","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}