archives

Supertrees by Flipping


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Chen, Duhong, Eulenstein, Oliver, Fernandez-Baca, David and Sanderson, Michael (2001) Supertrees by Flipping. Technical Report, Department of Computerscience, Iowa State University.

Full text available as:Adobe PDF
Postscript

Abstract

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.

Keywords:phylogenetic tree, supertree, tree assembly,
Subjects:Theory of Computation: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (B.6-7, F.1.3)
ID code:00000264
Deposited by:Oliver Eulenstein on 08 January 2002



Contact site administrator at: ssg@cs.iastate.edu