Biology subjects

Gascuel, O.

Publications and source records attributed to Gascuel, O..

At least 19 recordsLinked to original sources

bioRxiv2026

Outperforming the Majority-Rule Consensus Tree Using Fine-Grained Dissimilarity Measures

Phylogenetic analyses often require the summarization of multiple trees, e.g., in Bayesian analyses to obtain the centroid of the posterior distribution of trees, or to determine the consensus of a set of bootstrap trees. The majority-rule consensus tree is the most commonly used. It is easy to compute and minimizes the sum of Robinson-Foulds (RF) distances to the input trees. In mathematical terms, the majority-rule consensus tree is the median of the input trees with respect to the RF distance. However, due to the coarse nature of RF distance, which only considers whether two branches induce exactly the same bipartition of the taxa or not, highly unresolved trees can be produced when the phylogenetic signal is low. To overcome this limitation, we propose using median trees with respect to finer-grained dissimilarity measures between trees. These measures include a quartet distance between tree topologies, and transfer distances, which quantify the similarity between bipartitions, in contrast to the 0/1 view of RF. We describe fast heuristic consensus algorithms for transfer-based tree dissimilarities, capable of efficiently processing trees with thousands of taxa. Through evaluations on simulated datasets in both Bayesian and bootstrapping maximum-likelihood frameworks, our results show that our methods improve consensus tree resolution in scenarios with low to moderate phylogenetic signal, while providing better or comparable dissimilarities to the true phylogeny. Applying our methods to Mammal phylogeny and a large HIV dataset of over nine thousand taxa confirms the improvement with real data. These results demonstrate the usefulness of our new consensus tree methods for analyzing the large datasets that are available today. Our software, PhyloCRISP, is available from https://github.com/yukiregista/PhyloCRISP.

bioinformatics↗

bioRxiv2025

A Systematic Investigation of Overfitting in Maximum Likelihood Phylogenetic Inference

Maximum Likelihood (ML) tree inference reconstructs phylogenies from Multiple Sequence Alignments (MSAs). Since MSAs are inherently noisy, ML tools may experience overfitting, whereby the inferred topology incorrectly models noise alongside the true phylogenetic signal. We statistically assess overfitting in ML tools using log-likelihood scores on unseen sites as primary metric. We deploy a 10-fold Monte Carlo cross-validation approach, partitioning 9,062 empirical and 6,342 simulated MSAs into training (80%) and testing (20%) sites. We conduct inferences using RAxML-NG, IQ-TREE, Fast-Tree, and RAxML-NG ES (a recently released Early Stopping version) on the training MSAs. We store all intermediate improved topologies and subsequently evaluate them on the testing sites. We perform a linear regression on the final segments (we use four distinct segment-window configurations) of the derived testing curves, and statistically evaluate the line slopes via the sign test. Our results indicate that ML tools do not overfit. For RAxML-NG (standard and ES) and IQ-TREE, the overall trend is non-significant for 86-98% of the empirical MSAs (across all four segment-window configurations), while for less than 1% the tools exhibit over-fitting. FastTree shows more positive trends, suggesting premature termination, especially on protein MSAs. Topological accuracy curves on simulated data further confirm that tools do not systematically diverge from the true topology. To complement these findings, we test whether strategies to mitigate overfitting can benefit ML inferences. To this end, we also benchmark a site-based holdout validation (HV) version of RAxML-NG. The results confirm that the overfitting is absent and also indicate that excluding MSA sites substantially reduces phylogenetic signal as well as accuracy.

evolutionary biology↗

bioRxiv2024

PhyloCNN: Improving tree representation and neural network architecture for deep learning from trees in phylodynamics and diversification studies

