Reconstructing minimal rooted trees. (Q1811070)

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.