Computing Rooted and Unrooted Maximum Consistent Supertrees

Details Computing Rooted and Unrooted Maximum Consistent Supertrees Computing Rooted and Unrooted Maximum Consistent Supertrees

2009-01-21

arxiv.org/abs/0901.3299v2

Computer Science

Discrete Mathematics

This paper has been withdrawn by the authors due to an error

Scientific paper

A chief problem in phylogenetics and database theory is the computation of a maximum consistent tree from a set of rooted or unrooted trees. A standard input are triplets, rooted binary trees on three leaves, or quartets, unrooted binary trees on four leaves. We give exact algorithms constructing rooted and unrooted maximum consistent supertrees in time O(2^n n^5 m^2 log(m)) for a set of m triplets (quartets), each one distinctly leaf-labeled by some subset of n labels. The algorithms extend to weighted triplets (quartets). We further present fast exact algorithms for constructing rooted and unrooted maximum consistent trees in polynomial space. Finally, for a set T of m rooted or unrooted trees with maximum degree D and distinctly leaf-labeled by some subset of a set L of n labels, we compute, in O(2^{mD} n^m m^5 n^6 log(m)) time, a tree distinctly leaf-labeled by a maximum-size subset X of L that all trees in T, when restricted to X, are consistent with.

Affiliated with

Also associated with

No associations

Rating

Computing Rooted and Unrooted Maximum Consistent Supertrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing Rooted and Unrooted Maximum Consistent Supertrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Rooted and Unrooted Maximum Consistent Supertrees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-684924