Phylodynamics and diversification studies using complex evolutionary models can be challenging, especially with traditional likelihood-based approaches. As an alternative, likelihood-free simulation-based approaches have been proposed due to their ability to incorporate complex models and scenarios. Here, we propose a new simulation-based deep learning (DL) method capable of analyzing large datasets and accurately estimating parameter values for birth-death models in both phylodynamics and diversification studies. Our approach involves encoding trees by extracting a vector of local features for all nodes of the input phylogeny. We also developed a dedicated convolutional neural network architecture called PhyloCNN. Using simulations, we compared the accuracy of PhyloCNN when using feature vectors with a variable number of generations to describe the local context of nodes and leaves. The number of generations had a greater impact when considering smaller training sets, with a broader context showing higher accuracy, especially for complex evolutionary models. Compared to other recently developed DL approaches, PhyloCNN showed higher or similar accuracies for all parameters when used with training sets one or two orders of magnitude smaller (10,000 to 100,000 simulated training trees, instead of millions). We applied PhyloCNN with compelling results to two real-world phylodynamics and diversification datasets, related to HIV superspreaders in Zurich and to primates and their ecological role as seed dispersers. The high accuracy and computational efficiency of our method opens new possibilities for phylodynamics and diversification studies that need to account for idiosyncratic phylogenetic histories with specific parameter spaces and sampling scenarios not considered in more general approaches.

bioinformatics↗

bioRxiv2024

Much Ado About Nothing: Accelerating Maximum Likelihood Phylogenetic Inference via Early Stopping to evade (Over-)optimization

Maximum Likelihood (ML) based phylogenetic inference constitutes a challenging optimization problem. Given a set of aligned input sequences, phylogenetic inference tools strive to determine the tree topology, the branch-lengths, and the evolutionary parameters that maximize the phylogenetic likelihood function. However, there exist compelling reasons to not push optimization to its limits, by means of early, yet adequate stopping criteria. Since input sequences are typically subject to stochastic and systematic noise, one should exhibit caution regarding (over-)optimization and the inherent risk of overfitting the model to noisy input data. To this end, we propose, implement, and evaluate four statistical early stopping criteria in RAxML-NG that evade excessive and compute-intensive (over-)optimization. These generic criteria can seamlessly be integrated into other phylo-genetic inference tools while not decreasing tree accuracy. The first two criteria quantify input data-specific sampling noise to derive a stopping threshold. The third, employs the Kishino-Hasegawa (KH) test to statistically assess the significance of differences between intermediate trees before, and after major optimization steps in RAxML-NG. The optimization terminates early when improvements are insignificant. The fourth method utilizes multiple testing correction in the KH test. We show that all early stopping criteria infer trees that are statistically equivalent compared to inferences without early stopping. In conjunction with a necessary simplification of the standard RAxML-NG tree search heuristic, the average inference times on empirical and simulated datasets are [~]3.5 and [~]1.8 times faster, respectively, than for standard RAxML-NG v.1.2. The four stopping criteria have been implemented in RAxML-NG and are available as open source code under GNU GPL at https://github.com/togkousa/raxml-ng.

bioinformatics↗

bioRxiv2024

The Bayesian Phylogenetic Bootstrap, Application to Short Trees and Branches

Felsensteins bootstrap is the most commonly used method to measure branch support in phylogenetics. Current sequencing technologies can result in massive sampling of taxa (e.g. SARS-CoV-2). In this case, the sequences are very similar, the trees are short, and the branches correspond to a small number of mutations (possibly 0). Nevertheless, these trees contain a strong signal, with unresolved parts but a low rate of false branches. With such data, Felsensteins bootstrap is not satisfactory. Due to the frequentist nature of bootstrap sampling, the expected support of a branch corresponding to a single mutation is [~]63%, even though it is highly likely to be correct. Here we propose a Bayesian version of the phylogenetic bootstrap in which sites are assigned uninformative prior probabilities. The branch support can then be interpreted as a posterior probability. We do not view the alignment as a small subsample of a large sample of sites, but rather as containing all available information (e.g., as with complete viral genomes, which are becoming routine). We give formulas for expected supports under the assumption of perfect phylogeny, in both the frequentist and Bayesian frameworks, where a branch corresponding to a single mutation now has an expected support of [~]90%. Simulations show that these theoretical results are robust to realistic data. Analyses on low-homoplasy viral and non-viral datasets show that Bayesian bootstrap support is easier to interpret, with high supports for branches very likely to be correct. As homoplasy increases, the two supports become closer and strongly correlated.

