{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T04:25:59Z","timestamp":1778732759955,"version":"3.51.4"},"reference-count":30,"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\/bf01188585","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T21:03:45Z","timestamp":1108674225000},"page":"155-179","source":"Crossref","is-referenced-by-count":88,"title":["A robust model for finding optimal evolutionary trees"],"prefix":"10.1007","volume":"13","author":[{"given":"M.","family":"Farach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Warnow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"BF01188585_CR1","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A. V. Aho","year":"1981","unstructured":"A. V. Aho, Y. Sagiv, T. G. Szymanski, and J. D. Ullman, Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions,SIAM J. Comput., 10(3):405\u2013421, 1981.","journal-title":"SIAM J. Comput."},{"key":"BF01188585_CR2","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1016\/0022-2836(91)90193-A","volume":"219","author":"S. F. Altschul","year":"1991","unstructured":"S. F. Altschul, Amino acid substitution matrices from an information theoretic perspective,J. Mol. Biol., 219:555\u2013565, 1991.","journal-title":"J. Mol. Biol."},{"key":"BF01188585_CR3","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0025-5564(74)90028-5","volume":"19","author":"W. Beyer","year":"1974","unstructured":"W. Beyer, M. Stein, T. Smith, and S. Ulam, A molecular sequence metric and evolutionary trees,Math. Biosci., 19:9\u201325, 1974.","journal-title":"Math. Biosci."},{"key":"BF01188585_CR4","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, M. Fellows, and T. Warnow, Two strikes against perfect phylogeny,Proceedings, International Congress on Automata and Language Processing (ICALP), Vienna, July 1992.","DOI":"10.1007\/3-540-55719-9_80"},{"key":"BF01188585_CR5","unstructured":"P. Buneman,Mathematics in the Archeological and Historical Sciences F. R. Hobson, D. G. Kendall, and P. Tautu, eds., University Press, Edinburgh, p. 387."},{"key":"BF01188585_CR6","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1111\/j.1558-5646.1967.tb03411.x","volume":"32","author":"L. Cavalli-Sforza","year":"1967","unstructured":"L. Cavalli-Sforza and A. Edwards, Phylogenetic analysis models and estimation procedures,Evolution, 32:550\u2013570, 1967.","journal-title":"Evolution"},{"key":"BF01188585_CR7","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"1990","unstructured":"T. Cormen, C. Leiserson, and R. Rivest,Introduction to Algorithms, MIT Press, Cambridge, MA, 1990."},{"key":"BF01188585_CR8","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(89)90216-0","volume":"30","author":"J. Culberson","year":"1989","unstructured":"J. Culberson and P. Rudnicki, A fast algorithm for constructing trees from distance matrices,Inform. Process. Lett., 30:215\u2013220, 1989.","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"BF01188585_CR9","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF02458863","volume":"49","author":"W. H. E. Day","year":"1987","unstructured":"W. H. E. Day, Computational complexity of inferring phylogenies from dissimilarity matrices,Bull, of Math. Biol., 49(4):461\u2013467, 1987.","journal-title":"Bull, of Math. Biol."},{"key":"BF01188585_CR10","unstructured":"M. Dayhoff and R. Eck,Atlas of Protein Sequence and Structure 1967\u201368, National Biomedical Research Foundation, Silver Spring, MD."},{"key":"BF01188585_CR11","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1086\/282802","volume":"106","author":"J. S. Farris","year":"1972","unstructured":"J. S. Farris, Estimating phylogenetic trees from distance matrices,Amer. Natur., 106:645\u2013668, 1972.","journal-title":"Amer. Natur."},{"key":"BF01188585_CR12","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1146\/annurev.ge.22.120188.002513","volume":"22","author":"J. Felsenstein","year":"1988","unstructured":"J. Felsenstein, Phylogenies from molecular sequences: inference and reliability,Annual Rev. Genet., 22:521\u2013565, 1988.","journal-title":"Annual Rev. Genet."},{"key":"BF01188585_CR13","first-page":"29","volume":"155","author":"W. M. Fitch","year":"1976","unstructured":"W. M. Fitch and E. Margoliash, The construction of phylogenetic trees,Science, 155:29\u201394, 1976.","journal-title":"Science"},{"key":"BF01188585_CR14","volume-title":"Computers and Intractability","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability, Freeman, New York, 1979."},{"key":"BF01188585_CR15","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1126\/science.1604319","volume":"256","author":"G. H. Gonnet","year":"1992","unstructured":"G. H. Gonnet, M. A. Cohen, and S. A. Benner, Exhaustive matching of the entire protein sequence database,Science, 256:1443\u20131445, 1992.","journal-title":"Science"},{"issue":"2","key":"BF01188585_CR16","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"D. Harel and R. Tarjan, Fast algorithm for finding nearest common ancestors,SIAM J. Comput., 13(2):338\u2013355, 1984.","journal-title":"SIAM J. Comput."},{"key":"BF01188585_CR17","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0025-5564(67)90032-6","volume":"1","author":"C. J. Jardine","year":"1967","unstructured":"C. J. Jardine, N. Jardine, and R. Sibson, The structure and construction of taxonomic hierarchies, Math. Biosci., 1:173\u2013179, 1967.","journal-title":"Math. Biosci."},{"key":"BF01188585_CR18","unstructured":"S. Kannan, E. Lawler, and T. Warnow, Determining the evolutionary tree,Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 475\u2013484, San Francisco, CA, Jan. 1990."},{"issue":"5","key":"BF01188585_CR19","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0020-0190(88)90090-7","volume":"27","author":"M. K\u0159ivanek","year":"1988","unstructured":"M. K\u0159ivanek, The complexity of ultrametric partitions on graphs,Inform. Process. Lett., 27(5):265\u2013270, 1988.","journal-title":"Inform. Process. Lett."},{"key":"BF01188585_CR20","doi-asserted-by":"crossref","unstructured":"W.-H. Li, Simple method for constructing phylogenetic trees from distance matrices,Proc. Nat. Acad. Sci. USA, 78:1085\u201389.","DOI":"10.1073\/pnas.78.2.1085"},{"key":"BF01188585_CR21","unstructured":"C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, Manuscript."},{"issue":"2","key":"BF01188585_CR22","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF02459948","volume":"50","author":"W. Miller","year":"1988","unstructured":"W. Miller and E. W. Myers, Sequence comparison with concave weighting functions,Bull. Math. Biol., 50(2):97\u2013120, 1988.","journal-title":"Bull. Math. Biol."},{"key":"BF01188585_CR23","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:406\u201325, 1987.","journal-title":"Mol. Biol Evol."},{"key":"BF01188585_CR24","volume-title":"Numerical Taxonomy","author":"R. Sokal","year":"1963","unstructured":"R. Sokal and P. Sneath,Numerical Taxonomy, Freeman, San Francisco, CA, 1963."},{"key":"BF01188585_CR25","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M. A. Steel","year":"1992","unstructured":"M. A. Steel, The complexity of reconstructing trees from qualitative characters and subtrees,J. Classification, 9:91\u2013116, 1992.","journal-title":"J. Classification"},{"key":"BF01188585_CR26","unstructured":"E. Sweedyk and T. Warnow, The optimal tree alignment problem is hard, Manuscript."},{"issue":"1","key":"BF01188585_CR27","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/0020-0190(82)90137-5","volume":"14","author":"R. E. Tarjan","year":"1982","unstructured":"R. E. Tarjan, Sensitivity analysis of minimum spanning trees and shortest path trees,Inform. Process. Lett., 14(1):30\u201333, 1982.","journal-title":"Inform. Process. Lett."},{"key":"BF01188585_CR28","doi-asserted-by":"crossref","unstructured":"Y. Tateno, M. Nei, and F. Tajima, Accuracy of estimated phylogenetic trees from molecular data. I: Distantly related trees,J. Mol. Evol., 18:387\u2013404.","DOI":"10.1007\/BF01840887"},{"key":"BF01188585_CR29","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0022-5193(77)90351-4","volume":"64","author":"M. S. Waterman","year":"1977","unstructured":"M. S. Waterman, T. F. Smith, M. Singh, and W. A. Beyer, Additive evolutionary trees,J. Theoret. Biol., 64:199\u2013213, 1977.","journal-title":"J. Theoret. Biol."},{"key":"BF01188585_CR30","first-page":"434","volume":"2","author":"W. J. Wilbur","year":"1985","unstructured":"W. J. Wilbur, On the PAM matrix model of protein evolution,Mol Biol. Evol, 2:434\u2013447, 1985.","journal-title":"Mol Biol. Evol"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188585.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01188585\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T16:41:45Z","timestamp":1556728905000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01188585"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,2]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1995,2]]}},"alternative-id":["BF01188585"],"URL":"https:\/\/doi.org\/10.1007\/bf01188585","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,2]]}}}