Distance methods play a central role in the field of phylogeny reconstruction, providing fast, efficient algorithms which yield reliable trees. The taxonomy problem is; given a set of DNA or amino acid sequences from several species, accurately reconstruct a phylogenetic tree representing their evolutionary history. Distance methods approach this problem by inferring a distance matrix of species-to-species evolutionary distances, and finding a tree which approximates the distance matrix. Our results consider the approach of using profile distances instead of leaf-to-leaf distances. We consider the vector space of tree metrics with regard to a basis generated by profile distances Given a fixed tree topology, we show how to project edge weights onto a topology based upon its set of profile distances. The projected edge weights provide topological insight, as negative edge weights will point to false edges in the topology. Although the presence of such negative edge weights is not guaranteed, we show that if the test tree is sufficiently close to the target tree in topology, negative edge weights will highlight the false edges. An algorithm is presented which uses this information to accurately reconstruct tree metrics.

Evolution is often modeled as a stochastic process which modifies DNA. One of the most popular and successful such processes are the Cavender-Farris (CF) trees, which are represented as edge weighted trees. The Phylogeny Construction Problem is that of, given /spl kappa/ samples drawn from a CF tree, output a CF tree which is close to the original. Each CF tree naturally defines a random variable, and the gold standard for reconstructing such trees is the maximum likelihood estimator of this variable. This approach is notoriously computationally expensive. We show that a very simple algorithm, which is a variant on one of the most popular algorithms used by practitioners, converges on the true tree at a rate which differs from the optimum by a constant. We do this by analyzing upper and lower bounds for the convergence rate of learning very simple CF trees, and then show that the learnability of each CF tree is sandwiched between two such simpler trees. Our results rely on the fact that, if the right metric is used, the likelihood space of CF trees is smooth.