text: 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 becoming necessary. Other fast heuristics have been developed for building trees from very large alignments (, and ), but they lack theoretical performance guarantees. Our new algorithm runs in @math time, where @math is an increasing function of an upper bound on the branch lengths in the phylogeny, the upper bound @math must be below @math , and @math for all @math . For phylogenies with very 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 @math . Via a prototype and a sequence of large-scale experiments, we show that many large phylogenies can be reconstructed fast, without compromising reconstruction accuracy.
  @cite_14: Phylogenetic reconstruction is the problem of reconstructing an evolutionary tree from sequences corresponding to leaves of that tree. A central goal in phylogenetic reconstruction is to be able to reconstruct the tree as accurately as possible from as short as possible input sequences. The sequence length required for correct topological reconstruction depends on certain properties of the tree, such as its depth and minimal edge-weight. Fast converging reconstruction algorithms are considered state-of the-art in this sense, as they require asymptotically minimal sequence length in order to guarantee (with high probability) correct topological reconstruction of the entire tree. However, when the original phylogenetic tree contains very short edges, this minimal sequence-length is still too long for practical purposes. Short edges are not only very hard to reconstruct; their presence may also prevent the correct reconstruction of long edges. In this paper we present a fast converging reconstruction algorithm which returns a partially resolved topology containing all edges of the original tree whose weight exceeds some (non-trivial) lower bound, which is determined by the input sequence length, as well as some properties of the tree, such as its depth. It does not depend, however, on the minimal edge-weight. This lower bound provides a partial reconstruction guarantee which is strictly stronger than the guarantees given by other fast converging algorithms. Our algorithm also has optimal complexity (linear space and quadratic-time) which, together with its partial reconstruction guarantee, makes it appealing for practical use.
  @cite_7: We give the first tight lower bounds on the complexity of reconstructing k-ary evolutionary trees from additive distance data. We also consider the problem under DNA-based distance estimation assumptions, where the accuracy of distance data depends on the length of the sequence and the distance. We give the first o(n2) algorithm to reconstruct trees in this context, and prove a trade-off between the length of the DNA sequences and the number of distance queries needed to reconstruct the tree. We introduce new computational models for understanding this problem, which simplify the development of algorithms. We prove lower bounds in these models which apply to the type of techniques currently in use.
  @cite_0: We introduce a new phylogenetic reconstruction algorithm which, unlike most previous rigorous inference techniques, does not rely on assumptions regarding the branch lengths or the depth of the tree. The algorithm returns a forest which is guaranteed to contain all edges that are: 1) sufficiently long and 2) sufficiently close to the leaves. How much of the true tree is recovered depends on the sequence length provided. The algorithm is distance-based and runs in polynomial time.
  @cite_19: Abstract Inferring evolutionary trees is an interesting and important problem in biology, but one that is computationally difficult as most associated optimization problems are NP-hard. Although many methods are provably statistically consistent (i.e. the probability of recovering the correct tree converges to 1 as the sequence length increases), the actual rate of convergence for different methods has not been well understood. In a recent paper we introduced a new method for reconstructing evolutionary trees called the dyadic closure method (DCM), and we showed that DCM has a very fast convergence rate. DCM runs in O( n 5 log n ) time, where n is the number of sequences, and so, although polynomial, the computational requirements are potentially too large to be of use in practice. In this paper we present another tree reconstruction method, the witness-antiwitness method (WAM). WAM is faster than DCM, especially on random trees, and converges to the true tree topology at the same rate as DCM. We also compare WAM to other methods used to reconstruct trees, including Neighbor Joining (possibly the most popular method among molecular biologists), and new methods introduced in the computer science literature.
  @cite_15: We present a novel distance-based algorithm for evolutionary tree reconstruction. Our algorithm reconstructs the topology of a tree with n leaves in O(n2) time using O(n) working space. In the gene...
summary: Erd o s @cite_19 gave an @math algorithm that reconstructs a phylogeny with high probability, assuming the Cavender-Farris model of evolution, for sufficiently long sequences. For most trees, their algorithm runs in @math time and requires @math sequence length. Cs u ros @cite_15 provided a @math algorithm with similar performance guarantees. Recent papers @cite_14 @cite_0 give similar algorithms to identify parts of the tree that can be reconstructed. These approaches use quartet queries chosen so that, with high probability, only correct quartets are queried. The only sub-quadratic time algorithm with guarantees on reconstruction accuracy is by King @cite_7 ; for most trees, its running time is @math provided that the sequences are @math in length.