{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T15:47:26Z","timestamp":1779896846495,"version":"3.53.1"},"reference-count":40,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T00:00:00Z","timestamp":1719187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada\u2014Discovery Grants","doi-asserted-by":"publisher","award":["RGPIN-2022-04322"],"award-info":[{"award-number":["RGPIN-2022-04322"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada\u2014Discovery Grants","doi-asserted-by":"publisher","award":["CGS D-589644-2024"],"award-info":[{"award-number":["CGS D-589644-2024"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada\u2014Discovery Grants","doi-asserted-by":"publisher","award":["326911"],"award-info":[{"award-number":["326911"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Canada Graduate Scholarship-Doctoral","award":["RGPIN-2022-04322"],"award-info":[{"award-number":["RGPIN-2022-04322"]}]},{"name":"Canada Graduate Scholarship-Doctoral","award":["CGS D-589644-2024"],"award-info":[{"award-number":["CGS D-589644-2024"]}]},{"name":"Canada Graduate Scholarship-Doctoral","award":["326911"],"award-info":[{"award-number":["326911"]}]},{"name":"Fonds de recherche du Qu\u00e9bec-Nature and technologies","award":["RGPIN-2022-04322"],"award-info":[{"award-number":["RGPIN-2022-04322"]}]},{"name":"Fonds de recherche du Qu\u00e9bec-Nature and technologies","award":["CGS D-589644-2024"],"award-info":[{"award-number":["CGS D-589644-2024"]}]},{"name":"Fonds de recherche du Qu\u00e9bec-Nature and technologies","award":["326911"],"award-info":[{"award-number":["326911"]}]},{"name":"University of Sherbrooke grant","award":["RGPIN-2022-04322"],"award-info":[{"award-number":["RGPIN-2022-04322"]}]},{"name":"University of Sherbrooke grant","award":["CGS D-589644-2024"],"award-info":[{"award-number":["CGS D-589644-2024"]}]},{"name":"University of Sherbrooke grant","award":["326911"],"award-info":[{"award-number":["326911"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Comparing phylogenetic trees is a prominent problem widely used in applications such as clustering and building the Tree of Life. While there are many well-developed distance measures for phylogenetic trees defined on the same set of taxa, the situation is contrasting for trees defined on different but mutually overlapping sets of taxa. This paper presents a new polynomial-time algorithm for completing phylogenetic trees and computing the distance between trees defined on different but overlapping sets of taxa. This novel approach considers both the branch lengths and the topology of the phylogenetic trees being compared. We demonstrate that the distance measure applied to completed trees is a metric and provide several properties of the new method, including its symmetrical nature in tree completion.<\/jats:p>","DOI":"10.3390\/sym16070790","type":"journal-article","created":{"date-parts":[[2024,6,24]],"date-time":"2024-06-24T10:41:12Z","timestamp":1719225672000},"page":"790","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Novel Algorithm for Comparing Phylogenetic Trees with Different but Overlapping Taxa"],"prefix":"10.3390","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3630-2911","authenticated-orcid":false,"given":"Aleksandr","family":"Koshkarov","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Sherbrooke, Sherbrooke, QC J1K 2R1, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1818-208X","authenticated-orcid":false,"given":"Nadia","family":"Tahiri","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Sherbrooke, Sherbrooke, QC J1K 2R1, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,6,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","article-title":"Comparison of phylogenetic trees","volume":"53","author":"Robinson","year":"1981","journal-title":"Math. Biosci."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Briand, S., Dessimoz, C., El-Mabrouk, N., Lafond, M., and Lobinska, G. (2020). A generalized Robinson-Foulds distance for labeled trees. BMC Genom., 21.","DOI":"10.1186\/s12864-020-07011-0"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"5007","DOI":"10.1093\/bioinformatics\/btaa614","article-title":"Information theoretic generalized Robinson\u2013Foulds metrics for comparing phylogenetic trees","volume":"36","author":"Smith","year":"2020","journal-title":"Bioinformatics"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1181","DOI":"10.1089\/cmb.2021.0342","article-title":"The Generalized Robinson-Foulds Distance for Phylogenetic Trees","volume":"28","author":"Valiente","year":"2021","journal-title":"J. Comput. Biol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1093\/sysbio\/45.3.323","article-title":"The triples distance for rooted bifurcating phylogenetic trees","volume":"45","author":"Critchlow","year":"1996","journal-title":"Syst. Biol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"193","DOI":"10.2307\/2413326","article-title":"Comparison of undirected phylogenetic trees based on subtrees of four evolutionary units","volume":"34","author":"Estabrook","year":"1985","journal-title":"Syst. Zool."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1002\/jgt.22776","article-title":"On the quartet distance given partial information","volume":"100","author":"Snir","year":"2022","journal-title":"J. Graph Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s00285-009-0295-2","article-title":"Nodal distances for rooted phylogenetic trees","volume":"61","author":"Cardona","year":"2010","journal-title":"J. Math. Biol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1089\/cmb.2008.0068","article-title":"An exact algorithm for the geodesic distance between phylogenetic trees","volume":"15","author":"Kupczok","year":"2008","journal-title":"J. Comput. Biol."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Khodaei, M., Owen, M., and Beerli, P. (2023). Geodesics to characterize the phylogenetic landscape. PLoS ONE, 18.","DOI":"10.1371\/journal.pone.0287350"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1656","DOI":"10.1137\/S0097539794269461","article-title":"Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms","volume":"26","author":"Amir","year":"1997","journal-title":"SIAM J. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1016\/j.dam.2020.07.007","article-title":"On the extremal maximum agreement subtree problem","volume":"285","author":"Markin","year":"2020","journal-title":"Discret. Appl. Math."},{"key":"ref_13","first-page":"126","article-title":"Distributions of tree comparison metrics\u2014Some new results","volume":"42","author":"Steel","year":"1993","journal-title":"Syst. Biol."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1255","DOI":"10.1093\/sysbio\/syab100","article-title":"Robust analysis of phylogenetic tree space","volume":"71","author":"Smith","year":"2022","journal-title":"Syst. Biol."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Tahiri, N., Willems, M., and Makarenkov, V. (2018). A new fast method for inferring multiple consensus trees using k-medoids. BMC Evol. Biol., 18.","DOI":"10.1186\/s12862-018-1163-8"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"3367","DOI":"10.1093\/bioinformatics\/btac326","article-title":"Building alternative consensus trees and supertrees using k-means and Robinson and Foulds distance","volume":"38","author":"Tahiri","year":"2022","journal-title":"Bioinformatics"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1282","DOI":"10.1093\/sysbio\/syab015","article-title":"On defining and finding islands of trees and mitigating large island bias","volume":"70","author":"Silva","year":"2021","journal-title":"Syst. Biol."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1093\/sysbio\/syu023","article-title":"Supertrees based on the subtree prune-and-regraft distance","volume":"63","author":"Whidden","year":"2014","journal-title":"Syst. Biol."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Makarenkov, V., Barseghyan, G.S., and Tahiri, N. (2023). Inferring multiple consensus trees and supertrees using clustering: A review. Data Analysis and Optimization: In Honor of Boris Mirkin\u2019s 80th Birthday, Springer.","DOI":"10.1007\/978-3-031-31654-8_13"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"12764","DOI":"10.1073\/pnas.1423041112","article-title":"Synthesis of phylogeny and taxonomy into a comprehensive tree of life","volume":"112","author":"Hinchliff","year":"2015","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Letunic, I., and Bork, P. (2024). Interactive Tree of Life (iTOL) v6: Recent updates to the phylogenetic tree display and annotation tool. Nucleic Acids Res., gkae268.","DOI":"10.1093\/nar\/gkae268"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Wang, J.T., Shan, H., Shasha, D., and Piel, W.H. (2005). Fast structural search in phylogenetic databases. Evol. Bioinform., 1.","DOI":"10.1177\/117693430500100009"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Chen, D., Burleigh, J.G., Bansal, M.S., and Fern\u00e1ndez-Baca, D. (2008). PhyloFinder: An intelligent search engine for phylogenetic tree databases. BMC Evol. Biol., 8.","DOI":"10.1186\/1471-2148-8-90"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1080\/10635150701416682","article-title":"Majority-rule supertrees","volume":"56","author":"Cotton","year":"2007","journal-title":"Syst. Biol."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Christensen, S., Molloy, E.K., Vachaspati, P., and Warnow, T. (2018). OCTAL: Optimal Completion of gene trees in polynomial time. Algorithms Mol. Biol., 13.","DOI":"10.1186\/s13015-018-0124-5"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Kupczok, A. (2011). Split-based computation of majority-rule supertrees. BMC Evol. Biol., 11.","DOI":"10.1186\/1471-2148-11-205"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1093\/sysbio\/syp032","article-title":"Properties of majority-rule supertrees","volume":"58","author":"Dong","year":"2009","journal-title":"Syst. Biol."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Bansal, M.S. (2020). Linear-time algorithms for phylogenetic tree completion under Robinson\u2013Foulds distance. Algorithms Mol. Biol., 15.","DOI":"10.1186\/s13015-020-00166-1"},{"key":"ref_29","unstructured":"Yao, K., and Bansal, M.S. (2021, January 5\u20137). Optimal completion and comparison of incomplete phylogenetic trees under robinson-foulds distance. Proceedings of the 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), Wroc\u0142aw, Poland."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"5256","DOI":"10.1038\/s41598-022-08360-4","article-title":"A vectorial tree distance measure","volume":"12","author":"Priel","year":"2022","journal-title":"Sci. Rep."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1006\/aama.2001.0759","article-title":"Geometry of the space of phylogenetic trees","volume":"27","author":"Billera","year":"2001","journal-title":"Adv. Appl. Math."},{"key":"ref_32","unstructured":"Ren, Y., Zha, S., Bi, J., Sanchez, J.A., Monical, C., Delcourt, M., Guzman, R.K., and Davidson, R. (2017). A combinatorial method for connecting BHV spaces representing different numbers of taxa. arXiv."},{"key":"ref_33","unstructured":"Grindstaff, G., and Owen, M. (2018). Geometric comparison of phylogenetic trees with different leaf sets. arXiv."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1222","DOI":"10.1109\/TCBB.2018.2884459","article-title":"imPhy: Imputing phylogenetic trees with missing information using mathematical programming","volume":"17","author":"Yasui","year":"2018","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Yoshida, R. (2023). Imputing phylogenetic trees using tropical polytopes over the space of phylogenetic trees. Mathematics, 11.","DOI":"10.3390\/math11153419"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1093\/sysbio\/syz045","article-title":"INSTRAL: Discordance-aware phylogenetic placement using quartet scores","volume":"69","author":"Rabiee","year":"2020","journal-title":"Syst. Biol."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1532","DOI":"10.1093\/bioinformatics\/btab875","article-title":"Completing gene trees without species trees in sub-quadratic time","volume":"38","author":"Mai","year":"2022","journal-title":"Bioinformatics"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1156","DOI":"10.1089\/cmb.2022.0212","article-title":"Quartet Based Gene Tree Imputation Using Deep Learning Improves Phylogenomic Analyses Despite Missing Data","volume":"29","author":"Mahbub","year":"2022","journal-title":"J. Comput. Biol."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"212","DOI":"10.5220\/0011697100003414","article-title":"GPTree: Generator of Phylogenetic Trees with Overlapping and Biological Events for Supertree Inference","volume":"Volume 3: BIOINFORMATICS","author":"Koshkarov","year":"2023","journal-title":"Proceedings of the 16th International Joint Conference on Biomedical Engineering Systems and Technologies (BIOSTEC 2023)"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Koshkarov, A., and Tahiri, N. (2023). GPTree Cluster: Phylogenetic tree cluster generator in the context of supertree inference. Bioinform. Adv., 3.","DOI":"10.1093\/bioadv\/vbad023"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/16\/7\/790\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:03:23Z","timestamp":1760108603000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/16\/7\/790"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,24]]},"references-count":40,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2024,7]]}},"alternative-id":["sym16070790"],"URL":"https:\/\/doi.org\/10.3390\/sym16070790","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,24]]}}}