Computational phylogenetics

Computational phylogenetics is the application of computational algorithms, methods, and programs to phylogenetic analyses. The goal is to assemble a phylogenetic tree representing a hypothesis about the evolutionary ancestry of a set of genes, species, or other taxa. For example, these techniques have been used to explore the family tree of hominid species and the relationships between specific genes shared by many types of organisms. Traditional phylogenetics relies on morphological data obtained by measuring and quantifying the phenotypic properties of representative organisms, while the more recent field of molecular phylogenetics uses nucleotide sequences encoding genes or amino acid sequences encoding proteins as the basis for classification. Many forms of molecular phylogenetics are closely related to and make extensive use of sequence alignment in constructing and refining phylogenetic trees, which are used to classify the evolutionary relationships between homologous genes represented in the genomes of divergent species. The phylogenetic trees constructed by computational methods are unlikely to perfectly reproduce the evolutionary tree that represents the historical relationships between the species being analyzed. The historical species tree may also differ from the historical tree of an individual homologous gene shared by those species. Phylogenetic trees generated by computational phylogenetics can be either rooted or unrooted depending on the input data and the algorithm used. A rooted tree is a directed graph that explicitly identifies a most recent common ancestor (MRCA), usually an imputed sequence that is not represented in the input. Genetic distance measures can be used to plot a tree with the input sequences as leaf nodes and their distances from the root proportional to their genetic distance from the hypothesized MRCA. Identification of a root usually requires the inclusion in the input data of at least one "outgroup" known to be only distantly related to the sequences of interest.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (9)

Personnes associées (6)

Concepts associés (32)

Cours associés (1)

Séances de cours associées (15)

CH-210: Biochemistry

Les constituants biochimiques de l'organisme, protéines, glucides, lipides, à la lumière de l'évolution des concepts et des progrès en biologie moléculaire et génétique, sont étudiés.

Maximum de parcimonie

Les méthodes de maximum de parcimonie, ou plus simplement méthodes de parcimonie ou encore parcimonie de Wagner, sont une méthode statistique non-paramétrique très utilisée, notamment pour l'inférence phylogénétique. Cette méthode permet de construire des arbres de classification hiérarchique après enracinement, lesquels permettent d'obtenir des informations sur la structure de parenté d'un ensemble de taxons. Sous l'hypothèse du maximum de parcimonie, l'arbre phylogénétique « préféré » est celui qui requiert le plus petit nombre de changements évolutifs.

Computational phylogenetics

Multiple sequence alignment

Multiple sequence alignment (MSA) may refer to the process or the result of sequence alignment of three or more biological sequences, generally protein, DNA, or RNA. In many cases, the input set of query sequences are assumed to have an evolutionary relationship by which they share a linkage and are descended from a common ancestor. From the resulting MSA, sequence homology can be inferred and phylogenetic analysis can be conducted to assess the sequences' shared evolutionary origins.

Prédiction de la structure protéique : AlphaFold Evolution et OpenFold Insights PHYS-754: Lecture series on scientific machine learning

Explore l'évolution de la prédiction de la structure protéique avec les modèles AlphaFold et introduit les idées OpenFold.

Construire des arbres phylogénétiques: Algorithme UPGMA BIO-109: Introduction to life sciences (for IC)

Couvre l'algorithme UPGMA pour construire des arbres phylogénétiques et comprendre les relations génétiques.

Comprendre les modèles génériques des séquences protéiques

Explore un cadre unifié pour la compréhension et l'évaluation de modèles de séquences génériques d'ADN/ARN ou de protéines, couvrant des sujets tels que la coévolution, la conservation et différents modèles tels que GREMLIN et BERT.

Bootstrapping phylogenies inferred from rearrangement data

Bernard Moret, Yu Lin, Vaibhav Rajan

Background: 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. Results: 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 for sequence data and of our corresponding new approach for rearrangement data 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. Conclusions: 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.

BioMed Central2012

Reconstruction of Large-Scale Phylogenies

Vaibhav Rajan

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.

EPFL2012

Bootstrapping phylogenies inferred from rearrangement data

Bernard Moret, Yu Lin, 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