Phylogenetics is the study of the evolutionary relationships between species. The present dissertation is concerned with the efficiency, accuracy and tractability of mathematical methods for recovering these relationships. We provide new algorithms for recovering the topology and branch lengths of the evolutionary tree, and provide reliability results for our own, as well as previous methods. We focus principally on distance methods, where the phylogeny is recovered from estimates of the pair-wise evolutionary distances between terminal species.

For a known phylogenetic topology, we provide a way to recover weighted least squares edge lengths in optimal O(n ²) time, under a very general variance model. We generalize and unify many previous results under our framework of efficient computation of Lagrange multipliers. Our approach sheds much light on observed connections between WLS edge estimation and other popular algorithms for reconstructing phylogenetic topologies, most prominently the venerable and popular neighbor-joining (NJ).

New reliability bounds for NJ are presented in Chapter 3 by improving previous results and settling a famous and long-standing conjecture of Atteson concerning its error tolerance. Our results cast NJ as a robust “quartet consensus” method, explaining its surprising superiority over other such methods in practical applications. These results will also appear in [47].

When the input is not sufficiently reliable for full reconstruction, it is preferable to provide correct partial information, rather than an incorrect but fully specified tree. In [10] we presented the first practical algorithm for recovering “maximal”, reliable, edge-disjoint partial sub-forests of the model tree, without making a priori assumptions on its edge lengths.

Here, we extend the above method by recovering genetic sequences of ancestral nodes. For trees with “short” edges, this can be done for arbitrarily deep nodes with bounded probability of error. Previous algorithms [12] show that for such trees, full topological reconstruction can be obtained from sequences of logarithmic length. We give an algorithm with asymptotically optimal running time and sequence length requirements, which reconstructs the full topology for arbitrarily deep short-edge trees, and otherwise returns a partial sub-forest. As in [10], we require no a-priori edge length assumptions and allow the user control over the probability of false positives.