Biology subjects

Warnow, T.

Publications and source records attributed to Warnow, T..

At least 19 recordsLinked to original sources

bioRxiv2026

Min-frame transformation enables more sensitive viral genome alignment

MotivationMaximal unique matches (MUMs) are a fundamental primitive in genome comparison, where they serve as high-confidence anchors for downstream multiple genome alignment. However, because MUMs rely on exact string matching, their effectiveness degrades with increased genome divergence and larger sets of genomes, inhibiting their ability to recover long homologous regions and reducing the number of base pairs covered by the multiple genome alignment. Additionally, existing approaches that improve robustness to mutation, such as spaced seeds or translated alignment methods, introduce trade-offs in specificity, scalability, or computational complexity. MethodsTo address this gap, we introduce the Min-Frame Transformation (MFT), a deterministic encoding of nucleotide sequences to sequences over a transformed alphabet that preserves the coordinate structure of the original sequence. At each position, the MFT selects a k-mer from a local window according to a fixed global ordering and assigns it a character in the transformed alphabet via a predefined mapping. This process captures local sequence context and can mask the impact of mutations, increasing the likelihood that homologous regions remain detectable as exact matches. The resulting transformed sequences can be indexed using standard string data structures, such as suffix arrays and suffix trees, enabling efficient extraction of MUMs without modifying existing algorithms. ImpactThe MFT is a novel computational approach for improving the robustness of MUM-based seeding for genome alignment by producing longer and more contiguous matches that span a greater fraction of the genome, leading to improved alignment coverage and SNP recall. Altogether, these improvements have the potential to result in improvements for downstream viral genome analysis applications such as phylogenetic inference and transmission analysis. FundingTandy Warnow: NSF grant 2316233 Todd J. Treangen: NSF grants 2126387, 2239114, NIH grants U19-AI144297, P01-AI152999

bioinformatics↗

bioRxiv2026

A time-calibrated phylogeny of hummingbirds supports stepwise diversification in the Andes

Hummingbirds (Trochilidae) represent the second largest avian family, with [~]356 species occupying diverse habitats across the Neotropical and Nearctic regions. Their extensive diversification includes notable adaptations to extreme environments, with nearly one-third of extant taxa belonging to the predominantly high-altitude Coquettes and Brilliants. Although recent work proposed a monophyletic Andean clade uniting these groups, consistent with rapid radiation during Andean orogeny, we find no support for this relationship. Using 2,949 nuclear loci sampled from 47 species spanning all nine major hummingbird clades, we recover a different evolutionary pattern: a stepwise sequence of diversification in which Brilliants are sister to a broader assemblage comprising Coquettes, the genus Patagona, Emeralds, Mountain Gems, and the recently diverged Bees. By assembling complete mitochondrial genomes, we additionally detect significant discordance between nuclear topologies and those derived from the mitogenome and Z chromosome. Analyses of gene-tree heterogeneity show that incomplete lineage sorting is pervasive across the phylogeny, with particularly strong impacts on branches associated with Andean diversification. Divergence-time estimation further indicates that the major Andean radiation--including Brilliants, Coquettes, Emeralds, Bees, and Mountain Gems--originated around [~]14 Ma, with the three younger clades diversifying [~]12 Ma, coinciding with both the mid-Miocene Andean uplift and the mid-Miocene Climate Transition that increased habitat heterogeneity and likely promoted rapid speciation. To support future phylogenomic efforts, we identify a reduced set of highly informative, independent protein-coding loci and present a near-complete species-level phylogeny constrained by our autosomal backbone. Our findings highlight the importance of integrating loci with distinct inheritance modes to detect and interpret phylogenetic incongruence in rapid radiations.

evolutionary biology↗

bioRxiv2026

CAMUS: Scalable Phylogenetic Network Estimation