evolutionary biology↗

bioRxiv2023

Robustness of Felsenstein's versus Transfer Bootstrap Supports with respect to Taxon Sampling

The bootstrap method is based on resampling alignments and re-estimating trees. Felsensteins bootstrap proportions (FBP) is the most common approach to assess the reliability and robustness of sequence-based phylogenies. However, when increasing taxon-sampling (i.e., the number of sequences) to hundreds or thousands of taxa, FBP tends to return low supports for deep branches. The Transfer Bootstrap Expectation (TBE) has been recently suggested as an alternative to FBP. TBE is measured using a continuous transfer index in [0,1] for each bootstrap tree, instead of the {0,1} index used in FBP to measure the presence/absence of the branch of interest. TBE has been shown to yield higher and more informative supports, without inducing falsely supported branches. Nonetheless, it has been argued that TBE must be used with care due to sampling issues, especially in datasets with high number of closely related taxa. In this study, we conduct multiple experiments by varying taxon sampling and comparing FBP and TBE support values on different phylogenetic depth, using empirical datasets. Our results show that the main critic of TBE stands in extreme cases with shallow branches and highly unbalanced sampling among clades, but that TBE is still robust in most cases, while FBP is inescapably negatively impacted by high taxon sampling. We suggest guidelines and good practices in TBE (and FBP) computing and interpretation.

bioinformatics↗

bioRxiv2021

Sensitive Detection of Site-wise Convergent Evolution in Large Protein Alignments with ConDor

Evolutionary convergences are observed at all levels, from phenotype to DNA and protein sequences, and changes at these different levels tend to be highly correlated. Notably, convergent and parallel mutations can lead to convergent changes in phenotype, such as changes in metabolism, drug resistance, and other adaptations to changing environments. We propose a two-step approach to detect mutations under convergent evolution in protein alignments. We first select mutations that emerge more often than expected under neutral evolution and then test whether their emergences correlate with the convergent phenotype under study. The first step can be used alone when no phenotype is available, as is often the case with microorganisms. In the first step, a phylogeny is inferred from the data and used to simulate the evolution of each alignment position. These simulations are used to estimate the expected number of mutations under neutral conditions, which is compared to what is observed in the data. Next, using a comparative phylogenetic approach, we measure whether the presence of mutations occurring more often than expected correlates with the convergent phenotype. Our method is implemented in a standalone workflow and a webserver, called ConDor. We apply ConDor to three datasets: sedges PEPC proteins, HIV reverse transcriptase and fish rhodopsin. The results show that the two components of ConDor complement each other, with an overall accuracy that compares favorably to other available tools, especially on large datasets.

evolutionary biology↗

bioRxiv2021

Gotree/Goalign : Toolkit and Go API to facilitate the development of phylogenetic workflows

Besides computer intensive steps, phylogenetic analysis workflows are usually composed of many small, reccuring, but important data manipulations steps. Among these, we can find file reformatting, sequence renaming, tree re-rooting, tree comparison, bootstrap support computation, etc. These are often performed by custom scripts or by several heterogeneous tools, which may be error prone, uneasy to maintain and produce results that are challenging to reproduce. For all these reasons, the development and reuse of phylogenetic workflows is often a complex task. We identified many operations that are part of most phylogenetic analyses, and implemented them in a toolkit called Gotree/Goalign. The Gotree/Goalign toolkit implements more than 120 user-friendly commands and an API dedicated to multiple sequence alignment and phylogenetic tree manipulations. It is developed in Go, which makes executables efficient, easily installable, integrable in workflow environments, and parallelizable when possible. This toolkit is freely available on most platforms (Linux, MacOS and Windows) and most architectures (amd64, i386). Sources and binaries are available on GitHub at https://github.com/evolbioinfo/gotree, Bioconda, and DockerHub.

bioinformatics↗

bioRxiv2021

Using machine learning and big data to explore the drug resistance landscape in HIV

