Reconstruction of Large-Scale Phylogenies

The evolutionary relationships between organisms or phylogenies are fundamental to biology. They are invaluable as guiding tools to mine, organize and exploit the enormous amounts of biological data in the post-genomic era. The advent of high-throughput sequencing has resulted in whole genome data of many organisms and the need for inferring larger phylogenies ; both have necessitated the development of new methods and models in the field of phylogenetic reconstruction. The work presented in this dissertation contributes to this development. Phylogenies are most often inferred from genomic sequences – DNA or amino acid sequences. A key step before using a phylogenetic reconstruction method is that of aligning the input sequences. Finding accurate multiple sequence alignments is hard because of the heterogeneity of evolutionary signal present in the sequences—a more acute problem in whole genome sequences. A new approach to refining the phylogenetic signal of alignments is presented that identifies and eliminates phylogenetically noisy parts of the alignment in order to yield better phylogenies. The more recent model of evolution based on rearrangements (large-scale structural changes in genomes) has been a major step towards reconstructing large phylogenies. The design of models and methods in this area has presented significant mathematical challenges and some of these algorithmic and statistical questions are addressed in this work. The efficacy of simple distance-based methods are demonstrated in building accurate trees with rearrangement data, using precise estimates of true evolutionary distances. Novel methods methods are designed for robustness assessment of trees inferred by such distance-based methods. These methods are the first methods for robustness assessment for trees inferred from rearrangement data that are on par with previous such measures for trees inferred from sequence data. Further, two algorithmic problems on inversions are discussed : sorting by inversions and the inversion median problem. New algorithms and theoretical insights about the structure of the problems are described.

Bootstrapping phylogenies inferred from rearrangement data

Yu Lin, Bernard Moret, Vaibhav Rajan

Large-scale sequencing of genomes has enabled the inference of phylogenies based on the evolution of genomic architecture, under such events as rearrangements, duplications, and losses. Many evolutionary models and associated algorithms have been designed over the last few years and have found use in comparative genomics and phylogenetic inference. However, the assessment of phylogenies built from such data has not been properly addressed to date. The standard method used in sequence-based phylogenetic inference is the bootstrap, but it relies on a large number of homologous characters that can be resampled; yet in the case of rearrangements, the entire genome is a single character. Alternatives such as the jackknife suffer from the same problem, while likelihood tests cannot be applied in the absence of well established probabilistic models. We present a new approach to the assessment of distance-based phylogenetic inference from whole-genome data; our approach combines features of the jackknife and the bootstrap and remains nonparametric. For each feature of our method, we give an equivalent feature in the sequence-based framework; we also present the results of extensive experimental testing, in both sequence-based and genome-based frameworks. Through the feature-by-feature comparison and the experimental results, we show that our bootstrapping approach is on par with the classic phylogenetic bootstrap used in sequence-based reconstruction, and we establish the clear superiority of the classic bootstrap and of our corresponding new approach over proposed variants. Finally, we test our approach on a small dataset of mammalian genomes, verifying that the support values match current thinking about the respective branches. Our method is the first to provide a standard of assessment to match that of the classic phylogenetic bootstrap for aligned sequences. Its support values follow a similar scale and its receiver-operating characteristics are nearly identical, indicating that it provides similar levels of sensitivity and specificity. Thus our assessment method makes it possible to conduct phylogenetic analyses on whole genomes with the same degree of confidence as for analyses on aligned sequences. Extensions to search-based inference methods such as maximum parsimony and maximum likelihood are possible, but remain to be thoroughly tested. © 2011 Springer-Verlag.

Springer Verlag2011

Models and Algorithms for Whole-Genome Evolution and their Use in Phylogenetic Inference

Yu Lin

The rapid accumulation of sequenced genomes offers the chance to resolve longstanding questions about the evolutionary histories, or phylogenies, of groups of organisms. The relatively rare occurrence of large-scale evolutionary events in a whole genome, events such as genome rearrangements, duplications and losses, enables us to extract a strong and robust phylogenetic signal from whole-genome data. The work presented in this dissertation focuses on models and algorithms for whole-genome evolution and their use in phylogenetic inference. We designed algorithms to estimate pairwise genomic distances from large-scale genomic changes. We refined the evolutionary models on whole-genome evolution. We also made use of these results to provide fast and accurate methods for phylogenetic inference, that scales up, in both speed and accuracy, to modern high-resolution whole-genome data. We designed algorithms to estimate the true evolutionary distance between two genomes under genome rearrangements, and also under rearrangements, plus gains and losses. We refined the evolutionary model to be the first mathematical model to preserve the structural dichotomy in genomic organization between most prokaryotes and most eukaryotes. Those models and associated distance estimators provide a basis for studying facets of possible mechanisms of evolution through simulation and application to real genomes. Phylogenetic analyses from whole-genome data have been limited to small collections of genomes and low-resolution data; they have also lacked an effective assessment of robustness. We developed an approach that combines our distance estimator, any standard distance-based reconstruction algorithm, and a novel bootstrapping method based on resampling genomic adjacencies. The resulting tool overcomes a serious and long-standing impediment to the use of whole-genome data in phylogenetic inference and provides results comparable in accuracy and robustness to distance-based methods for sequence data. Maximum-likelihood approaches have been successfully applied to phylogenetic inferences for aligned sequences, but such applications remain primitive for whole-genome data. We developed a maximum-likelihood approach to phylogenetic analysis from whole-genome data. In combination with our bootstrap scheme, this new approach yields the first reliable phylogenetic tool for the analysis of whole-genome data at the level of syntenic blocks.

EPFL2012

Fast and accurate phylogenetic reconstruction from high-resolution whole-genome data and a novel robustness estimator

Yu Lin, Bernard Moret, Vaibhav Rajan

The rapid accumulation of whole-genome data has renewed interest in the study of genomic rearrangements. Comparative genomics, evolutionary biology, and cancer research all require models and algorithms to elucidate the mechanisms, history, and consequences of these rearrangements. However, even simple models lead to NP-hard problems, particularly in the area of phylogenetic analysis. Current approaches are limited to small collections of genomes and low-resolution data (typically a few hundred syntenic blocks). Moreover, whereas phylogenetic analyses from sequence data are deemed incomplete unless bootstrapping scores (a measure of confidence) are given for each tree edge, no equivalent to bootstrapping exists for rearrangement-based phylogenetic analysis. We describe a fast and accurate algorithm for rearrangement analysis that scales up, in both time and accuracy, to modern high-resolution genomic data. We also describe a novel approach to estimate the robustness of results-an equivalent to the bootstrapping analysis used in sequence-based phylogenetic reconstruction. We present the results of extensive testing on both simulated and real data showing that our algorithm returns very accurate results, while scaling linearly with the size of the genomes and cubically with their number. We also present extensive experimental results showing that our approach to robustness testing provides excellent estimates of confidence, which, moreover, can be tuned to trade off thresholds between false positives and false negatives. Together, these two novel approaches enable us to attack heretofore intractable problems, such as phylogenetic inference for high-resolution vertebrate genomes, as we demonstrate on a set of six vertebrate genomes with 8,380 syntenic blocks. A copy of the software is available on demand. © 2011, Mary Ann Liebert, Inc.

2011

Models and Algorithms for Whole-Genome Evolution and their Use in Phylogenetic Inference

Yu Lin

EPFL2012

Bootstrapping phylogenies inferred from rearrangement data

Yu Lin, Bernard Moret, Vaibhav Rajan

Springer Verlag2011

Fast and accurate phylogenetic reconstruction from high-resolution whole-genome data and a novel robustness estimator

Yu Lin, Bernard Moret, Vaibhav Rajan

2011