Biology subjects

Stamatakis, A.

Publications and source records attributed to Stamatakis, A..

At least 37 records · Page 2Linked to original sources

bioRxiv2023

AleRax: A tool for species and gene tree co-estimation and reconciliation under a probabilistic model of duplication, transfer, and loss

MotivationGenomes are a rich source of information on the pattern and process of evolution across biological scales. How best to make use of that information is an active area of research in phylogenetics. Ideally, phylogenetic methods should not only model substitutions along gene trees, which explain differences between homologous gene sequences, but also the processes that generate the gene trees themselves along a shared species tree. To conduct accurate inferences, one needs to account for uncertainty at both levels, that is, in gene trees estimated from inherently short sequences and in their diverse evolutionary histories along a shared species tree. ResultsWe present AleRax, a software that can infer reconciled gene trees together with a shared species tree using a simple, yet powerful, probabilistic model of gene duplication, transfer, and loss. A key feature of AleRax is its ability to account for uncertainty in the gene tree and its reconciliation by using an efficient approximation to calculate the joint phylogenetic-reconciliation likelihood and sample reconciled gene trees accordingly. Simulations and analyses of empirical data show that AleRax is one order of magnitude faster than competing gene tree inference tools while attaining the same accuracy. It is consistently more robust than species tree inference methods such as SpeciesRax and ASTRAL-Pro 2 under gene tree uncertainty. Finally, AleRax can process multiple gene families in parallel thereby allowing users to compare competing phylogenetic hypotheses and estimate model parameters, such as DTL probabilities for genome-scale datasets with hundreds of taxa Availability and ImplementationGNU GPL at https://github.com/BenoitMorel/AleRax and data are made available at https://cme.h-its.org/exelixis/material/alerax_data.tar.gz. ContactBenoit.Morel@h-its.org Supplementary informationSupplementary material is available.

bioinformatics↗

bioRxiv2023

Simulations of sequence evolution: how (un)realistic they really are and why

MotivationSimulating Multiple Sequence Alignments (MSAs) using probabilistic models of sequence evolution plays an important role in the evaluation of phylogenetic inference tools, and is crucial to the development of novel learning-based approaches for phylogenetic reconstruction, for instance, neural networks. These models and the resulting simulated data need to be as realistic as possible to be indicative of the performance of the developed tools on empirical data and to ensure that neural networks trained on simulations perform well on empirical data. Over the years, numerous models of evolution have been published with the goal to represent as faithfully as possible the sequence evolution process and thus simulate empirical-like data. In this study, we simulated DNA and protein MSAs under increasingly complex models of evolution with and without insertion/deletion (indel) events using a state-of-the-art sequence simulator. We assessed their realism by quantifying how accurately supervised learning methods are able to predict whether a given MSA is simulated or empirical. ResultsOur results show that we can distinguish between empirical and simulated MSAs with high accuracy using two distinct and independently developed classification approaches across all tested models of sequence evolution. Our findings suggest that the current state-of-the-art models fail to accurately replicate several aspects of empirical MSAs, including site-wise rates as well as amino acid and nucleotide composition. Data and Code AvailabilityAll simulated and empirical MSAs, as well as all analysis results, are available at https://cme.h-its.org/exelixis/material/simulation_study.tar.gz. All scripts required to reproduce our results are available at https://github.com/tschuelia/SimulationStudy and https://github.com/JohannaTrost/seqsharp. Contactjulia.haag@h-its.org

bioinformatics↗

bioRxiv2023

Adaptive RAxML-NG: Accelerating Phylogenetic inference under Maximum Likelihood using dataset difficulty

