Fast phylogeny reconstruction through learning of ancestral sequences

Details Fast phylogeny reconstruction through learning of ancestral sequences Fast phylogeny reconstruction through learning of ancestral sequences

2008-12-08

arxiv.org/abs/0812.1587v1

Computer Science

Data Structures and Algorithms

Scientific paper

Given natural limitations on the length DNA sequences, designing phylogenetic reconstruction methods which are reliable under limited information is a crucial endeavor. There have been two approaches to this problem: reconstructing partial but reliable information about the tree (\cite{Mo07, DMR08,DHJ06,GMS08}), and reaching "deeper" in the tree through reconstruction of ancestral sequences. In the latter category, \cite{DMR06} settled an important conjecture of M.Steel, showing that, under the CFN model of evolution, all trees on $n$ leaves with edge lengths bounded by the Ising model phase transition can be recovered with high probability from genomes of length $O(\log n)$ with a polynomial time algorithm. Their methods had a running time of $O(n^{10})$. Here we enhance our methods from \cite{DHJ06} with the learning of ancestral sequences and provide an algorithm for reconstructing a sub-forest of the tree which is reliable given available data, without requiring a-priori known bounds on the edge lengths of the tree. Our methods are based on an intuitive minimum spanning tree approach and run in $O(n^3)$ time. For the case of full reconstruction of trees with edges under the phase transition, we maintain the same sequence length requirements as \cite{DMR06}, despite the considerably faster running time.

Affiliated with

Also associated with

No associations

Rating

Fast phylogeny reconstruction through learning of ancestral sequences 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 Fast phylogeny reconstruction through learning of ancestral sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast phylogeny reconstruction through learning of ancestral sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-281574