Chen, Duhong; Diao, L.; Eulenstein, O.; Fernández-Baca, D.; Sanderson, M. 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]. Cited in 2 Documents 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 Keywords:consensus; rooted phylogenetic tree; characters; compatibility; branch and bound approach PDFBibTeX XMLCite \textit{D. Chen} et al., DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 61, 135--160 (2003; Zbl 1036.92020)