MotivationPhylogenetic inferences under the Maximum-Likelihood (ML) criterion deploy heuristic tree search strategies to explore the vast search space. Depending on the input dataset, searches from different starting trees might all converge to a single tree topology. Often, though, distinct searches infer multiple topologies with large log-likelihood score differences or yield topologically highly distinct, yet almost equally likely, trees. Recently, Haag et al. introduced an approach to quantify, and implemented machine learning methods to predict, the difficulty of an MSA with respect to phylogenetic inference. Easy MSAs exhibit a single likelihood peak on their likelihood surface, associated with a single tree topology to which most, if not all, independent searches rapidly converge. However, as difficulty increases, multiple locally optimal likelihood peaks emerge, yet from highly distinct topologies. ResultsTo this end, we introduce and implement an adaptive tree search heuristic in RAxML-NG, which modifies the thoroughness of the tree search strategy as a function of the predicted difficulty. Our adaptive strategy is based upon three observations. First, on easy datasets, searches converge rapidly and can hence be terminated at an earlier stage. Second, over-analyzing difficult datasets is hopeless and, thus, it suffices to quickly infer only one of the numerous almost equally likely topologies, to reduce overall execution time. Third, more extensive searches are justified and required on datasets with intermediate difficulty. While the likelihood surface exhibits multiple locally optimal peaks in this case, a small proportion of them is significantly better. Our experimental results for the adaptive heuristic on 9, 515 empirical and 5, 000 simulated datasets with varying difficulty exhibit substantial speedups, especially on easy and difficult datasets (53% of total MSAs), where we observe average speedups of more than 10x. Further, approximately 94% of the inferred trees using the adaptive strategy are statistically indistinguishable from the trees inferred under the standard strategy (RAxML-NG). AvailabilityGNU GPL at https://github.com/togkousa/raxml-ng/tree/adaptive. ContactAnastasis.Togkousidis@h-its.org Supplementary MaterialAvailable

bioinformatics↗

bioRxiv2023

The power and limitations of species tree-aware phylogenetics

Species tree-aware phylogenetic methods model how gene trees are generated along the species tree by a series of evolutionary events, including the duplication, transfer and loss of genes. Over the past ten years these methods have emerged as a powerful tool for inferring and rooting gene and species trees, inferring ancestral gene repertoires, and studying the processes of gene and genome evolution. However, these methods are complex and can be more difficult to use than traditional phylogenetic approaches. Method development is rapid, and it can be difficult to decide between approaches and interpret results. Here, we review ALE and GeneRax, two popular packages for reconciling gene and species trees, explaining how they work, how results can be interpreted, and providing a tutorial for practical analysis. It was recently suggested that reconciliation-based estimates of duplication and transfer frequencies are unreliable. We evaluate this criticism and find that, provided parameters are estimated from the data rather than being fixed based on prior assumptions, reconciliation-based inferences are in good agreement with the literature, recovering variation in gene duplication and transfer frequencies across lineages consistent with the known biology of studied clades. For example, published datasets support the view that transfers greatly outnumber duplications in most prokaryotic lineages. We conclude by discussing some limitations of current models and prospects for future progress. Significance statementEvolutionary trees provide a framework for understanding the history of life and organising biodiversity. In this review, we discuss some recent progress on statistical methods that allow us to combine information from many different genes within the framework of an overarching phylogenetic species tree. We review the advantages and uses of these methods and discuss case studies where they have been used to resolve deep branches within the tree of life. We conclude with the limitations of current methods and suggest how they might be overcome in the future.

evolutionary biology↗

bioRxiv2022

Comparison of phylogenetic placements to pairwise alignments for taxonomic assignment of ciliate OTUs

