Biology subjects

Ly-Trong, N.

Publications and source records attributed to Ly-Trong, N..

12 recordsLinked to original sources

bioRxiv2026

ProtFinder: An efficient machine learning framework for protein model selection on real data

Model selection is a fundamental step in phylogenetic analysis that determines the best-fit model of sequence evolution for a given multiple sequence alignment. Popular model selection methods, such as ModelFinder, rely on statistical information criteria, such as the Bayesian Information Criterion (BIC) or the Akaike Information Criterion (AIC). However, these approaches are computationally expensive and the use of information criteria has been the subject of ongoing discussion. Recently, machine learning has emerged as a promising approach for phylogenetic model selection in both nucleotide and protein sequence analyses. ModelDetector is currently the only machine learning-based method for amino acid substitution model selection. However, because ModelDetector was trained on simulated data, it does not perform well on real datasets. Another limitation is that it does not support different rate heterogeneity across sites (RHAS) models. To overcome these limitations, we introduce ProtFinder, an efficient machine learning framework for protein model selection that predicts amino acid substitution models, RHAS models, and amino acid frequency models. To enable ProtFinder to work with real datasets, we employed a transfer learning strategy consisting of three stages: (1) initial training on large-scale simulated data, (2) joint training on both simulated and real data, and (3) final fine-tuning using real data only. Experimental results show that ProtFinder outperformed ModelDetector in amino acid substitution model selection. ProtFinder achieved comparable accuracy to the maximum likelihood method ModelFinder for substitution model selection on medium and large MSAs. It performs slightly better than ModelFinder in RHAS model selection and substantially outperforms it in amino acid frequency model determination. Notably, ProtFinder is up to 1,400 times faster than ModelFinder in terms of inference time, making it particularly suitable for medium and large datasets.

evolutionary biology↗

bioRxiv2026

Phylogeny-aided detection of contamination in nearly 5 million SARS-CoV-2 genomes

Contamination can occur during genome sequencing when a contaminant genome is accidentally mixed with the intended genome to be sequenced. Contamination can lead to incorrect consensus genome calling, disrupting analyses of pathogen evolution and transmission. To investigate the extent of this issue, we developed PhyCD, a phylogeny-aided computational approach to investigate contamination in SARS-CoV-2 genome sequencing data. PhyCD masks consensus genome positions associated with suspicious sequencing read coverage drops, then leverages pandemic-scale phylogenetic placement techniques to identify putative contamination events. Applying PhyCD to nearly 5 million SARS-CoV-2 genomes, we identified 10,942 putative contamination events under conservative parameters. Across the flagged genomes, PhyCD flagged -- and so permits masking of -- a total of 64,753 substitutions that could cause errors in downstream genome data analyses.

bioinformatics↗

bioRxiv2026

GTRspmix: Capturing Heterogeneity of Exchangeabilities Across Sites to Improve Protein Phylogenetics

Site rate and profile mixture models capture the heterogeneity of the amino acid substitution process across sites. However, these models typically use a single matrix of amino acid exchangeabilities and ignore potential heterogeneities of these exchangeabilities across sites. Simply combining multiple exchangeability matrices with rate and profile mixtures leads to a combinatorial explosion of mixture components and a prohibitive increase in free parameters. Here, we introduce GTRspmix, a novel framework that incorporates multiple exchangeability matrices into profile and site rate mixture models while effectively managing model complexity. GTRspmix employs a clustering-based strategy that groups profiles and assigns a distinct exchangeability matrix to each profile cluster. Evaluations using both empirical and simulated datasets demonstrate that GTRspmix fits empirical data significantly better than conventional models, and that overparameterization does not present a problem for sufficiently large alignments. Based on these results, we estimated general-purpose empirical models (SXXpfamCYY series available in IQ-TREE3) from the Pfam database. These general-purpose models not only fit data much better, but they also influence branch length and tree topology estimates, effectively mitigating long-branch attraction artifacts. Because the total number of rate matrices remains manageable, the computational efficiency of the inference is identical to that of conventional profile mixture models (e.g., LG+C60+G4). GTRspmix provides a more realistic and flexible model of protein evolution, offering a robust foundation for the inference of reliable phylogenetic trees.

evolutionary biology↗

bioRxiv2026

CMAPLE 2: Fast and Accurate Phylogenetic Inference for Millions of Pathogen Genomes

