Biology subjects

Bettisworth, B.

Publications and source records attributed to Bettisworth, B..

11 recordsLinked to original sources

bioRxiv2026

DGM Is Dead; Long Live DGM-Star! A Quantization-Theoretic Approach to Gamma Rate Discretization

Modeling substitution rate heterogeneity as a discretized Gamma distribution is standard in phylogenetic inference. Ferretti et al. (2026) have recently demonstrated that the most commonly used equiprobable Gamma rate discretization, known simply as the discrete Gamma model (DGM), substantially overestimates average branch lengths in reconstructed phylogenies when the true rates are drawn from a continuous Gamma distribution. We propose an alternative method to discretize the Gamma rate distribution that considerably reduces the bias in estimated branch lengths and can be used as a drop-in replacement for the standard DGM. The method works especially well on large trees with short branches, yielding up to a 20-fold reduction in bias on simulated phylogenies. It is developed by applying quantization-theoretic tools to the analysis of a simplified star-phylogeny abstraction introduced by Ferretti et al. (2026), where the new method is unbiased by construction. We explain Ferretti et al.'s counterintuitive observation that increasing the number of rate categories can exacerbate the bias of the standard DGM, even though this should in principle make DGM a better approximation to the continuous case, and offer our method as an immediately available alternative.

evolutionary biology↗

bioRxiv2026

Quantifying and Predicting the Difficulty of Multiple Sequence Alignment with AlDiScore

Multiple Sequence Alignment (MSA) constitutes an important and frequent operation in molecular sequence data analysis. There exist numerous tools, algorithms, and criteria to infer an MSA. This plethora of available approaches to MSA may induced an ensemble of divergent MSAs for the same underlying unaligned sequence set. Even a single MSA tool may infer distinct MSAs when varying the input parameters. Hence, when using a diversified set of MSA algorithms and parameterizations, the observed dispersion within an MSA ensemble expresses the difficulty of inferring a robust alignment. We refer to this notion as MSA difficulty. As downstream analyses heavily rely on the MSA, characterizing MSA difficulty for a given unaligned sequence set is critical. Initially, we show that measures of dispersion within diversified MSA ensembles can reliably predict MSA difficulty. We then assess the adequacy of these measures by computing the average reference-based distance between the MSAs in the MSA ensemble and its corresponding structural reference MSA and subsequently comparing this distance to the corresponding reference-free average distance over all MSA pairs in the ensemble. We find that Blackburne and Whelans dpos alignment metric is most appropriate as its reference-free [Formula] counterpart most accurately approximates the reference-based difficulty computed on BAliBASE reference data. We therefore use [Formula] to quantify MSA difficulty on a scale from 0 (easy) to 1 (difficult). Next, we introduce the AlDiScore open-source tool, which uses machine learning to directly and reliably predict reference-free difficulty scores from unaligned sequence sets to completely omit expensive MSA computations. The underlying regression model relies upon a large set of features, including sampling-based measures of transitive consistency. We trained our AlDiScore model on a diverse collection of empirical datasets from BAliBASE, TreeBASE, and published studies. Subsequently, we demonstrate that AlDiScore attains an R2 of 0.89 and of 0.84 on unseen AA and DNA sequence sets extracted from the PANDIT v17 database. Finally, we show that there is no correlation between MSA difficulty and the corresponding phylogenetic difficulty of the respective MSA.

bioinformatics↗

bioRxiv2025

bigrig: A range simulator for the DEC model

Quality software tools for science are, as a necessity, rigorously tested and verified. However, there is a major challenge to testing software used for phylogenetics and similar analysis. There is a shortage of ground truth data which can be used for validation, resulting in a reliance on simulated data. This reliance on simulated data results in a second challenge: the verification of the tool which generates the simulated data. In historical biogeography, software which simulated data has exclusively been implemented on an ad-hoc basis to verify specific tools. Here, we introduce bigrig, a simulator for the DEC[+J] model of range evolution. We show that bigrig is correct with extremely rigorous statistical testing and validation, ensuring that results deviate by no more than 0.0001 with 99.999% confidence. We also show that bigrig is extremely fast, capable of generating data for trees with tens of thousands of tips in under a second.

bioinformatics↗

bioRxiv2025

raxtax: A k-mer-based non-Bayesian Taxonomic Classifier

MotivationTaxonomic classification in biodiversity studies is the process of assigning the anonymous sequences of a marker gene (barcode) or whole genomes (metagenomics) to a specific lineage using a reference database that contains named sequences in a known taxonomy. This classification is important for assessing the diversity of biological systems. Taxonomic classification faces two main challenges: first, accuracy is critical as errors can propagate to downstream analysis results; and second, the classification time requirements can limit study size and study design, in particular when considering the constantly growing reference databases. To address these two challenges, we introduce raxtax, an efficient, novel taxonomic classification tool for barcodes that uses common k-mers between all pairs of query and reference sequences. We also introduce two novel uncertainty scores which take into account the fundamental biases of reference databases. ResultsWe validate raxtax on three widely used empirical reference databases and show that it is 2.7-100 times faster than competing state-of-the-art tools on the largest database while being equally accurate. In particular, raxtax exhibits increasing speedups with growing query and reference sequence numbers compared to existing tools (for 100,000 and 1,000,000 query and reference sequences overall, it is 1.3 and 2.9 times faster, respectively), and therefore alleviates the taxonomic classification scalability challenge. Availability and Implementationraxtax is available at https://github.com/noahares/raxtax under a CCNC-BY-SA license. The scripts and summary metrics used in our analyses are available at https://github.com/noahares/raxtax_paper_scripts. The source code, sequence data and summarized results of the analyses are available at https://doi.org/10.5281/zenodo.15057027.

bioinformatics↗

bioRxiv2024

Read Length Dominates Phylogenetic Placement Accuracy of Ancient DNA Reads

A common problem when analyzing ancient DNA (aDNA) data is to identify the species which corresponds to the recovered aDNA sequence(s). The standard approach is to deploy sequence similarity based tools such as BLAST. However, as aDNA reads may frequently either stem from unsampled taxa due to extinction, it is likely that there is no exact match in any database. As a consequence, these tools may not be able to accurately place such reads in a phylogenetic context. Phylogenetic placement is a technique where a read is placed onto a specific branch of a phylogenetic reference tree, which allows for a substantially finer resolution when identifying reads. Prior applications of phylogenetic placement has deployed only on data from extant sources. Therefore, it is unclear how the aDNA damage affects phylogenetic placements applicability to aDNA data. To investigate how aDNA damage affects placement accuracy, we re-implemented a statistical model of aDNA damage. We deploy this model, along with a modified version of the existing assessment pipeline PEWO, to 7 empirical datasets with 4 leading tools: APPLES, EPA-ng, pplacer, and RAPPAS. We explore the aDNA damage parameter space via a grid search in order to identify the aDNA damage factors that exhibit the largest impact on placement accuracy. We find that the frequency of DNA backbone nicks (and consequently read length) has the by far largest impact on aDNA read placement accuracy, and that other factors, such as misincorporations, have a negligible effect on overall placement accuracy.

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

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↗

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

RootDigger: a root placement program for phylogenetic trees

SummaryIn phylogenetic analysis, it is common to infer unrooted trees. Thus, it is unknown which node is the most recent common ancestor of all the taxa in the phylogeny. However, knowing the root location is desirable for downstream analyses and interpretation. There exist several methods to recover a root, such as midpoint rooting or rooting the tree at an outgroup. Non-reversible Markov models can also be used to compute the likelihood of a potential root position. We present a software called RootDigger which uses a non-reversible Markov model to compute the most likely root location on a given tree and to infer a confidence value for each possible root placement. Availability and implementationRootDigger is available under the MIT licence at https://github.com/computations/root_digger

bioinformatics↗

bioRxiv2019

Empirical Analysis of Phylogenetic Quasi-Terraces

AO_SCPLOWBSTRACTC_SCPLOWTerraces in phylogenetic tree space are, among other things, important for the design of tree space search strategies. While the phenomenon of phylogenetic terraces is already known for unlinked partition models on partitioned phylogenomic data sets, it has not yet been studied if an analogous structure is present under linked and scaled partition models. To this end, we analyze aspects such as the log-likelihood distributions, likelihood-based significance tests, and nearest neighborhood interchanges on the trees residing on a terrace and compare their distributions among unlinked, linked, and scaled partition models. Our study shows that there exists a terrace-like structure under linked and scaled partition models as well. We denote this phenomenon as quasi-terrace. Therefore quasi-terraces should be taken into account in the design of tree search algorithms as well as when reporting results on the final tree topology in empirical phylogenetic studies.

bioinformatics↗