MotivationPhylogenetic networks are models of evolution that go beyond trees, and so represent reticulate events such as horizontal gene transfer or hybridization, which are frequently found in many taxa. Yet, the estimation of phylogenetic networks is extremely computationally challenging, and nearly all methods are limited to very small datasets with perhaps 10 to 15 species (some limited to even smaller numbers). ResultsWe introduce CAMUS (Constrained Algorithm Maximizing qUartetS), a scalable method for phylogenetic network estimation. CAMUS takes an input constraint tree T as well as a set Q of unrooted quartet trees that it derives from input, and returns a level-1 phylogenetic network N that is built upon T through the addition of edges, in order to maximize the number of quartet trees in Q that are induced in N . We perform a simulation study under the Network Multi-Species Coalescent and show that a simple pipeline using CAMUS provides high accuracy and outstanding speed and scalability, in comparison to two leading methods, PhyloNet-MPL used with a fixed tree and SNaQ. CAMUS is slightly less accurate than PhyloNet-MPL used without a fixed tree, but is much faster (minutes instead of hours) and can complete on inputs with 201 species while PhyloNet-MPL fails to complete on the inputs with more than 51 species. Availability and ImplementationThe source code is available at https://github.com/jsdoublel/camus.

bioinformatics↗

bioRxiv2025

TIPP-SD: A New Method for Species Detection in Microbiomes

In this study, we present TIPP-SD (i.e., TIPP for Species Detection), a new technique for species detection in a microbiome sample. TIPP-SD uses a modified version of TIPP3, which is a recently developed abundance profiling tool based on maximum likelihood phylogenetic placement into marker gene taxonomies. TIPP-SD depends on a parameter (i.e., "thresh-old") for the required support for species detection, thus allowing us to compute a precision-recall curve as we vary this parameter. In comparing the precision-recall curves for TIPP-SD, TIPP3, Kraken2, Bracken, and Metapresence, we find that TIPP-SD improves on the other methods with respect to accuracy under conditions where some species occur in low abundance, or where there is sequencing error. Under easier conditions, TIPP-SD is close to the best of these methods. Finally, although TIPP-SD is slower than Kraken2 and Bracken, it is still fast enough to be used on large datasets.

bioinformatics↗

bioRxiv2024

TIPP3 and TIPP3-fast: Improved Abundance Profiling in Metagenomics

We present TIPP3 and TIPP3-fast, new tools for abundance profiling in metagenomic datasets. Like its predecessor, TIPP2, the TIPP3 pipeline uses a maximum likelihood approach to place reads into labeled taxonomies using marker genes, but it achieves superior accuracy to TIPP2 by enabling the use of much larger taxonomies through improved algorithmic techniques. We show that TIPP3 outperforms leading methods for abundance profiling in two important contexts: when reads come from genomes not already in a public database (i.e., novel genomes) and when reads contain sequencing errors. We also show that TIPP3-fast has slightly lower accuracy than TIPP3, but is still more accurate than other leading methods and uses a small fraction of TIPP3s runtime. Additionally, we highlight the potential benefits of restricting abundance profiling methods to those reads that map to marker genes (i.e., using a filtered marker-gene based analysis), which we show typically improves accuracy. TIPP3 is freely available at https://github.com/c5shen/TIPP3. Author summaryTIPP3 is a new marker gene-based abundance profiling tool that builds on TIPP and TIPP2 with significant enhancements. TIPP3 supports larger reference packages ([~] 55,000 sequences per marker gene) and achieves higher accuracy in abundance profiling, especially with challenging input reads containing sequencing errors or novel genomes. TIPP3 outperforms TIPP2 and other leading methods in profiling accuracy, and its fast version TIPP3-fast is competitive in runtime with the competing methods while being more accurate under challenging conditions. TIPP3 is open-source and available at https://github.com/c5shen/TIPP3.

bioinformatics↗

bioRxiv2024

Advances in Estimating Level-1 Phylogenetic Networks from Unrooted SNPs

