×

Flipping: A supertree construction method. (English) Zbl 1036.92020

Janowitz, M. F. (ed.) et al., Bioconsensus. DIMACS working group meetings on bioconsensus, October 25–26, 2000 and October 2–5, 2001, DIMACS Center. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3197-6/hbk). DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 61, 135-160 (2003).
Summary: There are now many thousand phylogenetic trees, each of which constitutes a small subtree of the tree of life. We present an approach that allows us to integrate subtrees into large trees – supertrees – in an effort to assemble the tree of life. The input to our approach is a collection of rooted trees that intersect pairwise in their leaf sets; the goal is to construct a rooted supertree that retains as much as possible of the topological information in the input trees. This task is complicated by inconsistencies among these trees due to errors in their phylogenetic estimation.
We consider the case where the input trees are represented by the clusters they exhibit. The flip problem is to find the minimum number of flips needed to resolve all incompatibilities, where each flip moves a taxon into or out of a cluster. The resulting clusters form a flip supertree. We survey the known complexity results for the flip problem, including its NP-completeness. As an important result we prove that minimum-flip supertrees exhibit each cluster that is present in every input trees. Furthermore, we present simulation studies showing that flip supertrees are relatively accurate when compared to other supertrees, such as MRP supertrees, used by biologists.
For the entire collection see [Zbl 1012.00048].

MSC:

92D15 Problems related to evolution
92B10 Taxonomy, cladistics, statistics in mathematical biology
05C05 Trees
05C90 Applications of graph theory
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite