Cargando…
Testing the agreement of trees with internal labels
BACKGROUND: 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 [Formula: see text] of semi-labeled trees, called input trees, over p...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8643029/ https://www.ncbi.nlm.nih.gov/pubmed/34863219 http://dx.doi.org/10.1186/s13015-021-00201-9 |
_version_ | 1784609796174905344 |
---|---|
author | Fernández-Baca, David Liu, Lei |
author_facet | Fernández-Baca, David Liu, Lei |
author_sort | Fernández-Baca, David |
collection | PubMed |
description | BACKGROUND: 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 [Formula: see text] of semi-labeled trees, called input trees, over partially overlapping sets of taxa. The agreement problem asks whether there exists a tree [Formula: see text] , called an agreement tree, whose taxon set is the union of the taxon sets of the input trees such that the restriction of [Formula: see text] to the taxon set of [Formula: see text] is isomorphic to [Formula: see text] , for each [Formula: see text] . 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. RESULTS: We give a [Formula: see text] algorithm for the agreement problem, where n is the total number of distinct taxa in [Formula: see text] , k is the number of trees in [Formula: see text] , and [Formula: see text] is the maximum number of children of a node in [Formula: see text] . CONCLUSION: 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. |
format | Online Article Text |
id | pubmed-8643029 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-86430292021-12-06 Testing the agreement of trees with internal labels Fernández-Baca, David Liu, Lei Algorithms Mol Biol Research BACKGROUND: 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 [Formula: see text] of semi-labeled trees, called input trees, over partially overlapping sets of taxa. The agreement problem asks whether there exists a tree [Formula: see text] , called an agreement tree, whose taxon set is the union of the taxon sets of the input trees such that the restriction of [Formula: see text] to the taxon set of [Formula: see text] is isomorphic to [Formula: see text] , for each [Formula: see text] . 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. RESULTS: We give a [Formula: see text] algorithm for the agreement problem, where n is the total number of distinct taxa in [Formula: see text] , k is the number of trees in [Formula: see text] , and [Formula: see text] is the maximum number of children of a node in [Formula: see text] . CONCLUSION: 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. BioMed Central 2021-12-04 /pmc/articles/PMC8643029/ /pubmed/34863219 http://dx.doi.org/10.1186/s13015-021-00201-9 Text en © The Author(s) 2021 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) . The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/ (https://creativecommons.org/publicdomain/zero/1.0/) ) applies to the data made available in this article, unless otherwise stated in a credit line to the data. |
spellingShingle | Research Fernández-Baca, David Liu, Lei Testing the agreement of trees with internal labels |
title | Testing the agreement of trees with internal labels |
title_full | Testing the agreement of trees with internal labels |
title_fullStr | Testing the agreement of trees with internal labels |
title_full_unstemmed | Testing the agreement of trees with internal labels |
title_short | Testing the agreement of trees with internal labels |
title_sort | testing the agreement of trees with internal labels |
topic | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8643029/ https://www.ncbi.nlm.nih.gov/pubmed/34863219 http://dx.doi.org/10.1186/s13015-021-00201-9 |
work_keys_str_mv | AT fernandezbacadavid testingtheagreementoftreeswithinternallabels AT liulei testingtheagreementoftreeswithinternallabels |