We address the problem of how to estimate a phylogenetic network when given SNPs (i.e., single nucleotide polymorphisms, or bi-allelic markers that have evolved under the infinite sites assumption). We focus on level-1 phylogenetic networks (i.e., networks where the cycles are node-disjoint), since more complex networks are unidentifiable. We provide a polynomial time quartet-based method that we prove correct for reconstructing the unrooted topology of any level-1 phylogenetic network N, if we are given a set of SNPs that covers all the bipartitions of N, even if the ancestral state is not known, provided that the cycles are of length at least 5; we also prove that an algorithm developed by Dan Gusfield in JCSS 2005 correctly recovers the unrooted topology in polynomial time in this case. To the best of our knowledge, this is the first result to establish that the unrooted topology of a level-1 network is uniquely recoverable from SNPs without known ancestral states. We also present a stochastic model for DNA evolution, and we prove that the two methods (our quartet-based method and Gusfields method) are statistically consistent estimators of the unrooted topology of the level-1 phylogenetic network. For the case of multi-state homoplasy-free characters, we prove that our quartet-based method correctly constructs the unrooted topology of level-1 networks under the required conditions (all cycles of length at least five), while Gusfields algorithm cannot be used in that condition. These results assume that we have access to an oracle for indicating which sites in the DNA alignment are homoplasy-free, and we show that the methods are robust, under some conditions, to oracle errors.

evolutionary biology↗

bioRxiv2023

Computing Multiple Sequence Alignments given a Constraint Subset Alignment using EMMA

BackgroundAdding sequences into an existing (possibly user-provided) alignment has multiple applications, including updating a large alignment with new data, adding sequences into a constraint alignment constructed using biological knowledge, or computing alignments in the presence of sequence length heterogeneity. Although this is a natural problem, only a few tools have been developed to use this information with high fidelity. ResultsWe present EMMA (Extending Multiple alignments using MAFFT-add) for the problem of adding a set of unaligned sequences into a multiple sequence alignment (i.e., a constraint alignment). EMMA builds on MAFFT-add, which is also designed to add sequences into a given constraint alignment. EMMA improves on MAFFT--add methods by using a divide-and-conquer framework to scale its most accurate version, MAFFT-linsi--add, to constraint alignments with many sequences. We show that EMMA has an accuracy advantage over other techniques for adding sequences into alignments under many realistic conditions and can scale to large datasets with high accuracy (hundreds of thousands of sequences). EMMA is available at https://github.com/c5shen/EMMA. ConclusionsEMMA is a new tool that provides high accuracy and scalability for adding sequences into an existing alignment.

bioinformatics↗

bioRxiv2023

DISCO+QR: Rooting Species Trees in the Presence of GDL and ILS

AO_SCPLOWBSTRACTC_SCPLOWGenes evolve under processes such as gene duplication and loss (GDL), so that gene family trees are multi-copy, as well as incomplete lineage sorting (ILS); both processes produce gene trees that differ from the species tree. The estimation of species trees from sets of gene family trees is challenging, and the estimation of rooted species trees presents additional analytical challenges. Two of the methods developed for this problem are STRIDE (Emms and Kelly, MBE 2017), which roots species trees by considering GDL events, and Quintet Rooting (Tabatabaee et al., ISMB 2022 and Bioinformatics 2022), which roots species trees by considering ILS. We present DISCO+QR, a new method for rooting species trees in the presence of both GDL and ILS. DISCO+QR, operates by taking the input gene family trees and decomposing them into single-copy trees using DISCO (Willson et al., Systematic Biology 2022) and then roots the given species tree using the information in the single-copy gene trees using Quintet Rooting (QR). We show that the relative accuracy of STRIDE and DISCO+QR depend on properties of the dataset (number of species, genes, rate of gene duplication, degree of ILS, and gene tree estimation error), and that each provides advantages over the other under some conditions. Availability: DISCO and QR are available in GitHub. The supplementary materials are available at http://tandy.cs.illinois.edu/discoqr-suppl.pdf.

bioinformatics↗

bioRxiv2022

Statistically Consistent Rooting of Species Trees under the Multi-Species Coalescent Model

