One of the central challenges in phylogenetics is the accurate reconstruction of phylogenetic trees from short taxon-sequences. The sequence length required for correct topological reconstruction depends on certain properties of the tree such as its depth and edge-weights. Of special interest are fast converging algorithms, which, under the assumption of a constant lower bound on edge weights, require only polynomial length sequences to guarantee correct topological reconstruction with high probability. However, when the original phylogenetic tree contains very short edges, the required sequence-length may be too long for practical purposes. Moreover, incorrect reconstruction of short edges may (and in practice often does) propagate in the sense that it prevents the correct reconstruction of long edges as well. Therefore, most known reconstruction algorithms assume that the original tree has a fully resolved topology and all its edges are sufficiently long.
In this talk we present a fast converging reconstruction algorithm which avoids this assumption. The algorithm returns a partially resolved topology which contains all sufficiently long edges of the original tree, and no edges which contradict the original topology. It is designed to reconstruct more edges when the input sequences grow longer. Unlike existing fast converging reconstruction algorithms, this method provides a reconstruction guarantee for every taxon-sequence length. This makes it more appropriate for practical use.
view more