Reconstructing minimal rooted trees. (Q1811070): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Set OpenAlex properties.
 
(4 intermediate revisions by 3 users not shown)
Property / reviewed by
 
Property / reviewed by: Vincent L. Moulton / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Vincent L. Moulton / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Extension operations on sets of leaf-labelled trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: An efficient algorithm for supertrees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reconstruction of rooted trees from subtrees / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of reconstructing trees from qualitative characters and subtrees / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/s0166-218x(02)00250-0 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2043950637 / rank
 
Normal rank

Latest revision as of 10:08, 30 July 2024

scientific article
Language Label Description Also known as
English
Reconstructing minimal rooted trees.
scientific article

    Statements

    Reconstructing minimal rooted trees. (English)
    0 references
    0 references
    10 June 2003
    0 references
    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.
    0 references
    0 references
    phylogenetic tree
    0 references
    rooted triples
    0 references
    clusters
    0 references
    tree compatibility
    0 references
    supertrees
    0 references
    0 references