Rooted species trees are used in several downstream applications of phylogenetics. Most species tree estimation methods produce unrooted trees and additional methods are then used to root these unrooted trees. Recently, Quintet Rooting (QR) (Tabatabaee et al., ISMB and Bioinformatics 2022), a polynomial-time method for rooting an unrooted species tree given unrooted gene trees under the multispecies coalescent, was introduced. QR, which is based on a proof of identifiability of rooted 5-taxon trees in the presence of incomplete lineage sorting, was shown to have good accuracy, improving over other methods for rooting species trees when incomplete lineage sorting was the only cause of gene tree discordance, except when gene tree estimation error was very high. However, the statistical consistency of QR was left as an open question. Here, we present QR-STAR, a polynomial-time variant of QR that has an additional step for determining the rooted shape of each quintet tree. We prove that QR-STAR is statistically consistent under the multispecies coalescent model. Our simulation study under a variety of model conditions shows that QR-STAR matches or improves on the accuracy of QR. QR-STAR is available in open source form at https://github.com/ytabatabaee/Quintet-Rooting.

bioinformatics↗

bioRxiv2022

BATCH-SCAMPP: Scaling phylogenetic placement methods to place many sequences

Phylogenetic placement, the problem of placing sequences into phylogenetic trees, has been limited either by the number of sequences placed in a single run or by the size of the placement tree. The most accurate scalable phylogenetic placement method with respect to the number of query sequences placed, EPA-ng, has a runtime that scales sublinearly to the number of query sequences. However, larger phylogenetic trees cause an increase in EPA-ngs memory usage, limiting the method to placement trees of up to 10,000 sequences. Our recently designed SCAMPP framework has been shown to scale EPA-ng to larger placement trees of up to 200,000 sequences by building a subtree for the placement of each query sequence. The approach of SCAMPP does not take advantage of EPA-ngs parallel efficiency since it only places a single query for each run of EPA-ng. Here we present BATCH-SCAMPP, a new technique that overcomes this barrier and enables EPA-ng and other phylogenetic placement methods to scale to ultra-large backbone trees and many query sequences. BATCH-SCAMPP is freely available at https://github.com/ewedell/BSCAMPP_code.

bioinformatics↗

bioRxiv2022

WITCH-NG: Efficient and Accurate Alignment of Datasets with Sequence Length Heterogeneity

Multiple sequence alignment (MSA) is a basic part of many bioinformatics pipelines, including in phylogeny estimation, prediction of structure for both RNAs and proteins, and metagenomic sequence analysis. Yet many sequence datasets exhibit substantial sequence length heterogeneity, both because of large insertions and deletions (indels) in the evolutionary history of the sequences and the inclusion of sequencing reads or incompletely assembled sequences in the input. A few methods have been developed that can be highly accurate in aligning datasets with sequence length heterogeneity, with UPP (Nguyen et al., 2015) one of the first methods to achieve good accuracy, and WITCH (Shen et al., Bioinformatics 2021) an improvement on UPP for accuracy, In this paper, we show how we can speed up WITCH. Our improvement includes replacing a critical step in WITCH (currently performed using a heuristic search) by a polynomial time exact algorithm using Smith-Waterman. Our new method, WITCH-NG (i.e., "next generation WITCH", pronounced "witching") achieves the same accuracy but is substantially faster. WITCH-NG is available in open source form at https://github.com/RuneBlaze/WITCH-NG.

bioinformatics↗

bioRxiv2022

HMMerge: an Ensemble Method for Improving Multiple Sequence Alignment

Despite advances in method development for multiple sequence alignment over the last several decades, the alignment of datasets exhibiting substantial sequence length heterogeneity, especially when the input sequences include very short sequences (either as a result of sequencing technologies or of large deletions during evolution) remains an inadequately solved problem. We present HMMerge, a method to compute an alignment of datasets exhibiting high sequence length heterogeneity, or to add short sequences into a given "backbone" alignment. HMMerge builds on the technique from its predecessor alignment methods, UPP and WITCH, which build an ensemble of HMMs for the backbone alignment and add the remaining sequences into the backbone alignment using the ensemble. HMMerge differs from UPP and WITCH by building a new HMM for each query sequence: it uses a novel ensemble approach to combine the HMMs, each weighted by the probability of generating the query sequence, into a single HMM. Then it applies the Viterbi algorithm to add the query sequence into the backbone alignment. We show that using this "merged" HMM provides better accuracy than the current approach in UPP and matches or improves on WITCH for adding short sequences into backbone alignments. HMMerge is freely available at https://github.com/MinhyukPark/HMMerge.

bioinformatics↗

bioRxiv2022

Fast and Accurate Species Trees from Weighted Internode Distances

