Biology – Quantitative Biology – Populations and Evolution
Scientific paper
2011-11-02
Biology
Quantitative Biology
Populations and Evolution
Scientific paper
As sequence databases increase in size, there is increasing interest in phylogeny algorithms that are both fast and accurate. In response, researchers have developed sub-quadratic time heuristics for building trees from very large alignments \cite{fasttree,WABI}. These heuristics lack theoretical performance guarantees, so it is unclear whether their use is universally appropriate. We present a fast algorithm that correctly reconstructs a large class of phylogenies, with high probability, assuming a Markov model of evolution. The running time of the algorithm is $O(n^{1+\gamma(g)}\log^2n)$, where $\gamma$ is an increasing function of the upper bound on branch lengths in the phylogeny and $\gamma(g)<1$ for all $g$. For phylogenies with short branches, the running time of our algorithm is close to linear. For example, if all branch lengths correspond to a mutation probability of less than 0.02, the running time of our algorithm is roughly $O(n^{1.2}\log^2n)$. Our results demonstrate that many large phylogenies can be reconstructed fast, without compromising the reconstruction accuracy.
Brown Daniel G.
Truszkowski Jakub
No associations
LandOfFree
Fast reconstruction of phylogenetic trees using locally-sensitive hashing 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 reconstruction of phylogenetic trees using locally-sensitive hashing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast reconstruction of phylogenetic trees using locally-sensitive hashing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-327490