Phylogenetic analysis is essential to genomic epidemiology, for example in tracing the origin and evolution of SARS-CoV-2 variants during the COVID-19 pandemic. We previously introduced CMAPLE, a single-threaded implementation of the MAPLE algorithm designed for large-scale epidemiological genomic datasets. CMAPLE can reconstruct phylogenetic trees from up to one million SARS-CoV-2 genomes. Here, we present CMAPLE 2, a multi-threaded version of CMAPLE with parallel sample placement and subtree pruning and regrafting (SPR) search algorithms. CMAPLE 2 also reduces memory consumption by compressing data structures using multiple references along the tree instead of a single reference genome. It further implements two advanced models of highly site- and nucleotide-specific mutation patterns as observed in pandemic-scale genome data. Additionally, CMAPLE 2 parallelizes SPR-based Tree Assessment (SPRTA), an efficient and interpretable approach for assessing phylogenetic tree uncertainty, and supports ancestral state and mutation inference via mutation-annotated tree (MAT) reconstruction. When inferring a phylogeny from 500,000 SARS-CoV-2 genomes using 48 CPU cores, CMAPLE 2 reduces runtime from 5 days (with sequential CMAPLE) to 9 hours (a 13-fold speedup) while decreasing peak RAM usage from 11.1 GB to 7.3 GB. CMAPLE 2 can now reconstruct a tree of nearly four million SARS-CoV-2 genomes from scratch within 12 days using 41 GB of RAM, a task that the sequential CMAPLE and MAPLE cannot realistically complete. CMAPLE 2 is applicable to many pathogen genome datasets and enhances our preparedness for future pandemics.

evolutionary biology↗

bioRxiv2026

Tryptophan became part of the universal genetic code post-LUCA

We evaluate whether tryptophan (W), widely thought to be the last of the 20 canonical amino acids added to the genetic code, was already present in the Last Universal Common Ancestor (LUCA). We reconstruct the evolutionary history of tryptophanyl-tRNA synthetase (WRS), the enzyme that attaches W to its tRNA, and the related tyrosyl-tRNA synthetase (YRS). We identify and exclude sequences derived from ancient recombination between archaeal and bacterial YRSs. Diverse rooting methods, including a novel approach exploiting time non-reversible evolution, all place the root between bacterial and archaeal YRS rather than between YRS and WRS. This supports post-LUCA WRS origination in Archaea, followed by its horizontal transfer to Bacteria. However, ancestral sequence reconstruction suggests that Archaea were depleted for W while Bacteria were not, and enzymes essential for W biosynthesis emerged in Bacteria. This suggests that W usage originated in Bacteria, with later WRS emergence in Archaea allowing the archaeal genetic code to converge with the bacterial code. The universality of the genetic code is usually attributed to common descent from LUCA, but the final step making the code universal was instead achieved by horizontal gene transfer. This gives credence to similar mechanisms for earlier steps in genetic code evolution.

evolutionary biology↗

bioRxiv2026

Modeling Site-Specific Mutation Patterns in Pandemic-Scale Phylogenetics

Models of genome evolution often account for different evolutionary rates at different genome positions due to, e.g., varying selective pressures or mutation rates. Recent evidence from millions of publicly shared SARS-CoV-2 genomes has revealed a more complex mutational landscape than can be modeled with existing approaches. Here, mutation rates are in fact not only highly position-specific, as currently modeled, but also nucleotide-specific; for example, specific mutations can occur very often at certain determined genome positions, while at the same positions other mutations might not be highly recurrent. Here, we propose and investigate a general model of genome evolution where each genome position is allowed to evolve under an independent, non-normalized substitution rate matrix describing site-specific rates of all mutation types ("Site-Specific Matrix" model, or SSM). We implement SSM in the efficient pandemic-scale phylogenetic inference software CMAPLE. Large-scale genomic epidemiological simulations suggest that, given enough data, SSM can accurately infer position- and nucleotide-specific substitution rates for more frequently observed nucleotides (typically the reference nucleotide), while other rates require higher levels of divergence. Simulations also show that SSM has a modest impact on the accuracy of phylogenetic tree estimation. We use SSM to analyze the evolution of millions of SARS-CoV-2 genomes and observe substantial mismatches between the substitution rates of classical rate variation models and our SSM estimates. These results suggest that classical models of rate variation are inadequate for modeling site-specific mutation patterns and that SSM is a useful alternative for large-scale genome analyses.

evolutionary biology↗

bioRxiv2024

TreeFormer: A transformer-based tree rearrangement operation for phylogenetic reconstruction

Phylogenetic inference is a fundamental problem in biology, which studies the origins and evolutionary relationships among species. Popular phylogenetic inference methods, such as IQ-TREE, RAxML, and PHYML, typically utilize heuristic tree search algorithms to seek a phylogenetic tree that maximizes the likelihood of the observed genetic data. However, tree search is time-consuming and often prone to local optima. To address these issues, we introduce TreeFormer, a new Transformer-based tree rearrangement operation for tree search. Experimental results show that TreeFormer achieves higher accuracy than FastTree 2 when reconstructing trees from real alignments with fewer than 1000 sites.

evolutionary biology↗

bioRxiv2024

This is SPRTA: assessing phylogenetic confidence at pandemic scales

