Testing the agreement of trees with internal labels

Abstract 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 $${\mathcal {P}}= \{{\mathcal {T}}_1, {\mathcal {T}}_2, \ldot...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	David Fernández-Baca, Lei Liu
Formato:	article
Lenguaje:	EN
Publicado:	BMC 2021
Materias:	Phylogenetic tree Taxonomy Agreement Algorithm Biology (General) QH301-705.5 Genetics QH426-470
Acceso en línea:	https://doaj.org/article/c2518d7cc57641d08d89a726ed1ed4ea
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:c2518d7cc57641d08d89a726ed1ed4ea
record_format	dspace
spelling	oai:doaj.org-article:c2518d7cc57641d08d89a726ed1ed4ea2021-12-05T12:03:08ZTesting the agreement of trees with internal labels10.1186/s13015-021-00201-91748-7188https://doaj.org/article/c2518d7cc57641d08d89a726ed1ed4ea2021-12-01T00:00:00Zhttps://doi.org/10.1186/s13015-021-00201-9https://doaj.org/toc/1748-7188Abstract 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 $${\mathcal {P}}= \{{\mathcal {T}}_1, {\mathcal {T}}_2, \ldots , {\mathcal {T}}_k\}$$ P = { T 1 , T 2 , … , T k } of semi-labeled trees, called input trees, over partially overlapping sets of taxa. The agreement problem asks whether there exists a tree $${\mathcal {T}}$$ T , called an agreement tree, whose taxon set is the union of the taxon sets of the input trees such that the restriction of $${\mathcal {T}}$$ T to the taxon set of $${\mathcal {T}}_i$$ T i is isomorphic to $${\mathcal {T}}_i$$ T i , for each $$i \in \{1, 2, \ldots , k\}$$ i ∈ { 1 , 2 , … , k } . 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 $${\mathcal {O}}(n k (\sum _{i \in [k]} d_i + \log ^2(nk)))$$ O ( n k ( ∑ i ∈ [ k ] d i + log 2 ( n k ) ) ) algorithm for the agreement problem, where n is the total number of distinct taxa in $${\mathcal {P}}$$ P , k is the number of trees in $${\mathcal {P}}$$ P , and $$d_i$$ d i is the maximum number of children of a node in $${\mathcal {T}}_i$$ T i . 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.David Fernández-BacaLei LiuBMCarticlePhylogenetic treeTaxonomyAgreementAlgorithmBiology (General)QH301-705.5GeneticsQH426-470ENAlgorithms for Molecular Biology, Vol 16, Iss 1, Pp 1-17 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Phylogenetic tree Taxonomy Agreement Algorithm Biology (General) QH301-705.5 Genetics QH426-470
spellingShingle	Phylogenetic tree Taxonomy Agreement Algorithm Biology (General) QH301-705.5 Genetics QH426-470 David Fernández-Baca Lei Liu Testing the agreement of trees with internal labels
description	Abstract 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 $${\mathcal {P}}= \{{\mathcal {T}}_1, {\mathcal {T}}_2, \ldots , {\mathcal {T}}_k\}$$ P = { T 1 , T 2 , … , T k } of semi-labeled trees, called input trees, over partially overlapping sets of taxa. The agreement problem asks whether there exists a tree $${\mathcal {T}}$$ T , called an agreement tree, whose taxon set is the union of the taxon sets of the input trees such that the restriction of $${\mathcal {T}}$$ T to the taxon set of $${\mathcal {T}}_i$$ T i is isomorphic to $${\mathcal {T}}_i$$ T i , for each $$i \in \{1, 2, \ldots , k\}$$ i ∈ { 1 , 2 , … , k } . 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 $${\mathcal {O}}(n k (\sum _{i \in [k]} d_i + \log ^2(nk)))$$ O ( n k ( ∑ i ∈ [ k ] d i + log 2 ( n k ) ) ) algorithm for the agreement problem, where n is the total number of distinct taxa in $${\mathcal {P}}$$ P , k is the number of trees in $${\mathcal {P}}$$ P , and $$d_i$$ d i is the maximum number of children of a node in $${\mathcal {T}}_i$$ T i . 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	article
author	David Fernández-Baca Lei Liu
author_facet	David Fernández-Baca Lei Liu
author_sort	David Fernández-Baca
title	Testing the agreement of trees with internal labels
title_short	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_sort	testing the agreement of trees with internal labels
publisher	BMC
publishDate	2021
url	https://doaj.org/article/c2518d7cc57641d08d89a726ed1ed4ea
work_keys_str_mv	AT davidfernandezbaca testingtheagreementoftreeswithinternallabels AT leiliu testingtheagreementoftreeswithinternallabels
_version_	1718372343776018432

Testing the agreement of trees with internal labels

Ejemplares similares