Taxonomic assignment of OTUs is an important bioinformatics step in analyzing environmental sequencing data. Pairwise-alignment and phylogenetic-placement methods represent two alternative approaches to taxonomic assignments, but their results can differ. Here we used available colpodean ciliate OTUs from forest soils to compare the taxonomic assignments of VSEARCH (which performs pairwise alignments) and EPA-ng (which performs phylogenetic placements). We showed that when there are differences in taxonomic assignments between pairwise alignments and phylogenetic placements at the subtaxon level, there is a low pairwise similarity of the OTUs to the reference database. We then showcase how the output of EPA-ng can be further evaluated using GAPPA to assess the taxonomic assignments when there exist multiple equally likely placements of an OTU, by taking into account the sum over the likelihood weights of the OUT placements within a subtaxon, and the branch distances between equally likely placement locations. We also inferred evolutionary and ecological characteristics of the colpodean OTUs using their placements within subtaxa. This study demonstrates how to fully analyse the output of EPA-ng, by using GAPPA in conjunction with knowledge of the taxonomic diversity of the clade of interest.

evolutionary biology↗

bioRxiv2022

A representative Performance Assessment of Maximum Likelihood based Phylogenetic Inference Tools

SummaryThe evaluation of phylogenetic inference tools is commonly conducted on simulated and empirical sequence data alignments. An open question is how representative these alignments are with respect to those, commonly analyzed by users. Based upon the RAxMLGrove database, it is now possible to simulate DNA sequences based on more than 70, 000 representative RAxML and RAxML-NG tree inferences on empirical datasets conducted on the RAxML web servers. This allows to assess the phylogenetic tree inference accuracy of various inference tools based on realistic and representative simulated DNA alignments. We simulated 20, 000 MSAs based on representative datasets (in terms of signal strength) from RAxMLGrove, and used 5, 000 datasets from the TreeBASE database, to assess the inference accuracy of FastTree2, IQ-TREE2, and RAxML-NG. We find that on quantifiably difficult-to-analyze MSAs all of the analysed tools perform poorly, such that the quicker FastTree2, can constitute a viable alternative to infer trees. We also find, that there are substantial differences between accuracy results on simulated and empirical data, despite the fact that a substantial effort was undertaken to simulate sequences under as realistic as possible settings. ContactDimitri Hohler, dimitri.hoehler@h-its.org

bioinformatics↗

bioRxiv2022

Asteroid: a new minimum balanced evolution supertree algorithm robust to missing data.

MotivationMissing data and incomplete lineage sorting are two major obstacles to accurate species tree inference. Gene tree methods such as ASTRAL and ASTRID have been developed to account for incomplete lineage sorting. However, they can be severely affected by high levels of missing data. ResultsWe present Asteroid, a novel supertree method that infers an unrooted species tree from a set of unrooted gene trees. We show on both empirical and simulated datasets that Asteroid is more robust to missing data than ASTRAL and ASTRID, while being several orders of magnitude faster than ASTRAL for datasets that contain thousands of genes. Asteroid offers advanced features such as parallelization, support value computation, and support for multi-copy and multifurcating gene trees. AvailabilityAsteroid is freely available at https://github.com/BenoitMorel/Asteroid Contactbenoit.morel@h-its.org online.

bioinformatics↗

bioRxiv2022

The Free Lunch is not over yet - Systematic Exploration of Numerical Thresholds in Phylogenetic Inference

Maximum Likelihood (ML) is a widely used phylogenetic inference model. ML implementations heavily rely on numerical optimization routines that use internal numerical thresholds to determine convergence. We systematically analyze the impact of these threshold settings on the log-likelihood and runtimes for ML tree inferences with RAxML-NG, IQ-TREE, and FastTree on empirical datasets. We provide empirical evidence that we can substantially accelerate tree inferences with RAxML-NG and IQ-TREE by changing the default values of two such numerical thresholds. At the same time, altering these settings does not significantly impact the quality of the inferred trees. We further show that increasing both thresholds accelerates the RAxML-NG bootstrap without influencing the resulting support values. For RAxML-NG, increasing the likelihood thresholds{epsilon} LnL and{epsilon} brlen to 10 and 103 respectively results in an average tree inference speedup of 1.9 {+/-} 0.6 on Data collection 1, 1.8 {+/-} 1.1 on Data collection 2, and 1.9 {+/-} 0.8 on Data collection 2 for the RAxML-NG bootstrap. Increasing the likelihood threshold{epsilon} LnL to 10 in IQ-TREE results in an average tree inference speedup of 1.3 {+/-} 0.4 on Data collection 1 and 1.3 {+/-} 0.9 on Data collection 2.

