The Tree of Life is a standard graphical representation of the evolutionary history of organisms. It plays an important role in many analyses in biology.  The Tree of Life is reconstructed using DNA sequences collected from extant species. The basic idea is simple: the further in the tree two species are, the more dissimilar their sequences should be. In order to solve this reconstruction problem accurately and efficiently on large datasets, sophisticated mathematical and computational techniques have been used in recent years. Tools from probability theory have been particularly helpful in that respect because of the key role played by chance in evolutionary processes. The overall goal of this grant was to further develop this fruitful interplay between probability theory and mathematical phylogenetics through several projects extending previous rigorous tools to more realistic biological models of sequence evolution. 

Evolution acts on genomes through mutations which are inherited from ancestors. An important class of mutations is known as indels, whereby a nucleotide is inserted or deleted in a DNA sequence. Indels lead to significant challenges in comparing DNA data from multiple species as they cause nucleotides to be “misaligned.” The process of correcting for these nucleotide shifts is called the multiple sequence alignment problem--a notoriously difficult computational problem. Multiple sequence alignment is typically the first step in tree reconstruction algorithms. One major outcome of the current grant is a mathematical proof that this difficult problem can in fact be avoided. A new efficient method for reconstructing trees was developed that works directly on unaligned sequences and it was shown rigorously that almost optimal data requirement can be achieved using it. In related projects, techniques from probability theory were also employed to study the multiple sequence alignment problem in a proper evolutionary context.

New sequencing technologies have greatly facilitated the production of larger and larger datasets. In that context, representing the evolutionary history of a group of organisms with a single tree is often a simplification. Because different genes have different histories, a more appropriate model is a collection of trees, one for each gene. This approach is relevant for instance if some genes have undergone lateral gene transfers, whereby a gene is inherited from a distant species rather than from a direct ancestor. In that case, the resulting collection of trees can be modeled mathematically as an ensemble, each gene tree being a copy of an underlying species tree subject to a form of combinatorial noise. An outcome of this project has been a mathematical proof that the species tree can be recovered from the noisy gene trees even in the presence of high rates of transfers, which is common for example in some bacterial species. Several other types of gene tree ensembles were also studied successfully.

The reconstruction of the Tree of Life is a fundamental problem in biology which provides insights into the study of evolution, adaptation, and speciation. Through the development and broad dissemination of new algorithms for phylogenetic analysis as well as the training of graduate students, the research activities supported by this grant have helped advance the state of knowledge in evolutionary biology and may in the future contribute to the numerous benefits to society of phylogenetic research such as--just to name a few--the discovery of new life forms for biotechnology, the protection of ecosystems from invasive species, the identification of emerging diseases, or the prediction of disease outbreaks.

Last Modified: 10/29/2014
Modified by: Sebastien Roch