Technical Report Number
Theory of Computation
There are now many thousand evolutionary trees, each of which constitutes a small subtree of the tree of life. We present an approach that allows us to integrate subtrees into larger trees in an effort to assemble the supertree of life. Topological inconsistency due to errors in phylogenetic estimation complicate the task of making supertrees. To tackle this problem we solve the following optimization problem: Given a set of trees that intersect pairwise in their leaf sets --- a grove --- find a tree --- a supertree --- that has the smallest distance to the trees in the grove. We introduce a new distance measure, called flip-distance, study the complexity of computing it, and show its performance using simulations.