Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Fast Phylogenetic Tree Reconstruction Using Locality-Sensitive Hashing
verfasst von : Daniel G. Brown, Jakub Truszkowski
Erschienen in: Algorithms in Bioinformatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present the first sub-quadratic time algorithm that with high probability correctly reconstructs phylogenetic trees for short sequences generated by a Markov model of evolution. Due to rapid expansion in sequence databases, such very fast algorithms are necessary. Other fast heuristics have been developed for building trees from large alignments [18,1], but they lack theoretical performance guarantees. Our new algorithm runs in
O
(
n
1 +
γ
(
g
)
log
2
n
) time, where
γ
is an increasing function of an upper bound on the branch lengths in the phylogeny, the upper bound
g
must be below
$1/2-\sqrt{1/8} \approx 0.15$
, and
γ
(
g
) < 1 for all
g
. For phylogenies with very short branches, the running time of our algorithm is near-linear. For example, if all branches have mutation probability less than 0.02, the running time of our algorithm is roughly
O
(
n
1.2
log
2
n
). Our preliminary experiments show that many large phylogenies can be reconstructed more accurately than allowed by current methods, in comparable running times.