Computational Methods in Phylogenetic Analysis

The aim of phylogenetic analysis is to reconstruct the phylogeny (evolutionary history) of a set of organisms or genes from present-day data. Since this involves inferring past events from present-day data, this is a difficult endeavor. Even so, it must be done, for it is scientifically important and practically useful to do so. Phylogeneticists – those who do this for a living – are finding modern computational methods to be quite useful in this arduous task. This short book presents the main computational methods in present use in this field, as well as some on the cutting edge. These methods are presented in the setting of building binary trees (rooted or unrooted) from molecular sequence data. Some of these methods are applicable to other types of data as well. This book is written from the quantitative perspective. The author has aimed to present the algorithms and ideas in sufficient depth and at a formal level for someone to be able to implement them, or even adapt them to new situations. This book may also be used in a graduate or upper-division undergraduate course on the topic (one in which the computational perspective is emphasized) or as an adjunct in a course on bioinformatics. Towards this use, there are a number of pictures and examples included to assist student readers in understanding the ideas. There are also exercise questions included at the end of several chapters. The first chapter is on substitution models, stochastic processes, and substitution matrices, the second on distance-based tree-building methods, the third on parsimony-based tree-building methods, the fourth on probabilistic tree-building methods, and the fifth on finding consensus features in built trees. The sixth and the seventh chapters present more cutting edge material, on sequence graphs and aligning them, and on using sequence graphs for building a phylogenetic tree from unaligned sequences. The eighth chapter is on comparing and aligning trees. The ninth chapter presents some other interesting computational problems in phylogenetic analysis — for instance, phylogenetic networks for handling convergent evolution.