{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:24:52Z","timestamp":1772166292737,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,4]],"date-time":"2021-12-04T00:00:00Z","timestamp":1638576000000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2021,12]]},"abstract":"Abstract<\/jats:title>\n \n \n Background<\/jats:bold>\n <\/jats:title>\n \n A semi-labeled tree is a tree where all leaves as well as, possibly, some internal nodes are labeled with taxa. Semi-labeled trees encompass ordinary phylogenetic trees and taxonomies. Suppose we are given a collection\n \n \n $${\\mathcal {P}}= \\{{\\mathcal {T}}_1, {\\mathcal {T}}_2, \\ldots , {\\mathcal {T}}_k\\}$$<\/jats:tex-math>\n \n \n P<\/mml:mi>\n =<\/mml:mo>\n {<\/mml:mo>\n \n T<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n T<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n T<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n of semi-labeled trees, called input trees, over partially overlapping sets of taxa. The agreement problem asks whether there exists a tree\n \n \n $${\\mathcal {T}}$$<\/jats:tex-math>\n \n T<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , called an agreement tree, whose taxon set is the union of the taxon sets of the input trees such that the restriction of\n \n \n $${\\mathcal {T}}$$<\/jats:tex-math>\n \n T<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n to the taxon set of\n \n \n $${\\mathcal {T}}_i$$<\/jats:tex-math>\n \n \n T<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is isomorphic to\n \n \n $${\\mathcal {T}}_i$$<\/jats:tex-math>\n \n \n T<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , for each\n \n \n $$i \\in \\{1, 2, \\ldots , k\\}$$<\/jats:tex-math>\n \n \n i<\/mml:mi>\n \u2208<\/mml:mo>\n {<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n k<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . The agreement problems is a special case of the supertree problem, the problem of synthesizing a collection of phylogenetic trees with partially overlapping taxon sets into a single supertree that represents the information in the input trees. An obstacle to building large phylogenetic supertrees is the limited amount of taxonomic overlap among the phylogenetic studies from which the input trees are obtained. Incorporating taxonomies into supertree analyses can alleviate this issue.\n <\/jats:p>\n <\/jats:sec>\n \n Results<\/jats:title>\n \n We give a\n \n \n $${\\mathcal {O}}(n k (\\sum _{i \\in [k]} d_i + \\log ^2(nk)))$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n k<\/mml:mi>\n \n (<\/mml:mo>\n \n \u2211<\/mml:mo>\n \n i<\/mml:mi>\n \u2208<\/mml:mo>\n [<\/mml:mo>\n k<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n \n d<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n +<\/mml:mo>\n \n log<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:msup>\n \n (<\/mml:mo>\n n<\/mml:mi>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n algorithm for the agreement problem, where\n n<\/jats:italic>\n is the total number of distinct taxa in\n \n \n $${\\mathcal {P}}$$<\/jats:tex-math>\n \n P<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n k<\/jats:italic>\n is the number of trees in\n \n \n $${\\mathcal {P}}$$<\/jats:tex-math>\n \n P<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and\n \n \n $$d_i$$<\/jats:tex-math>\n \n \n d<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the maximum number of children of a node in\n \n \n $${\\mathcal {T}}_i$$<\/jats:tex-math>\n \n \n T<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n <\/jats:sec>\n \n Conclusion<\/jats:title>\n Our algorithm can aid in integrating taxonomies into supertree analyses. Our computational experience with the algorithm suggests that its performance in practice is much better than its worst-case bound indicates.<\/jats:p>\n <\/jats:sec>","DOI":"10.1186\/s13015-021-00201-9","type":"journal-article","created":{"date-parts":[[2021,12,4]],"date-time":"2021-12-04T05:02:29Z","timestamp":1638594149000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Testing the agreement of trees with internal labels"],"prefix":"10.1186","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8563-3637","authenticated-orcid":false,"given":"David","family":"Fern\u00e1ndez-Baca","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,12,4]]},"reference":[{"issue":"3","key":"201_CR1","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"Alfred V Aho","year":"1981","unstructured":"Aho Alfred V, Sagiv Yehoshua, Szymanski Thomas G, Ullman Jeffrey D. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J Comput. 1981;10(3):405\u201321.","journal-title":"SIAM J Comput."},{"key":"201_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.2307\/1222480","volume":"41","author":"BR Baum","year":"1992","unstructured":"Baum BR. Combining trees as a way of combining data sets for phylogenetic inference, and the desirability of combining gene trees. Taxon. 1992;41:3\u201310.","journal-title":"Taxon"},{"issue":"2","key":"201_CR3","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1093\/sysbio\/sys090","volume":"62","author":"V Berry","year":"2012","unstructured":"Berry V, Bininda-Emonds OR, Semple C. Amalgamating source trees with different taxonomic levels. Syst Biol. 2012;62(2):231\u201349.","journal-title":"Syst Biol"},{"issue":"2","key":"201_CR4","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1080\/10635150500541649","volume":"55","author":"V Berry","year":"2006","unstructured":"Berry V, Semple C. Fast computation of supertrees for compatible phylogenies with nested taxa. Syst Biol. 2006;55(2):270\u201388.","journal-title":"Syst Biol"},{"key":"201_CR5","doi-asserted-by":"crossref","unstructured":"Bininda-Emonds ORP, editor. Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life, vol. 4. Series on Computational Biology. Berlin: Springer; 2004.","DOI":"10.1007\/978-1-4020-2330-9"},{"key":"201_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s00026-006-0272-z","volume":"10","author":"M Bordewich","year":"2006","unstructured":"Bordewich M, Evans G, Semple C. Extending the limits of supertree methods. Anna Comb. 2006;10:31\u201351.","journal-title":"Anna Comb"},{"key":"201_CR7","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1016\/j.tcs.2005.10.033","volume":"351","author":"D Bryant","year":"2006","unstructured":"Bryant D, Lagergren J. Compatibility of unrooted phylogenetic trees is FPT. Theor Comput Sci. 2006;351:296\u2013302.","journal-title":"Theor Comput Sci"},{"key":"201_CR8","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-1-4020-2330-9_8","volume-title":"Phylogenetic supertrees: combining information to reveal the Tree of Life","author":"P Daniel","year":"2004","unstructured":"Daniel P, Semple C. Supertree algorithms for nested taxa. In: Bininda-Emonds ORP, editor. Phylogenetic supertrees: combining information to reveal the Tree of Life. Dordrecht: Kluwer; 2004. p. 151\u201371."},{"key":"201_CR9","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1186\/s13015-017-0099-7","volume":"12","author":"Y Deng","year":"2017","unstructured":"Deng Y, Fern\u00e1ndez-Baca D. An efficient algorithm for testing the compatibility of phylogenies with nested taxa. Algorithms Mol Biol. 2017;12:7.","journal-title":"Algorithms Mol Biol"},{"issue":"8","key":"201_CR10","doi-asserted-by":"publisher","first-page":"2453","DOI":"10.1007\/s00453-017-0330-4","volume":"80","author":"Y Deng","year":"2018","unstructured":"Deng Y, Fern\u00e1ndez-Baca D. Fast compatibility testing for rooted phylogenetic trees. Algorithmica. 2018;80(8):2453\u201377.","journal-title":"Algorithmica"},{"issue":"2","key":"201_CR11","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1137\/120897559","volume":"44","author":"D Fern\u00e1ndez-Baca","year":"2015","unstructured":"Fern\u00e1ndez-Baca D, Guillemot S, Shutters B, Vakati S. Fixed-parameter algorithms for finding agreement supertrees. SIAM J Comput. 2015;44(2):384\u2013410.","journal-title":"SIAM J Comput"},{"issue":"3","key":"201_CR12","doi-asserted-by":"publisher","first-page":"53","DOI":"10.3390\/a12030053","volume":"12","author":"D Fern\u00e1ndez-Baca","year":"2019","unstructured":"Fern\u00e1ndez-Baca D, Liu L. Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study. Algorithms. 2019;12(3):53.","journal-title":"Algorithms"},{"key":"201_CR13","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-030-57821-3_12","volume-title":"Bioinformatics research and applications","author":"D Fern\u00e1ndez-Baca","year":"2020","unstructured":"Fern\u00e1ndez-Baca D, Liu L. Testing the agreement of trees with internal labels. In: Zhipeng C, Ion M, Giri N, Pavel S, Xuan G, editors. Bioinformatics research and applications. Cham: Springer; 2020. p. 127\u201339."},{"issue":"41","key":"201_CR14","doi-asserted-by":"publisher","first-page":"12764","DOI":"10.1073\/pnas.1423041112","volume":"112","author":"CE Hinchliff","year":"2015","unstructured":"Hinchliff CE, Smith SA, Allman JF, Burleigh JG, Chaudhary R, Coghill LM, Crandall KA, Deng J, Drew BT, Gazis R, Gude K, Hibbett DS, Katz LA, Laughinghouse\u00a0IV HD, McTavish EJ, Midford PE, Owen CL, Reed RH, Reesk JA, Soltis DE, Williams T, Cranston KA. Synthesis of phylogeny and taxonomy into a comprehensive tree of life. Proc Natl Acad Sci. 2015;112(41):12764\u20139.","journal-title":"Proc Natl Acad Sci"},{"issue":"4","key":"201_CR15","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm J, de Lichtenberg K, Thorup M. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J ACM. 2001;48(4):723\u201360.","journal-title":"J ACM"},{"key":"201_CR16","doi-asserted-by":"crossref","unstructured":"Jansson J, Lingas A, Rajaby R, Sung W-K. Determining the consistency of resolved triplets and fan triplets. In International Conference on Research in Computational Molecular Biology, pages 82\u201398. Springer, 2017.","DOI":"10.1007\/978-3-319-56970-3_6"},{"key":"201_CR17","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1111\/j.1096-0031.1989.tb00569.x","volume":"5","author":"WP Maddison","year":"1989","unstructured":"Maddison WP. Reconstructing character evolution on polytomous cladograms. Cladistics. 1989;5:365\u201377.","journal-title":"Cladistics"},{"issue":"1\u20132","key":"201_CR18","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0166-218X(95)00074-2","volume":"69","author":"MP Ng","year":"1996","unstructured":"Ng MP, Wormald NC. Reconstruction of rooted trees from subtrees. Discrete Appl Math. 1996;69(1\u20132):19\u201331.","journal-title":"Discrete Appl Math"},{"key":"201_CR19","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-1-4020-2330-9_12","volume-title":"Phylogenetic supertrees: combining information to reveal the tree of life","author":"RM Page","year":"2004","unstructured":"Page RM. Taxonomy, supertrees, and the tree of life. In: Bininda-Emonds OR, editor. Phylogenetic supertrees: combining information to reveal the tree of life. Dordrecht: Kluwer; 2004. p. 247\u201365."},{"key":"201_CR20","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/1055-7903(92)90035-F","volume":"1","author":"MA Ragan","year":"1992","unstructured":"Ragan MA. Phylogenetic inference based on matrix representation of trees. Mol Phylogenet Evol. 1992;1:53\u20138.","journal-title":"Mol Phylogenet Evol"},{"key":"201_CR21","doi-asserted-by":"publisher","first-page":"e3058","DOI":"10.7717\/peerj.3058","volume":"5","author":"BD Redelings","year":"2017","unstructured":"Redelings BD, Holder MT. A supertree pipeline for summarizing phylogenetic and taxonomic information for millions of species. PeerJ. 2017;5:e3058.","journal-title":"PeerJ"},{"issue":"5885","key":"201_CR22","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1126\/science.1154449","volume":"321","author":"MJ Sanderson","year":"2008","unstructured":"Sanderson MJ. Phylogenetic signal in the eukaryotic tree of life. Science. 2008;321(5885):121\u20133.","journal-title":"Science"},{"issue":"Database issue","key":"201_CR23","doi-asserted-by":"publisher","first-page":"D5","DOI":"10.1093\/nar\/gkn741","volume":"37","author":"EW Sayers","year":"2009","unstructured":"Sayers EW, et al. Database resources of the National Center for Biotechnology Information. Nucleic Acids Res. 2009;37(Database issue):D5\u201315.","journal-title":"Nucleic Acids Res"},{"key":"201_CR24","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C Semple","year":"2003","unstructured":"Semple C, Steel M. Phylogenetics. Oxford: Oxford Lecture Series in Mathematics. Oxford University Press; 2003."},{"key":"201_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/boj.12385","volume":"181","author":"The Angiosperm Phylogeny Group","year":"2016","unstructured":"The Angiosperm Phylogeny Group. An update of the Angiosperm Phylogeny Group classification for the orders and families of flowering plants: APG IV. Bot J Linnean Soc. 2016;181:1\u201320.","journal-title":"Bot J Linnean Soc."},{"key":"201_CR26","unstructured":"Warnow T. Supertree construction: opportunities and challenges. Technical Report arXiv:1805.03530, ArXiV, May 2018."},{"key":"201_CR27","doi-asserted-by":"crossref","unstructured":"Wulff-Nilsen C. Faster deterministic fully-dynamic graph connectivity. In: Proceedings of the Twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201913, pages 1757\u20131769, Philadelphia, PA, USA, 2013. Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611973105.126"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00201-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-021-00201-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00201-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T11:24:14Z","timestamp":1699874654000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-021-00201-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["201"],"URL":"https:\/\/doi.org\/10.1186\/s13015-021-00201-9","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-454322\/v1","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12]]},"assertion":[{"value":"29 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"22"}}