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 constitutes the refereed proceedings of the 10th International Workshop on Algorithms in Bioinformatics, WABI 2010, held in Liverpool, UK, in September 2010. The 30 revised full papers presented were carefully reviewed and selected from 83 submissions. The papers are organized in topical sections on biomolecular structure: RNA, protein and molecular comparison; comparative genomics; haplotype and genotype analysis; high-throughput data analysis: next generation sequencing and flow cytometry; networks; phylogenetics; and sequences, strings and motifs.

This book constitutes the refereed proceedings of the 11th International Workshop on Algorithms in Bioinformatics, WABI 2011, held in Saarbrücken, Germany, in September 2011. The 30 papers presented were carefully reviewed and selected from 77 submissions. They cover aspects of algorithms in bioinformatics, computational biology and systems biology.

This is the first book on "phylogenetic supertrees", a recent, but controversial development for inferring evolutionary trees. Rather than analyze the combined primary character data directly, supertree construction proceeds by combining the tree topologies derived from those data. This difference in strategy has allowed for the exciting possibility of larger, more complete phylogenies than are otherwise currently possible, with the potential to revolutionize evolutionarily-based research. This book provides a comprehensive look at supertrees, ranging from the methods used to build supertrees to the significance of supertrees to bioinformatic and biological research. Reviews of many the major supertree methods are provided and four new techniques, including a Bayesian implementation of supertrees, are described for the first time. The far-reaching impact of supertrees on biological research is highlighted both in general terms and through specific examples from diverse clades such as flowering plants, even-toed ungulates, and primates. The book also critically examines the many outstanding challenges and problem areas for this relatively new field, showing the way for supertree construction in the age of genomics. Interdisciplinary contributions from the majority of the leading authorities on supertree construction in all areas of the bioinformatic community (biology, computer sciences, and mathematics) will ensure that this book is a valuable reference with wide appeal to anyone interested in phylogenetic inference.