Reconstructing minimal rooted trees.
A fundamental task in evolutionary biology is to combine a collection of rooted phylogenetic trees (input trees) into a single rooted phylogenetic tree (the output tree), whose leaf set consists of the union of the leaf sets of the input trees and which also displays all of the input trees. This is sometimes known as the supertree problem, and it may not be possible to solve it if the input trees carry conflicting information. In this paper only the case where the input trees carry no conflicting information is considered, that is, the case where the trees are consistent. In \textit{A. V. Aho} et al. [SIAM J. Comput. 10, 405--421 (1981; Zbl 0462.68086)] an algorithm is presented that determines in polynomial time if a collection of rooted triples (rooted trees with three leaves) is consistent or not, and, if it is, outputs a tree consistent with the triples. Moreover, in \textit{M. Constantinescu} and \textit{D. Sankoff} [J. Classif. 12, No. 1, 101--112 (1995; Zbl 0829.92013)] and \textit{M. P. Ng} and \textit{N. C. Wormald} [Discrete Appl. Math. 69, No. 1--2, 19--31 (1996; Zbl 0868.05019)] algorithms are presented that can output all trees displaying a consistent collection of rooted triples. Building upon these studies, this paper presents two main results. First, an algorithm is presented that finds the set of all minimal rooted phylogenetic trees displaying a consistent collection of rooted triples. This constructs each such tree in polynomial time (although it is shown that there be exponentially many such trees). Second, for a collection of consistent rooted triples, a characterization is given of the tree output by the Aho et al. algorithm with respect to the set of minimal trees displaying the triples, that is based on the clusters in this tree.
- New results on optimizing rooted triplets consistency
- New Results on Optimizing Rooted Triplets Consistency
- scientific article; zbMATH DE number 2089994
- Building a small and informative phylogenetic supertree
- The complexity of inferring a minimally resolved phylogenetic supertree
- scientific article; zbMATH DE number 6851886
- scientific article; zbMATH DE number 7564377
- New heuristics for rooted triplet consistency
- An efficient algorithm for supertrees
- Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
- Extension operations on sets of leaf-labelled trees
- Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
- Reconstruction of rooted trees from subtrees
- The complexity of reconstructing trees from qualitative characters and subtrees
- Minimum triplet covers of binary phylogenetic \(X\)-trees
- The matroid structure of representative triple sets and triple-closure computation
- An efficient algorithm for supertrees
- Extension operations on sets of leaf-labelled trees
- Best match graphs with binary trees
- Closure operations in phylogenetics
- Best match graphs
- Computing quadratic entropy in evolutionary trees
- Recovering a phylogenetic tree using pairwise closure operations
- Complete characterization of incorrect orthology assignments in best match graphs
- The complexity of inferring a minimally resolved phylogenetic supertree
- Reduced representations of rooted trees.
- Resolving unresolved resolved and unresolved triplets consistency problems
This page was built for publication: Reconstructing minimal rooted trees.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1811070)