Species tree estimation is a basic step in many biological research projects, but is complicated by the fact that gene trees can differ from the species tree due to processes such as incomplete lineage sorting (ILS), gene duplication and loss (GDL), and horizontal gene transfer (HGT), which can cause different regions within the genome to have different evolutionary histories (i.e., "gene tree heterogeneity"). One approach to estimating species trees in the presence of gene tree heterogeneity resulting from ILS operates by computing trees on each genomic region (i.e., computing "gene trees") and then using these gene trees to define a matrix of average internode distances, where the internode distance in a tree T between two species x and y is the number of nodes in T between the leaves corresponding to x and y. Given such a matrix, a tree can then be computed using methods such as neighbor joining. Methods such as ASTRID and NJst (which use this basic approach) are provably statistically consistent, very fast (low degree polynomial time) and have had high accuracy under many conditions that makes them competitive with other popular species tree estimation methods. In this study, inspired by the very recent work of weighted ASTRAL, we present weighted ASTRID, a variant of ASTRID that takes the branch uncertainty on the gene trees into account in the internode distance. Our experimental study evaluating weighted ASTRID shows improvements in accuracy compared to the original (unweighted) ASTRID while remaining fast. Moreover, weighted ASTRID shows competitive accuracy against weighted ASTRAL, the state of the art. Thus, this study provides a new and very fast method for species tree estimation that improves upon ASTRID, has comparable accuracy with the state of the art while remaining much faster. Weighted ASTRID is available at https://github.com/RuneBlaze/internode.

evolutionary biology↗

bioRxiv2022

Exploring Trade-offs in Scalable Phylogenetic Placement Methods

Phylogenetic placement is the problem of placing "query" sequences into an existing tree (called a "backbone tree"), and is useful in both microbiome analysis and to update large evolutionary trees. The most accurate phylogenetic placement method to date is the maximum likelihood-based method pplacer, which uses RAxML to estimate numeric parameters on the backbone tree and then adds the given query sequence to the edge that maximizes the probability that the resulting tree generates the query sequence. Unfortunately, pplacer fails to return valid outputs on many moderately large datasets, and so is limited to backbone trees with at most [~]10,000 leaves. In TCBB 2022, Wedell et al. introduced SCAMPP, a technique to enable pplacer to run on larger backbone trees. SCAMPP operates by finding a small "placement subtree" specific to each query sequence, within which the query sequence are placed using pplacer. That approach matched the scalability and accuracy of APPLES-2, the previous most scalable method. In this study, we explore a different aspect of pplacers strategy: the technique used to estimate numeric parameters on the backbone tree. We confirm anecdotal evidence that using FastTree instead of RAxML to estimate numeric parameters on the backbone tree enables pplacer to scale to much larger backbone trees, almost (but not quite) matching the scalability of APPLES-2 and pplacer-SCAMPP. We then evaluate the combination of these two techniques - SCAMPP and the use of FastTree. We show that this combined approach, pplacer-SCAMPP-FastTree, has the same scalability as APPLES-2, improves on the scalability of pplacer-FastTree, and achieves better accuracy than the comparably scalable methods. Availability: https://github.com/gillichu/PLUSplacer-taxtastic.

bioinformatics↗

bioRxiv2022

eMAFFTadd: scaling MAFFT-linsi-add to large datasets

Multiple sequence alignment is essential for many biological downstream analyses, but accurate alignment of large datasets, especially those exhibiting high rates of evolution or sequence length heterogeneity, is still unsolved. We present SALMA, a new multiple sequence alignment that provides high accuracy and scalability, even for datasets exhibiting high rates of evolution and great sequence length heterogeneity that arises from evolutionary processes. Like some prior methods (e.g., UPP, WITCH, and MAFFT-sparsecore), SALMA operates in two distinct stages: the first stage computes a "backbone alignment" for a subset of the sequences, and the second stage adds the remaining sequences into the backbone alignment. The main novelty in SALMA is how it adds the remaining ("query") sequences into the backbone alignment. For this step, which we refer to as SALMA-add, we use divide-and-conquer to scale MAFFT-linsi--add to enable it to add sequences into large backbone alignments. We show that SALMA-add has an advantage over other sequence-adding techniques for many realistic conditions and can scale to very large datasets with high accuracy (hundreds of thousands of sequences). We also show that SALMA is one of the most accurate compared to standard alignment methods. Our open source software for SALMA is available at https://github.com/c5shen/SALMA.

