One of the most fundamental computational problems in biology is that of inferring evolutionary histories of groups of species from sequence data. Such evolutionary histories, known as phylogenies are usually represented as binary trees where leaves represent extant species, whereas internal nodes represent their shared ancestors. As the amount of sequence data available to biologists increases, very fast phylogenetic reconstruction algorithms are becoming necessary. Currently, large sequence alignments can contain up to hundreds of thousands of sequences, making traditional methods, such as Neighbor Joining, computationally prohibitive. To address this problem, we have developed three novel fast phylogenetic algorithms. The first algorithm, QTree, is a quartet-based heuristic that runs in O(n log n) time. It is based on a theoretical algorithm that reconstructs the correct tree, with high probability, assuming every quartet is inferred correctly with constant probability. The core of our algorithm is a balanced search tree structure that enables us to locate an edge in the tree in O(log n) time. Our algorithm is several times faster than all the current methods, while its accuracy approaches that of Neighbour Joining. The second algorithm, LSHTree, is the first sub-quadratic time algorithm with theoretical performance guarantees under a Markov model of sequence evolution. Our new algorithm runs in O(n^{1+[gamma](g)} log^2 n) time, where [gamma] is an increasing function of an upper bound on the mutation rate along any branch in the phylogeny, and [gamma](g)

This book considers evolution at different scales: sequences, genes, gene families, organelles, genomes and species. The focus is on the mathematical and computational tools and concepts, which form an essential basis of evolutionary studies, indicate their limitations, and give them orientation. Recent years have witnessed rapid progress in the mathematics of evolution and phylogeny, with models and methods becoming more realistic, powerful, and complex. Aimed at graduates and researchers in phylogenetics, mathematicians, computer scientists and biologists, and including chapters by leading scientists: A. Bergeron, D. Bertrand, D. Bryant, R. Desper, O. Elemento, N. El-Mabrouk, N. Galtier, O. Gascuel, M. Hendy, S. Holmes, K. Huber, A. Meade, J. Mixtacki, B. Moret, E. Mossel, V. Moulton, M. Pagel, M.-A. Poursat, D. Sankoff, M. Steel, J. Stoye, J. Tang, L.-S. Wang, T. Warnow, Z. Yang, this book of contributed chapters explains the basis and covers the recent results in this highly topical area.

Researchers interested in the history of the Indo-European family of languages have used a variety of methods to estimate the phylogeny of the family, and have obtained widely differing results. In this paper we explore the reconstructions of the Indo-European phylogeny obtained by using the major phylogeny estimation procedures on an existing database of 336 characters (including lexical, phonological, and morphological characters) for 24 Indo-European languages. Our study finds that the different methods agree in part, but that there are also several striking differences. We discuss the reasons for these differences, and make proposals with respect to phylogenetic reconstruction in historical linguistics.

Phylogenies, or evolutionary trees, are the basic structures necessary to think about and analyze differences between species. Statistical, computational, and algorithmic work in this field has been ongoing for four decades now, and there have been great advances in understanding. Yet no book has summarized this work. Inferring Phylogenies does just that in a single, compact volume. Phylogenies are inferred with various kinds of data. This book concentrates on some of the central ones: discretely coded characters, molecular sequences, gene frequencies, and quantitative traits. Also covered are restriction sites, RAPDs, and microsatellites.