bioinformatics↗

bioRxiv2022

From Easy to Hopeless - Predicting the Difficulty of Phylogenetic Analyses

Phylogenetic analyses under the Maximum Likelihood model are time and resource intensive. To adequately capture the vastness of tree space, one needs to infer multiple independent trees. On some datasets, multiple tree inferences converge to similar tree topologies, on others to multiple, topologically highly distinct yet statistically indistinguishable topologies. At present, no method exists to quantify and predict this behavior. We introduce a method to quantify the degree of difficulty for analyzing a dataset and present Pythia, a Random Forest Regressor that accurately predicts this difficulty. Pythia predicts the degree of difficulty of analyzing a dataset prior to initiating Maximum Likelihood based tree inferences. Pythia can be used to increase user awareness with respect to the amount of signal and uncertainty to be expected in phylogenetic analyses, and hence inform an appropriate (post-)analysis setup. Further, it can be used to select appropriate search algorithms for easy-, intermediate-, and hard-to-analyze datasets.

bioinformatics↗

bioRxiv2022

Lagrange-NG: The next generation of Lagrange

AO_SCPLOWBSTRACTC_SCPLOWComputing ancestral ranges via the Dispersion Extinction and Cladogensis (DEC) model of biogeography is characterized by an exponential number of states relative to the number of regions considered. This is because the DEC model requires computing a large matrix exponential, which typically accounts for up to 80% of overall runtime. Therefore, the kinds of biogeographical analyses that can be conducted under the DEC model are limited by the number of regions under consideration. In this work, we present a completely redesigned efficient version of the popular tool Lagrange which is up to 2.5 times faster, which we call Lagrange-NG (Next Generation). We further reduce time-to-completion by introducing a multi-grained parallelization approach, achieving a total parallel speedup of 8.5 over Lagrange on a machine with 8 cores. In order to validate the correctness of Lagrange-NG, we also introduce a novel metric on range distributions for trees in order to assess the difference between any two range inferences. Finally, Lagrange-NG exhibits substantially higher adherence to coding quality standards. It improves a respective software quality indicator as implemented in the SoftWipe tool from average (5.5; Lagrange) to high (7.8; Lagrange-NG). Lagrange-NG is freely available under GPL2.

bioinformatics↗

bioRxiv2021

RAxML Grove: An empirical Phylogenetic Tree Database

The assessment of novel phylogenetic models and inference methods is routinely being conducted via experiments on simulated as well as empirical data. When generating synthetic data it is often unclear how to set simulation parameters for the models and generate trees that appropriately reflect empirical model parameter distributions and tree shapes. As a solution, we present and make available a new database called RAxML Grove currently comprising more than 60,000 inferred trees and respective model parameter estimates from fully anonymized empirical data sets that were analyzed using RAxML (1) and RAxML-NG (2) on two web servers. We also describe and make available two simple applications of RAxML Grove to exemplify its usage and highlight its utility for designing realistic simulation studies and analyzing empirical model parameter and tree shape distributions. RAxML Grove is freely available at https://github.com/angtft/RAxMLGrove.

bioinformatics↗

bioRxiv2021

Phylourny: Predicting the Knock-out-phase of Tournaments via Phylogenetic Methods by example of the UEFA EURO 2020

