Fast reconstruction of phylogenetic trees using locality-sensitive hashing

Daniel G. Brown, Jakub Truszkowski

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.…