bioinformatics↗

bioRxiv2022

UPP2: Fast and Accurate Alignment Estimation of Datasets with Fragmentary Sequences

MotivationMultiple sequence alignment (MSA) is a basic step in many bioinformatics pipelines. However, achieving highly accurate alignments on large datasets, especially those with sequence length heterogeneity, is a challenging task. UPP (Ultra-large multiple sequence alignment using Phylogeny-aware Profiles) is a method for MSA estimation that builds an ensemble of Hidden Markov Models (eHMM) to represent an estimated alignment on the full length sequences in the input, and then adds the remaining sequences into the alignment using selected HMMs in the ensemble. Although UPP provides good accuracy, it is computationally intensive on large datasets. ResultsWe present UPP2, a direct improvement on UPP. The main advance is a fast technique for selecting HMMs in the ensemble that allows us to achieve the same accuracy as UPP but with greatly reduced runtime. We show UPP2 produces more accurate alignments compared to leading MSA methods on datasets exhibiting substantial sequence length heterogeneity, and is among the most accurate otherwise. Availabilityhttps://github.com/gillichu/sepp Contactwarnow@illinois.edu

bioinformatics↗

bioRxiv2021

Scalable Species Tree Inference with External Constraints

Species tree inference under the multi-species coalescent (MSC) model is a basic step in biological discovery. Despite the developments in recent years of methods that are proven statistically consistent and that have high accuracy, large datasets create computational challenges. Although there is generally some information available about the species trees that could be used to speed up the estimation, only one method-ASTRAL-J, a recent development in the ASTRAL family of methods-is able to use this information. Here we describe two new methods, NJst-J and FASTRAL-J, that can estimate the species tree given partial knowledge of the species tree in the form of a non-binary unrooted constraint tree.. We show that both NJst-J and FASTRAL-J are much faster than ASTRAL-J and we prove that all three methods are statistically consistent under the multi-species coalescent model subject to this constraint. Our extensive simulation study shows that both FASTRAL-J and NJst-J provide advantages over ASTRAL-J: both are faster (and NJst-J is particularly fast), and FASTRAL-J is generally at least as accurate as ASTRAL-J. An analysis of the Avian Phylogenomics project dataset with 48 species and 14,446 genes presents additional evidence of the value of FASTRAL-J over ASTRAL-J (and both over ASTRAL), with dramatic reductions in running time (20 hours for default ASTRAL, and minutes or seconds for ASTRAL-J and FASTRAL-J, respectively). AvailabilityFASTRAL-J and NJst-J are available in open source form at https://github.com/RuneBlaze/FASTRAL-constrained and https://github.com/RuneBlaze/NJst-constrained. Locations of the datasets used in this study and detailed commands needed to reproduce the study are provided in the supplementary materials at http://tandy.cs.illinois.edu/baqiao-suppl.pdf.

evolutionary biology↗

bioRxiv2021

Comparing Methods for Species Tree Estimation With Gene Duplication and Loss

Species tree inference from gene trees is an important part of biological research. One confounding factor in estimating species trees is gene duplication and loss which can lead to gene trees with multiple copies of the same gene. In recent years there have been several new methods developed to address this problem that have substantially improved on earlier methods; however, the best performing methods (ASTRAL-Pro, ASTRID-multi, and FastMulRFS) have not yet been directly compared. In this study, we compare ASTRAL-Pro, ASTRID-multi, and FastMulRFS under a wide variety of conditions. Our study shows that while all three have very good accuracy, nearly the same under many conditions, ASTRAL-Pro and ASTRID-multi are more reliably accurate than FastMuLRFS, and that ASTRID-multi is often faster than ASTRAL-Pro. The datasets generated for this study are freely available in the Illinois Data Bank at https://databank.illinois.edu/datasets/IDB-2418574

evolutionary biology↗