The prediction of knock-out tournaments represents an area of large public interest and active academic as well as industrial research. Here, we leverage the computational analogies between calculating the so-called phylogenetic likelihood score used in the area of molecular evolution and efficiently calculating, instead of approximating via simulations, the exact per-team winning probabilities, given a pairwise win probability matrix P. We implement and make available our method as open-source code and deploy it to calculate the winning probabilities for all teams participating at the knock-out phase of the UEFA EURO 2020 football tournament. We use three different P matrices to conduct predictions, two inferred via our own simple method and one computed by experts in the field. According to this expert P matrix which we trust most, we find that the most probable final is France versus England and that England has a slightly higher probability to win the title. The ability to efficiently and exactly compute winning probabilities, apart from improving and accelerating predictions, might allow for the development of novel methods to compute P.

bioinformatics↗

bioRxiv2021

SpeciesRax: A tool for maximum likelihood species tree inference from gene family trees under duplication, transfer, and loss.

Species tree inference from gene family trees is becoming increasingly popular because it can account for discordance between the species tree and the corresponding gene family trees. In particular, methods that can account for multiple-copy gene families exhibit potential to leverage paralogy as informative signal. At present, there does not exist any widely adopted inference method for this purpose. Here, we present SpeciesRax, the first maximum likelihood method that can infer a rooted species tree from a set of gene family trees and can account for gene duplication, loss, and transfer events. By explicitly modelling events by which gene trees can depart from the species tree, SpeciesRax leverages the phylogenetic rooting signal in gene trees. SpeciesRax infers species tree branch lengths in units of expected substitutions per site and branch support values via paralogy-aware quartets extracted from the gene family trees. Using both empirical and simulated datasets we show that SpeciesRax is at least as accurate as the best competing methods while being one order of magnitude faster on large datasets at the same time. We used SpeciesRax to infer a biologically plausible rooted phylogeny of the vertebrates comprising 188 species from 31612 gene families in one hour using 40 cores. SpeciesRax is available under GNU GPL at https://github.com/BenoitMorel/GeneRax and on BioConda.

molecular biology↗

bioRxiv2021

SPART, a versatile and standardized data exchange format for species partition information

A wide range of data types can be used to delimit species and various computer-based tools dedicated to this task are now available. Although these formalized approaches have significantly contributed to increase the objectivity of SD under different assumptions, they are not routinely used by alpha-taxonomists. One obvious shortcoming is the lack of interoperability among the various independently developed SD programs. Given the frequent incongruences between species partitions inferred by different SD approaches, researchers applying these methods often seek to compare these alternative species partitions to evaluate the robustness of the species boundaries. This procedure is excessively time consuming at present, and the lack of a standard format for species partitions is a major obstacle. Here we propose a standardized format, SPART, to enable compatibility between different SD tools exporting or importing partitions. This format reports the partitions and describes, for each of them, the assignment of individuals to the "inferred species". The syntax also allows to optionally report support values, as well as original trees and the full command lines used in the respective SD analyses. Two variants of this format are proposed, overall using the same terminology but presenting the data either optimized for human readability (matricial SPART) or in a format in which each partition forms a separate block (SPART.XML). ABGD, DELINEATE, GMYC, PTP and TR2 have already been adapted to output SPART files and a new version of LIMES has been developed to import, export, merge and split them.

bioinformatics↗

bioRxiv2021

Exploring Parallel MPI Fault Tolerance Mechanisms for Phylogenetic Inference with RAxML-NG

Phylogenetic trees are now routinely inferred on large scale HPC systems with thousands of cores as the parallel scalability of phylogenetic inference tools has improved over the past years to cope with the molecular data avalanche. Thus, the parallel fault tolerance of phylogenetic inference tools has become a relevant challenge. To this end, we explore parallel fault tolerance mechanisms and algorithms, the software modifications required, and the performance penalties induced via enabling parallel fault tolerance by example of RAxML-NG, the successor of the widely used RAxML tool for maximum likelihood based phylogenetic tree inference. We find that the slowdown induced by the necessary additional recovery mechanisms in RAxML-NG is on average 2%. The overall slowdown by using these recovery mechanisms in conjunction with a fault tolerant MPI implementation amounts to 8% on average for large empirical datasets. Via failure simulations, we show that RAxML-NG can successfully recover from multiple simultaneous failures, subsequent failures, failures during recovery, and failures during checkpointing. Recoveries are automatic and transparent to the user. The modified fault tolerant RAxML-NG code is available under GNU GPL at https://github.com/lukashuebner/ft-raxml-ng Contact: lukas.huebner@{kit.edu,h-its.org};, alexey.kozlov@h-its.org, hespe@kit.edu, sanders@kit.edu, alexandros.stamatakis@hits.org Supplementary information: Supplementary data are available at bioR{chi}iv.