The authors have withdrawn this manuscript due to a duplicate posting of manuscript number 435621. Therefore, the author does not wish this work to be cited as reference for the project. Please cite and refer to the preprint 435621 (DOI: https://doi.org/10.1101/2021.03.16.435621). If you have any questions, please contact the corresponding authors.

bioinformatics↗

bioRxiv2021

Deep learning from phylogenies to uncover the transmission dynamics of epidemics

Widely applicable, accurate and fast inference methods in phylodynamics are needed to fully profit from the richness of genetic data in uncovering the dynamics of epidemics. Standard methods, including maximum-likelihood and Bayesian approaches, generally rely on complex mathematical formulae and approximations, and do not scale with dataset size. We develop a likelihood-free, simulation-based approach, which combines deep learning with (1) a large set of summary statistics measured on phylogenies or (2) a complete and compact representation of trees, which avoids potential limitations of summary statistics and applies to any phylodynamics model. Our method enables both model selection and estimation of epidemiological parameters from very large phylogenies. We demonstrate its speed and accuracy on simulated data, where it performs better than the state-of-the-art methods. To illustrate its applicability, we assess the dynamics induced by superspreading individuals in an HIV dataset of men-having-sex-with-men in Zurich. Our tool PhyloDeep is available on github.com/evolbioinfo/phylodeep.

bioinformatics↗

bioRxiv2021

Cuban history of CRF19 recombinant subtype of HIV-1

CRF19 is a recombinant form of HIV-1 subtypes D, A1 and G, which was first sampled in Cuba in 1999, but was already present there in 1980s. CRF19 was reported almost uniquely in Cuba, where it accounts for ~25% of new HIV-positive patients and causes rapid progression to AIDS (~ 3 years). We analyzed a large data set comprising ~ 350 pol and env sequences sampled in Cuba over the last 15 years and ~ 350 from Los Alamos database. This data set contained both CRF19 (~ 315), and A1, D and G sequences. We performed and combined analyses for the three A1, G and D regions, using fast maximum likelihood approaches, including: (1) phylogeny reconstruction, (2) spatio-temporal analysis of the virus spread, and ancestral character reconstruction for (3) transmission mode and (4) drug resistance mutations (DRMs). This allowed us to acquire new insights on the CRF19 origin and transmission patterns. We showed that CRF19 recombined between 1966 and 1977, most likely in Cuban community stationed in Congo region. We further investigated CRF19 spread on the Cuban province level, and discovered that the epidemic started in 1970s, most probably in Villa Clara, that it was at first carried by heterosexual transmissions, and then quickly spread in the 1980s within the "men having sex with men" (MSM) community, with multiple transmissions back to heterosexuals. The analysis of the transmission patterns of common DRMs showed mostly acquired drug resistance rather than transmitted one. Our results show a very early introduction of CRF19 in Cuba, which could explain its local epidemiological success. Ignited by a major founder event, the epidemic then followed a similar pattern as other subtypes and CRFs in Cuba. The reason for the short time to AIDS remains to be understood and requires specific surveillance, in Cuba and elsewhere. Author summaryCRF19 is a recombinant form of HIV-1, which causes rapid progression to AIDS (~ 3 years versus 5 - 10 years for other subtypes and CRFs). CRF19 is reported almost uniquely in Cuba, where it is highly prevalent (~ 25%) among newly detected HIV-1 patients. In this study, we found that CRF19 most likely recombined around the 1970s in the Cuban community that was stationed in Democratic Republic of the Congo and Angola at that time. It was introduced very early into the Cuban province of Villa Clara, from where it had several introductions to La Habana in the 1980s and then further spread to other Cuban provinces. The CRF19 epidemic most probably started with heterosexual transmissions, followed in the 1980s by multiple introductions into "men having sex with men" (MSM) community, followed by multiple transmissions back to heterosexuals (often females). The early introduction of CRF19 into Cuba most likely explains its success, not observed in other parts of the world. However, importantly, its rapid progression to AIDS makes it crucial to survey CRF19 sub-epidemics not only in Cuba, but also in other parts of the world having regular exchanges with Cuba.

bioinformatics↗

bioRxiv2020

Simulating trajectories and phylogenies from population dynamics models with TiPS

We introduce TiPS, an R package to generate trajectories and phylogenetic trees associated with a compartmental model. Trajectories are simulated using Gillespies exact or approximate stochastic simulation algorithm, or a newly-proposed mixed version of the two. Phylogenetic trees are simulated from a trajectory under a backwards-in-time approach (i.e. coalescent). TiPS is based on the Rcpp package, allowing to combine the flexibility of R for model definition and the speed of C++ for simulations execution. The model is defined in R with a set of reactions, which allow capturing heterogeneity in life cycles or any sort of population structure. TiPS converts the model into C++ code and compiles it into a simulator that is interfaced in R via a function. Furthermore, the package allows defining time periods in which the models parameters can take different values. This package is particularly well suited for population genetics and phylodynamics studies that need to generate a large number of phylogenies used for population dynamics studies. This package is available on the CRAN at https://cran.r-project.org/package=TiPS.

bioinformatics↗

bioRxiv2020

Differing impacts of global and regional responses on SARS-CoV-2 transmission cluster dynamics

Although the global response to COVID-19 has not been entirely unified, the opportunity arises to assess the impact of regional public health interventions and to classify strategies according to their outcome. Analysis of genetic sequence data gathered over the course of the pandemic allows us to link the dynamics associated with networks of connected individuals with specific interventions. In this study, clusters of transmission were inferred from a phylogenetic tree representing the relationships of patient sequences sampled from December 30, 2019 to April 17, 2020. Metadata comprising sampling time and location were used to define the global behavior of transmission over this earlier sampling period, but also the involvement of individual regions in transmission cluster dynamics. Results demonstrate a positive impact of international travel restrictions and nationwide lockdowns on global cluster dynamics. However, residual, localized clusters displayed a wide range of estimated initial secondary infection rates, for which uniform public health interventions are unlikely to have sustainable effects. Our findings highlight the presence of so-called "super-spreaders", with the propensity to infect a larger-than-average number of people, in countries, such as the USA, for which additional mitigation efforts targeting events surrounding this type of spread are urgently needed to curb further dissemination of SARS-CoV-2.

genomics↗

bioRxiv2020

COVID-Align: Accurate online alignment of hCoV-19 genomes using a profile HMM

MotivationThe first cases of the COVID-19 pandemic emerged in December 2019. Until the end of February 2020, the number of available genomes was below 1,000, and their multiple alignment was easily achieved using standard approaches. Subsequently, the availability of genomes has grown dramatically. Moreover, some genomes are of low quality with sequencing/assembly errors, making accurate re-alignment of all genomes nearly impossible on a daily basis. A more efficient, yet accurate approach was clearly required to pursue all subsequent bioinformatics analyses of this crucial data. ResultshCoV-19 genomes are highly conserved, with very few indels and no recombination. This makes the profile HMM approach particularly well suited to align new genomes, add them to an existing alignment and filter problematic ones. Using a core of [~]2,500 high quality genomes, we estimated a profile using HMMER, and implemented this profile in COVID-Align, a user-friendly interface to be used online or as standalone via Docker. The alignment of 1,000 genomes requires less than 20mn on our cluster. Moreover, COVID-Align provides summary statistics, which can be used to determine the sequencing quality and evolutionary novelty of input genomes (e.g. number of new mutations and indels). Availabilityhttps://covalign.pasteur.cloud, hub.docker.com/r/evolbioinfo/covid-align Contactsolivier.gascuel@pasteur.fr, frederic.lemoine@pasteur.fr Supplementary informationSupplementary information is available at Bioinformatics online.

bioinformatics↗

bioRxiv2019

Rapidly Computing the Phylogenetic Transfer Index

Given trees T and T* on the same taxon set, the transfer index {phi}(b, T*) is the number of taxa that need to be ignored so that the bipartition induced by branch b in T is equal to some bipartition in T*. Recently, Lemoine et al. [14] used the transfer index to design a novel bootstrap analysis technique that improves on Felsensteins bootstrap on large, noisy data sets. In this work, we propose an algorithm that computes the transfer index for all branches b [isin] T in O(n log3 n) time, which improves upon the current O(n2)-time algorithm by Lin, Rajan and Moret [15]. Our implementation is able to process pairs of trees with hundreds of thousands of taxa in minutes and considerably speeds up the method of Lemoine et al. on large data sets. We believe our algorithm can be useful for comparing large phylogenies, especially when some taxa are misplaced (e.g. due to horizontal gene transfer, recombination, or reconstruction errors).

bioinformatics↗

bioRxiv2019

PastView: a user-friendly interface to explore evolutionary scenarios

BackgroundAncestral character states computed from the combination of phylogenetic trees with extrinsic traits are used to decipher evolutionary scenarios in various research fields such as phylogeography, epidemiology, and ecology. Despite the existence of powerful methods and software in ancestral character state inference, difficulties may arise when interpreting the outputs of such inferences. The growing complexity of data (trees, annotations), the diversity of optimization criteria for computing trees and ancestral character states, the combinatorial explosion of potential evolutionary scenarios if some ancestral characters states do not stand out clearly from others, requires the design of new methods that operate on tree topologies and extrinsic traits associations to ease the identification of evolutionary scenarios.\n\nResultWe developed a tool, PastView, a user-friendly interface that includes numerical and graphical features to help users to import and/or compute ancestral character states and extract evolutionary scenario as a set of successive transitions of ancestral character states from the tree root to its leaves. PastView offers synthetic views such as transition maps and integrates comparative analysis methods to highlight agreements or discrepancies between methods of ancestral annotations inference.\n\nConclusionThe main contribution of PastView is to assemble known numerical and graphical methods into a multi-maps graphical user interface dedicated to the computing, searching and viewing of evolutionary scenarios based on phylogenetic trees and ancestral character states. PastView is available publicly as a standalone software on www.pastview.org.

evolutionary biology↗

bioRxiv2018

A Darwinian Uncertainty Principle

Reconstructing ancestral characters and traits along a phylogenetic tree is central to evolutionary biology. It is the key to understanding morphology changes among species, inferring ancestral biochemical properties of life, and recovering migration routes in phylogeography. The goal is twofold: to reconstruct the character state at the tree root (e.g. the region of origin of some species), and to understand the process of state changes along the tree (e.g. species flow between countries). Although each goal can be achieved with high accuracy individually, we use mathematics and simulations to demonstrate that it is generally impossible to accurately estimate both the root state and the rates of state changes along the tree branches from the observed data at the tips of the tree. This inherent Darwinian uncertainty principle concerning the simultaneous estimation of pattern and process governs ancestral reconstructions in biology. Increasing the number of tips improves the joint estimation accuracy for certain tree shapes that arise in evolutionary models, however, for other trees shapes it does not.

evolutionary biology↗

bioRxiv2018

A Fast Likelihood Method to Reconstruct and Visualize Ancestral Scenarios

The reconstruction of ancestral scenarios is widely used to study the evolution of characters along a phylogenetic tree. In the likelihood framework one commonly uses the marginal posterior probabilities of the character states, and the joint reconstruction of the most likely scenario. Both approaches are somewhat unsatisfactory. Marginal reconstructions provide users with state probabilities, but these are difficult to interpret and visualize, while joint reconstructions select a unique state for every tree node and thus do not reflect the uncertainty of inferences.\n\nWe propose a simple and fast approach, which is in between these two extremes. We use decision-theory concepts and the Brier criterion to associate each node in the tree to a set of likely states. A unique state is predicted in the tree regions with low uncertainty, while several states are predicted in the uncertain regions, typically around the tree root. To visualize the results, we cluster the neighboring nodes associated to the same states and use graph visualization tools. The method is implemented in the PastML program and web server.\n\nThe results on simulated data consistently show the accuracy and robustness of the approach. The method is applied to large tree comprising 3,619 sequences from HIV-1M subtype C sampled worldwide, which is processed in a few minutes. Results are very convincing: we retrieve and visualize the main transmission routes of HIV-1C; we demonstrate that drug resistance mutations mostly emerge independently under treatment pressure, but some resistance clusters are found, corresponding to transmissions among untreated patients.

evolutionary biology↗