{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T15:49:02Z","timestamp":1779896942010,"version":"3.53.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,4,13]],"date-time":"2020-04-13T00:00:00Z","timestamp":1586736000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2020,4,13]],"date-time":"2020-04-13T00:00:00Z","timestamp":1586736000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS 1553421"],"award-info":[{"award-number":["IIS 1553421"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["MCB 1616514"],"award-info":[{"award-number":["MCB 1616514"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n<jats:title>Background<\/jats:title>\n<jats:p>We consider two fundamental computational problems that arise when comparing phylogenetic trees, rooted or unrooted, with non-identical leaf sets. The first problem arises when comparing two trees where the leaf set of one tree is a proper subset of the other. The second problem arises when the two trees to be compared have only partially overlapping leaf sets. The traditional approach to handling these problems is to first restrict the two trees to their common leaf set. An alternative approach that has shown promise is to first <jats:italic>complete<\/jats:italic> the trees by adding missing leaves, so that the resulting trees have identical leaf sets. This requires the computation of an optimal completion that minimizes the distance between the two resulting trees over all possible completions.<\/jats:p>\n<\/jats:sec><jats:sec>\n<jats:title>Results<\/jats:title>\n<jats:p>We provide optimal linear-time algorithms for both completion problems under the widely-used Robinson\u2013Foulds (RF) distance measure. Our algorithm for the first problem improves the time complexity of the current fastest algorithm from quadratic (in the size of the two trees) to linear. No algorithms have yet been proposed for the more general second problem where both trees have missing leaves. We advance the study of this general problem by proposing a useful restricted version of the general problem and providing optimal linear-time algorithms for the restricted version. Our experimental results on biological data sets suggest that completion-based RF distances can be very different compared to traditional RF distances.<\/jats:p>\n<\/jats:sec>","DOI":"10.1186\/s13015-020-00166-1","type":"journal-article","created":{"date-parts":[[2020,4,13]],"date-time":"2020-04-13T18:02:21Z","timestamp":1586800941000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Linear-time algorithms for phylogenetic tree completion under Robinson\u2013Foulds distance"],"prefix":"10.1186","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0039-2596","authenticated-orcid":false,"given":"Mukul S.","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,13]]},"reference":[{"issue":"1","key":"166_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"DF Robinson","year":"1981","unstructured":"Robinson DF, Foulds LR. Comparison of phylogenetic trees. Math Biosci. 1981;53(1):131\u201347.","journal-title":"Math Biosci"},{"issue":"3","key":"166_CR2","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1093\/sysbio\/45.3.323","volume":"45","author":"DE Critchlow","year":"1996","unstructured":"Critchlow DE, Pearl DK, Qian C, Faith D. The triples distance for rooted bifurcating phylogenetic trees. Syst Biol. 1996;45(3):323\u201334. https:\/\/doi.org\/10.1093\/sysbio\/45.3.323.","journal-title":"Syst Biol"},{"key":"166_CR3","doi-asserted-by":"crossref","unstructured":"Estabrook GF, McMorris FR, Meacham CA. Comparison of undirected phylogenetic trees based on subtrees of four evolutionary units. Syst Zool. 1985;34(2):193\u2013200. http:\/\/www.jstor.org\/stable\/2413326.","DOI":"10.2307\/sysbio\/34.2.193"},{"issue":"4","key":"166_CR4","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/0022-5193(78)90137-6","volume":"73","author":"MS Waterman","year":"1978","unstructured":"Waterman MS, Smith TF. On the similarity of dendrograms. J Theor Biol. 1978;73(4):789\u2013800.","journal-title":"J Theor Biol"},{"key":"166_CR5","volume-title":"Inferring phylogenies","author":"J Felsenstein","year":"2003","unstructured":"Felsenstein J. Inferring phylogenies. Sunderland: Sinauer Assoc; 2003."},{"issue":"2","key":"166_CR6","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1093\/bioinformatics\/btn606","volume":"25","author":"Y Wu","year":"2009","unstructured":"Wu Y. A practical method for exact computation of subtree prune and regraft distance. Bioinformatics. 2009;25(2):190\u20136. https:\/\/doi.org\/10.1093\/bioinformatics\/btn606.","journal-title":"Bioinformatics"},{"issue":"1","key":"166_CR7","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01908078","volume":"2","author":"CR Finden","year":"1985","unstructured":"Finden CR, Gordon AD. Obtaining common pruned trees. J Classif. 1985;2(1):255\u201376. https:\/\/doi.org\/10.1007\/BF01908078.","journal-title":"J Classif"},{"issue":"6","key":"166_CR8","doi-asserted-by":"publisher","first-page":"1656","DOI":"10.1137\/S0097539794269461","volume":"26","author":"A Amir","year":"1997","unstructured":"Amir A, Keselman D. Maximum agreement subtree in a set of evolutionary trees: metrics and efficient algorithms. SIAM J Comput. 1997;26(6):1656\u201369. https:\/\/doi.org\/10.1137\/S0097539794269461.","journal-title":"SIAM J Comput"},{"issue":"23","key":"166_CR9","doi-asserted-by":"publisher","first-page":"3119","DOI":"10.1093\/bioinformatics\/btm500","volume":"23","author":"DM de Vienne","year":"2007","unstructured":"de Vienne DM, Giraud T, Martin OC. A congruence index for testing topological similarity between trees. Bioinformatics. 2007;23(23):3119\u201324. https:\/\/doi.org\/10.1093\/bioinformatics\/btm500.","journal-title":"Bioinformatics"},{"issue":"2","key":"166_CR10","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00285-009-0295-2","volume":"61","author":"G Cardona","year":"2010","unstructured":"Cardona G, Llabr\u00e9s M, Rossell\u00f3 F, Valiente G. Nodal distances for rooted phylogenetic trees. J Math Biol. 2010;61(2):253\u201376. https:\/\/doi.org\/10.1007\/s00285-009-0295-2.","journal-title":"J Math Biol"},{"issue":"6","key":"166_CR11","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1089\/cmb.2008.0068","volume":"15","author":"A Kupczok","year":"2008","unstructured":"Kupczok A, Haeseler AV, Klaere S. An exact algorithm for the geodesic distance between phylogenetic trees. J Comput Biol. 2008;15(6):577\u201391.","journal-title":"J Comput Biol"},{"issue":"1","key":"166_CR12","doi-asserted-by":"publisher","first-page":"S8","DOI":"10.1186\/1471-2105-10-S1-S8","volume":"10","author":"HT Lin","year":"2009","unstructured":"Lin HT, Burleigh JG, Eulenstein O. Triplet supertree heuristics for the tree of life. BMC Bioinf. 2009;10(1):S8. https:\/\/doi.org\/10.1186\/1471-2105-10-S1-S8.","journal-title":"BMC Bioinf"},{"issue":"1","key":"166_CR13","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1186\/1748-7188-5-18","volume":"5","author":"MS Bansal","year":"2010","unstructured":"Bansal MS, Burleigh JG, Eulenstein O, Fern\u00e1ndez-Baca D. Robinson\u2013Foulds supertrees. Algorith Mol Biol. 2010;5(1):18.","journal-title":"Algorith Mol Biol"},{"issue":"4","key":"166_CR14","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1109\/TCBB.2012.47","volume":"9","author":"R Chaudhary","year":"2012","unstructured":"Chaudhary R, Burleigh JG, Fernandez-Baca D. Fast local search for unrooted Robinson\u2013Foulds supertrees. IEEE\/ACM Trans Comput Biol Bioinf. 2012;9(4):1004\u201313.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"4","key":"166_CR15","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1093\/sysbio\/syu023","volume":"63","author":"C Whidden","year":"2014","unstructured":"Whidden C, Zeh N, Beiko RG. Supertrees based on the subtree Prune-and-Regraft distance. Syst Biol. 2014;63(4):566\u201381. https:\/\/doi.org\/10.1093\/sysbio\/syu023.","journal-title":"Syst Biol"},{"key":"166_CR16","doi-asserted-by":"crossref","unstructured":"Akanni WA, Wilkinson M, Creevey CJ, Foster PG, Pisani D. Implementing and testing Bayesian and maximum-likelihood supertree methods in phylogenetics. R Soc Open Sci. 2015;2:8. http:\/\/rsos.royalsocietypublishing.org\/content\/2\/8\/140436.","DOI":"10.1098\/rsos.140436"},{"key":"166_CR17","unstructured":"Piel WH, Donoghue M, Sanderson M, Netherlands L. TreeBASE: a database of phylogenetic information. In: Proceedings of the 2nd international workshop of species 2000."},{"key":"166_CR18","first-page":"1","volume":"2005","author":"JT Wang","year":"2007","unstructured":"Wang JT, Shan H, Shasha D, Piel WH. Fast structural search in phylogenetic databases. Evol Bioinf. 2007;2005:1.","journal-title":"Evol Bioinf"},{"issue":"1","key":"166_CR19","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1186\/1471-2148-8-90","volume":"8","author":"D Chen","year":"2008","unstructured":"Chen D, Burleigh JG, Bansal MS, Fern\u00e1ndez-Baca D. PhyloFinder: an intelligent search engine for phylogenetic tree databases. BMC Evol Biol. 2008;8(1):90.","journal-title":"BMC Evol Biol"},{"issue":"2","key":"166_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0117987","volume":"10","author":"MM McMahon","year":"2015","unstructured":"McMahon MM, Deepak A, Fern\u00e1ndez-Baca D, Boss D, Sanderson MJ. STBase: one million species trees for comparative biology. PLOS ONE. 2015;10(2):1\u201317. https:\/\/doi.org\/10.1371\/journal.pone.0117987 02.","journal-title":"PLOS ONE"},{"key":"166_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-017-2456-9","author":"R Yoshida","year":"2017","unstructured":"Yoshida R, Fukumizu K, Vogiatzis C. Multilocus phylogenetic analysis with gene tree clustering. Ann Oper Res. 2017;. https:\/\/doi.org\/10.1007\/s10479-017-2456-9.","journal-title":"Ann Oper Res"},{"issue":"3","key":"166_CR22","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1080\/10635150701416682","volume":"56","author":"JA Cotton","year":"2007","unstructured":"Cotton JA, Wilkinson M, Steel M. Majority-rule supertrees. Syst Biol. 2007;56(3):445\u201352. https:\/\/doi.org\/10.1080\/10635150701416682.","journal-title":"Syst Biol"},{"issue":"1","key":"166_CR23","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1186\/1748-7188-5-2","volume":"5","author":"J Dong","year":"2010","unstructured":"Dong J, Fern\u00e1ndez-Baca D, McMorris F. Constructing majority-rule supertrees. Algorith Mol Biol. 2010;5(1):2. https:\/\/doi.org\/10.1186\/1748-7188-5-2.","journal-title":"Algorith Mol Biol"},{"issue":"17","key":"166_CR24","doi-asserted-by":"publisher","first-page":"2038","DOI":"10.1016\/j.dam.2011.07.002","volume":"159","author":"J Dong","year":"2011","unstructured":"Dong J, Fern\u00e1ndez-Baca D, McMorris FR, Powers RC. An axiomatic study of Majority-rule(+) and associated consensus functions on hierarchies. Discrete Appl Math. 2011;159(17):2038\u201344.","journal-title":"Discrete Appl Math"},{"issue":"1","key":"166_CR25","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1186\/1471-2148-11-205","volume":"11","author":"A Kupczok","year":"2011","unstructured":"Kupczok A. Split-based computation of majority-rule supertrees. BMC Evol Biol. 2011;11(1):205. https:\/\/doi.org\/10.1186\/1471-2148-11-205.","journal-title":"BMC Evol Biol"},{"issue":"5","key":"166_CR26","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1093\/bioinformatics\/btw600","volume":"33","author":"P Vachaspati","year":"2017","unstructured":"Vachaspati P, Warnow T. FastRFS: fast and accurate Robinson\u2013Foulds supertrees using constrained exact optimization. Bioinformatics. 2017;33(5):631\u20139. https:\/\/doi.org\/10.1093\/bioinformatics\/btw600.","journal-title":"Bioinformatics"},{"issue":"3","key":"166_CR27","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1093\/sysbio\/syp032","volume":"58","author":"J Dong","year":"2009","unstructured":"Dong J, Fernandez-Baca D. Properties of Majority-rule supertrees. Syst Biol. 2009;58(3):360\u20137. https:\/\/doi.org\/10.1093\/sysbio\/syp032.","journal-title":"Syst Biol"},{"key":"166_CR28","unstructured":"Christensen S, Molloy EK, Vachaspati P, Warnow T. Optimal Completion of Incomplete Gene Trees in Polynomial Time Using OCTAL. In: Schwartz R, Reinert K, editors. In: 17th international workshop on algorithms in bioinformatics (WABI 2017). vol.\u00a088 of Leibniz international proceedings in informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik; 2017. p. 27:1\u201327:14."},{"issue":"2","key":"166_CR29","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"JL Carter","year":"1979","unstructured":"Carter JL, Wegman MN. Universal classes of hash functions. Journal of Computer and System Sciences. 1979;18(2):143\u201354.","journal-title":"Journal of Computer and System Sciences."},{"issue":"4","key":"166_CR30","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M Dietzfelbinger","year":"1994","unstructured":"Dietzfelbinger M, Karlin A, Mehlhorn K, auf\u00a0der Heide FM, Rohnert H, Tarjan RE. Dynamic perfect hashing: upper and lower bounds. SIAM J Comput. 1994;23(4):738\u201361.","journal-title":"SIAM J Comput"},{"issue":"2","key":"166_CR31","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"MA Bender","year":"2005","unstructured":"Bender MA, Farach-Colton M, Pemmasani G, Skiena S, Sumazin P. Lowest common ancestors in trees and directed acyclic graphs. J Algorith. 2005;57(2):75\u201394.","journal-title":"J Algorith"},{"key":"166_CR32","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1017\/S0952836904005539","volume":"264","author":"M Cardillo","year":"2004","unstructured":"Cardillo M, Bininda-Emonds ORP, Boakes E, Purvis A. A species-level phylogenetic supertree of marsupials. J Zool. 2004;264:11\u201331.","journal-title":"J Zool"},{"issue":"1","key":"166_CR33","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1186\/1471-2148-6-93","volume":"6","author":"R Beck","year":"2006","unstructured":"Beck R, Bininda-Emonds O, Cardillo M, Liu FG, Purvis A. A higher-level MRP supertree of placental mammals. BMC Evol Biol. 2006;6(1):93.","journal-title":"BMC Evol Biol"},{"key":"166_CR34","first-page":"277","volume-title":"Advances in legume systematics","author":"MF Wojciechowski","year":"2000","unstructured":"Wojciechowski MF, Sanderson MJ, Steele KP, Liston A. Molecular phylogeny of the \u201cTemperate Herbaceous Tribes\u201d of Papilionoid legumes: a supertree approach. In: Herendeen PS, Bruneau A, editors. Advances in legume systematics, vol. 9. Kew: Royal Botanic Gardens; 2000. p. 277\u201398."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00166-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-020-00166-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-020-00166-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T23:08:01Z","timestamp":1618268881000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-020-00166-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,13]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["166"],"URL":"https:\/\/doi.org\/10.1186\/s13015-020-00166-1","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,13]]},"assertion":[{"value":"23 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"6"}}