bioinformatics↗

bioRxiv2020

SoftWipe - a tool and benchmark to assess scientific software quality

Scientific software from all areas of scientific research is pivotal to obtaining novel insights. Yet the quality of scientific software is rarely assessed, even though it might lead to incorrect scientific results in the worst case. Therefore, we have developed an open source tool and benchmark called SoftWipe, that provides a relative software quality ranking of 51 computational tools from diverse research areas. SoftWipe can be used in the review process of software papers and to inform the scientific software selection process.

bioinformatics↗

bioRxiv2020

Phylogenetic analysis of SARS-CoV-2 data is difficult

Numerous studies covering some aspects of SARS-CoV-2 data analyses are being published on a daily basis, including a regularly updated phylogeny on nextstrain.org. Here, we review the difficulties of inferring reliable phylogenies by example of a data snapshot comprising all virus sequences available on May 5, 2020 from gisaid.org. We find that it is difficult to infer a reliable phylogeny on these data due to the large number of sequences in conjunction with the low number of mutations. We further find that rooting the inferred phylogeny with some degree of confidence either via the bat and pangolin outgroups or by applying novel computational methods on the ingroup phylogeny does not appear to be possible. Finally, an automatic classification of the current sequences into sub-classes based on statistical criteria is also not possible, as the sequences are too closely related. We conclude that, although the application of phylogenetic methods to disentangle the evolution and spread of COVID-19 provides some insight, results of phylogenetic analyses, in particular those conducted under the default settings of current phylogenetic inference tools, as well as downstream analyses on the inferred phylogenies, should be considered and interpreted with extreme caution.

evolutionary biology↗

bioRxiv2020

CellPhy: accurate and fast probabilistic inference of single-cell phylogenies from scDNA-seq data

We introduce a maximum likelihood framework called CellPhy for inferring phylogenetic trees from single-cell DNA sequencing (scDNA-seq) data. CellPhy leverages a finite-site Markov genotype substitution model with 16 diploid states, akin to those typically used in statistical phylogenetics. It includes a dedicated error function for single cells that incorporates amplification/sequencing error and allelic dropout (ADO). Moreover, it can explicitly consider the uncertainty of the variant calling process by using genotype likelihoods as input. We implemented CellPhy in a widely used open-source phylogenetic inference package (RAxML-NG) that provides statistical confidence measurements on the estimated tree and scales particularly well on large scDNA-seq datasets with hundreds or thousands of cells. To benchmark CellPhy, we carried out 19,400 coalescent simulations of cell samples from exponentially-growing tumors for which the true phylogeny was known. We evolved single-cell diploid DNA genotypes along the simulated genealogies under different scenarios, including infinite- and finite-sites nucleotide mutation models, trinucleotide mutational signatures, sequencing, and amplification errors, allele dropouts, and cell doublets. Our simulations suggest that CellPhy is robust to amplification/sequencing errors and ADO and outperforms state-of-the-art methods under realistic scDNA-seq scenarios both in terms of accuracy and speed. Also, we sequenced 24 single-cell whole-genomes from a colorectal tumor. Together with three published scDNA-seq data sets, we analyzed these empirical data to illustrate how CellPhy can provide more reliable biological insights than most competing methods. CellPhy is freely available at https://github.com/amkozlov/cellphy.

bioinformatics↗