{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T18:35:51Z","timestamp":1777574151822,"version":"3.51.4"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"S10","license":[{"start":{"date-parts":[[2020,11,1]],"date-time":"2020-11-01T00:00:00Z","timestamp":1604188800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T00:00:00Z","timestamp":1605657600000},"content-version":"vor","delay-in-days":17,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Genomics"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>The Robinson-Foulds (RF) distance is a well-established measure between phylogenetic trees. Despite a lack of biological justification, it has the advantages of being a proper metric and being computable in linear time. For phylogenetic applications involving genes, however, a crucial aspect of the trees ignored by the RF metric is the type of the branching event (e.g. speciation, duplication, transfer, etc).<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We extend RF to trees with labeled internal nodes by including a node<jats:italic>flip<\/jats:italic>operation, alongside edge contractions and extensions. We explore properties of this extended RF distance in the case of a binary labeling. In particular, we show that contrary to the unlabeled case, an optimal edit path may require contracting \u201cgood\u201d edges, i.e. edges shared between the two trees.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusions<\/jats:title><jats:p>We provide a 2-approximation algorithm which is shown to perform well empirically. Looking ahead, computing distances between labeled trees opens up a variety of new algorithmic directions.Implementation and simulations available at<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/DessimozLab\/pylabeledrf\">https:\/\/github.com\/DessimozLab\/pylabeledrf<\/jats:ext-link>.<\/jats:p><\/jats:sec>","DOI":"10.1186\/s12864-020-07011-0","type":"journal-article","created":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T18:03:41Z","timestamp":1605722621000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["A generalized Robinson-Foulds distance for labeled trees"],"prefix":"10.1186","volume":"21","author":[{"given":"Samuel","family":"Briand","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christophe","family":"Dessimoz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"El-Mabrouk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Lafond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriela","family":"Lobinska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,18]]},"reference":[{"key":"7011_CR1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics vol. 24","author":"C Semple","year":"2003","unstructured":"Semple C, Steel M, et al. Phylogenetics vol. 24. Oxford: Oxford University Press on Demand; 2003."},{"issue":"1","key":"7011_CR2","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1093\/sysbio\/syx046","volume":"67","author":"C Colijn","year":"2018","unstructured":"Colijn C, Plazzotta G. A metric on phylogenetic tree shapes. Syst Biol. 2018; 67(1):113\u201326.","journal-title":"Syst Biol"},{"key":"7011_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2018.08.006","volume":"760","author":"M Lafond","year":"2019","unstructured":"Lafond M, El-Mabrouk N, Huber KT, Moulton V. The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metric. Theor Comput Sci. 2019; 760:15\u201334.","journal-title":"Theor Comput Sci"},{"issue":"9","key":"7011_CR4","doi-asserted-by":"publisher","first-page":"3692","DOI":"10.1007\/s00453-019-00594-5","volume":"81","author":"D Bryant","year":"2019","unstructured":"Bryant D, Scornavacca C. An O(n logN) time algorithm for computing the path-length distance between trees. Algorithmica. 2019; 81(9):3692\u2013706.","journal-title":"Algorithmica"},{"issue":"2","key":"7011_CR5","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.","journal-title":"J Math Biol"},{"issue":"2","key":"7011_CR6","doi-asserted-by":"publisher","first-page":"193","DOI":"10.2307\/2413326","volume":"34","author":"GF Estabrook","year":"1985","unstructured":"Estabrook GF, McMorris F, Meacham CA. Comparison of undirected phylogenetic trees based on subtrees of four evolutionary units. Syst Zool. 1985; 34(2):193\u2013200.","journal-title":"Syst Zool"},{"issue":"3","key":"7011_CR7","first-page":"323","volume":"45","author":"DE Critchlow","year":"1996","unstructured":"Critchlow DE, Pearl DK, Qian C. The triples distance for rooted bifurcating phylogenetic trees. Syst Zool. 1996; 45(3):323\u201334.","journal-title":"Syst Zool"},{"key":"7011_CR8","volume-title":"Discrete Mathematical Problems with Medical Applications: DIMACS Workshop Discrete Mathematical Problems with Medical Applications, December 8-10, 1999, DIMACS Center, vol. 55","author":"BDXHT Jiang","year":"2000","unstructured":"Jiang BDXHT, Li M, Tromp J, Zhang L. On computing the nearest neighbor interchange distance. In: Discrete Mathematical Problems with Medical Applications: DIMACS Workshop Discrete Mathematical Problems with Medical Applications, December 8-10, 1999, DIMACS Center, vol. 55. Providence: American Mathematical Soc.: 2000. p. 125."},{"key":"7011_CR9","doi-asserted-by":"publisher","first-page":"419","DOI":"10.4137\/EBO.S419","volume":"4","author":"G Hickey","year":"2008","unstructured":"Hickey G, Dehne F, Rau-Chaplin A, Blouin C. Spr distance computation for unrooted trees. Evol Bioinforma. 2008; 4:419.","journal-title":"Evol Bioinforma"},{"issue":"1","key":"7011_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00026-001-8006-8","volume":"5","author":"BL Allen","year":"2001","unstructured":"Allen BL, Steel M. Subtree transfer operations and their induced metrics on evolutionary trees. Ann Comb. 2001; 5(1):1\u201315.","journal-title":"Ann Comb"},{"issue":"4","key":"7011_CR11","doi-asserted-by":"publisher","first-page":"1014","DOI":"10.1109\/TCBB.2011.157","volume":"9","author":"Y Lin","year":"2012","unstructured":"Lin Y, Rajan V, Moret BM. A metric for phylogenetic trees based on matching. IEEE\/ACM Trans Comput Biol Bioinforma (TCBB). 2012; 9(4):1014\u201322.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinforma (TCBB)"},{"key":"7011_CR12","first-page":"31","volume":"2","author":"S Mittal","year":"2015","unstructured":"Mittal S, Munjal G. Tree mining and tree validation metrics: A review. IOSR: J Comput Eng. 2015; 2:31\u201336.","journal-title":"IOSR: J Comput Eng"},{"issue":"1","key":"7011_CR13","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01908061","volume":"2","author":"WH Day","year":"1985","unstructured":"Day WH. Optimal algorithms for comparing trees with labeled leaves. J Classif. 1985; 2(1):7\u201328.","journal-title":"J Classif"},{"issue":"6","key":"7011_CR14","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1089\/cmb.2007.R012","volume":"14","author":"ND Pattengale","year":"2007","unstructured":"Pattengale ND, Gottlieb EJ, Moret BM. Efficiently computing the robinson-foulds metric. J Comput Biol. 2007; 14(6):724\u201335.","journal-title":"J Comput Biol"},{"issue":"2","key":"7011_CR15","first-page":"126","volume":"42","author":"MA Steel","year":"1993","unstructured":"Steel MA, Penny D. Distributions of tree comparison metric\u2013some new results. Syst Biol. 1993; 42(2):126\u201341.","journal-title":"Syst Biol"},{"issue":"3","key":"7011_CR16","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1109\/TCBB.2009.32","volume":"6","author":"D Bryant","year":"2009","unstructured":"Bryant D, Steel M. Computing the distribution of a tree metric. IEEE\/ACM Trans Comput Biol Bioinforma. 2009; 6(3):420\u20136.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinforma"},{"issue":"4","key":"7011_CR17","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-foulds supertrees. IEEE\/ACM Trans Comput Biol Bioinforma (TCBB). 2012; 9(4):1004\u201313.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinforma (TCBB)"},{"key":"7011_CR18","doi-asserted-by":"publisher","unstructured":"Moon J, Eulenstein O. Cluster matching distance for rooted phylogenetic trees. In: International Symposium on Bioinformatics Research and Applications. Springer: 2018. p. 321\u201332. https:\/\/doi.org\/10.1007\/978-3-319-94968-0_31.","DOI":"10.1007\/978-3-319-94968-0_31"},{"issue":"1-2","key":"7011_CR19","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-2):131\u201347.","journal-title":"Math Biosci"},{"issue":"3","key":"7011_CR20","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(92)90136-J","volume":"42","author":"K Zhang","year":"1992","unstructured":"Zhang K, Statman R, Shasha D. On the editing distance between unordered labeled trees. Inf Process Lett. 1992; 42(3):133\u20139.","journal-title":"Inf Process Lett"},{"key":"7011_CR21","volume-title":"Annual Symposium on Combinatorial Pattern Matching","author":"K Zhang","year":"1993","unstructured":"Zhang K. A new editing based distance between unordered labeled trees. In: Annual Symposium on Combinatorial Pattern Matching. Berlin: Springer: 1993. p. 254\u201365."},{"issue":"3","key":"7011_CR22","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF01975866","volume":"15","author":"K Zhang","year":"1996","unstructured":"Zhang K. A constrained edit distance between unordered labeled trees. Algorithmica. 1996; 15(3):205\u201322.","journal-title":"Algorithmica"},{"key":"7011_CR23","doi-asserted-by":"publisher","unstructured":"Schwarz S, Pawlik M, Augsten N. A new perspective on the tree edit distance. In: International Conference on Similarity Search and Applications. Springer: 2017. p. 156\u201370. https:\/\/doi.org\/10.1007\/978-3-319-68474-1_11.","DOI":"10.1007\/978-3-319-68474-1_11"},{"key":"7011_CR24","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1101\/gr.073585.107","volume":"19","author":"AJ Vilella","year":"2009","unstructured":"Vilella AJ, Severin J, Ureta-Vidal A, Heng L, Durbin R, Birney E. EnsemblCompara gene trees: Complete, duplication-aware phylogenetic trees in vertebrates. Genome Res. 2009; 19:327\u201335.","journal-title":"Genome Res"},{"issue":"D1","key":"7011_CR25","doi-asserted-by":"publisher","first-page":"D922","DOI":"10.1093\/nar\/gkt1055","volume":"42","author":"F Schreiber","year":"2013","unstructured":"Schreiber F, Patricio M, Muffato M, Pignatelli M, Bateman A. Treefam v9: a new website, more species and orthology-on-the-fly. Nucleic Acids Res. 2013; 42(D1):D922\u2013D925. https:\/\/doi.org\/10.1093\/nar\/gkt1055.","journal-title":"Nucleic Acids Res"},{"key":"7011_CR26","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1090\/dimacs\/037\/19","volume":"37","author":"A Dress","year":"1997","unstructured":"Dress A. Towards a theory of holistic clustering. DIMACS Ser Discrete Math Theoret Comput Sci. 1997; 37:271\u201389.","journal-title":"DIMACS Ser Discrete Math Theoret Comput Sci"},{"key":"7011_CR27","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1186\/1471-2105-13-S19-S6","volume":"13","author":"M Hernandez-Rosales","year":"2012","unstructured":"Hernandez-Rosales M, Hellmuth M, Wieseke N, Huber KT, Moulton V, Stadler PF. From event-labeled gene trees to species trees. BMC Bioinformatics. 2012; 13:6. BioMed Central.","journal-title":"BMC Bioinformatics"},{"issue":"6","key":"7011_CR28","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1186\/1471-2164-15-S6-S12","volume":"15","author":"M Lafond","year":"2014","unstructured":"Lafond M, El-Mabrouk N. Orthology and paralogy constraints: satisfiability and consistency. BMC Genomics. 2014; 15(6):12.","journal-title":"BMC Genomics"},{"issue":"5","key":"7011_CR29","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1038\/nmeth.3830","volume":"13","author":"AM Altenhoff","year":"2016","unstructured":"Altenhoff AM, Boeckmann B, Capella-Gutierrez S, Dalquen DA, DeLuca T, Forslund K, Huerta-Cepas J, Linard B, Pereira C, Pryszcz LP, Schreiber F, da Silva AS, Szklarczyk D, Train C-M, Bork P, Lecompte O, von Mering C, Xenarios I, Sj\u00f6lander K, Jensen LJ, Martin MJ, Muffato M, Quest for Orthologs consortium, Gabald\u00f3n T, Lewis SE, Thomas PD, Sonnhammer E, Dessimoz C. Standardized benchmarking in the quest for orthologs. Nature methods. 2016; 13(5):425\u201330. https:\/\/doi.org\/10.1038\/nmeth.3830.","journal-title":"Nature methods"}],"container-title":["BMC Genomics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12864-020-07011-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12864-020-07011-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12864-020-07011-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T16:28:43Z","timestamp":1723912123000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcgenomics.biomedcentral.com\/articles\/10.1186\/s12864-020-07011-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11]]},"references-count":29,"journal-issue":{"issue":"S10","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["7011"],"URL":"https:\/\/doi.org\/10.1186\/s12864-020-07011-0","relation":{},"ISSN":["1471-2164"],"issn-type":[{"value":"1471-2164","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11]]},"assertion":[{"value":"18 November 2020","order":1,"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":"779"}}