Phylogenetics plays a central role in evolutionary biology and genomic epidemiology. Assessing phylogenetic confidence and reliability is therefore crucial and methods to do this, such as Felsensteins bootstrap, are among the most used in modern science. However, methods based on Felsensteins bootstrap suffer from excessive computational demand, and are unsuitable for large datasets. Furthermore, most of these methods emerge from a cladistic framework which makes their results hard to interpret in the context of genomic epidemiology. We propose SPRTA (" SPR-based Tree Assessment"), an efficient and interpretable approach to assess confidence in phylogenetic trees. SPRTA shifts the paradigm of phylogenetic support measurement from evaluating the confidence in clades (groupings of taxa) to genome evolution histories, for example assessing if a lineage evolved from another considered lineage or not. This focus on evolutionary histories is particularly valuable in genomic epidemiology, where typically the evolutionary and transmission history of a pathogen are of interest, not clade content. We illustrate the use of SPRTA by investigating a global SARS-CoV-2 phylogenetic tree relating > 2M genomes, highlighting plausible alternative evolutionary origins of many SARS-CoV-2 variants. We have implemented SPRTA within the free and open source maximum likelihood phylogenetic software MAPLE, available from https://github.com/NicolaDM/MAPLE.

bioinformatics↗

bioRxiv2024

Rate variation and recurrent sequence errors in pandemic-scale phylogenetics

Phylogenetic analyses of genome sequences from infectious pathogens reveal essential information regarding their evolution and transmission, as seen during the COVID-19 pandemic. Recently developed pandemic-scale phylogenetic inference methods reduce the computational demand of phylogenetic reconstruction from genomic epidemiological datasets, allowing the analysis of millions of closely related genomes. However, widespread homoplasies, due to recurrent mutations and sequence errors, cause phylogenetic uncertainty and biases. We present new algorithms and models to substantially improve the computational performance and accuracy of pandemic-scale phylogenetics. In particular, we account for, and identify, mutation rate variation and recurrent sequence errors. We reconstruct reliable and public sequence alignment and phylogenetic tree of > 2 million SARS-CoV-2 genomes encapsulating the evolutionary history and global spread of the virus up to February 2023.

bioinformatics↗

bioRxiv2024

CMAPLE: efficient phylogenetic inference in the pandemic era

We have recently introduced MAPLE (MAximum Parsimonious Likelihood Estimation), a new pandemic-scale phylogenetic inference method exclusively designed for genomic epidemiology. In response to the need for enhancing MAPLEs performance and scalability, here we present two key components: (1) CMAPLE software, a highly optimized C++ reimplementation of MAPLE with many new features and advancements; and (2) CMAPLE library, a suite of Application Programming Interfaces to facilitate the integration of the CMAPLE algorithm into existing phylogenetic inference packages. Notably, we have successfully integrated CMAPLE into the widely used IQ-TREE 2 software, enabling its rapid adoption in the scientific community. These advancements serve as a vital step towards better preparedness for future pandemics, offering researchers powerful tools for large-scale pathogen genomic analysis.

evolutionary biology↗

bioRxiv2023

AliSim-HPC: parallel sequence simulator for phylogenetics

MotivationSequence simulation plays a vital role in phylogenetics with many applications, such as evaluating phylogenetic methods, testing hypotheses, and generating training data for machine-learning applications. We recently introduced a new simulator for multiple sequence alignments called AliSim, which outperformed existing tools. However, with the increasing demands of simulating large data sets, AliSim is still slow due to its sequential implementation; for example, to simulate millions of sequence alignments, AliSim took several days or weeks. Parallelization has been used for many phylogenetic inference methods but not yet for sequence simulation. ResultsThis paper introduces AliSim-HPC, which, for the first time, employs high-performance computing for phylogenetic simulations. AliSim-HPC parallelizes the simulation process at both multi-core and multi-CPU levels using the OpenMP and MPI libraries, respectively. AliSim-HPC is highly efficient and scalable, which reduces the runtime to simulate 100 large alignments from one day to 9 minutes using 256 CPU cores from a cluster with 6 computing nodes, a 162-fold speedup. Availability and implementationAliSim-HPC is open source and available as part of the new IQ-TREE version v2.2.2.2 at https://github.com/iqtree/iqtree2/releases with a user manual at http://www.iqtree.org/doc/AliSim. Contactm.bui@anu.edu.au

evolutionary biology↗

bioRxiv2021

AliSim: A Fast and Versatile Phylogenetic Sequence Simulator For the Genomic Era

Sequence simulators play an important role in phylogenetics. Simulated data has many applications, such as evaluating the performance of different methods, hypothesis testing with parametric bootstraps, and, more recently, generating data for training machine-learning applications. Many sequence simulation programs exist, but the most feature-rich programs tend to be rather slow, and the fastest programs tend to be feature-poor. Here, we introduce AliSim, a new tool that can efficiently simulate biologically realistic alignments under a large range of complex evolutionary models. To achieve high performance across a wide range of simulation conditions, AliSim implements an adaptive approach that combines the commonly-used rate matrix and probability matrix approach. AliSim takes 1.3 hours and 1.3 GB RAM to simulate alignments with one million sequences or sites, while popular software Seq-Gen, Dawg, and INDELible require two to five hours and 50 to 500 GB of RAM. We provide AliSim as an extension of the IQ-TREE software version 2.2, freely available at www.iqtree.org, and a comprehensive user tutorial at http://www.iqtree.org/doc/AliSim.

bioinformatics↗