Robert C. Edgar

Protein structure databases have grown from thousands of experimentally determined structures to hundreds of millions of AI-predicted models, creating an urgent need for search methods that combine high accuracy with practical scalability. Here, I present the third generation of Reseek, a protein structure search algorithm achieving the highest overall accuracy (median rank 1) according to diverse metrics among tested methods including DALI, Foldseek and TM-align. Improved accuracy is obtained by parallel sequence alignment of many discrete alphabets capturing primary, secondary and tertiary features, giving a combined space of ∼ 10 ²² possible states. Separate statistical models are optimized for family, superfamily and fold discrimination, respectively, revealing distinct combinations of features that characterize each level. Hundreds of query structures can be searched a against a multimillion-structure database on a server computer in minutes, making large-scale structure search at state-of-the-art accuracy practical on commodity hardware.

Multiple sequence alignment (MSA) is a key step in phylogenetic analysis and is prone to error. Unfortunately, algorithms that remove likely alignment errors from MSAs sometimes also remove informative residues, making phylogenetic tree inference worse. Here we present a novel MSA cleaning algorithm based on consensus between MSAs using a range of Hidden Markov Models and guide trees, named CLOAK (CLeaning On the basis of Alignment C(K)onsensus). CLOAK is a gentle filter, with a low false positive rate for removal from MSAs according to the BALiBASE benchmarks, while still removing a significant fraction of likely alignment errors. Gentle vs. stringent MSA filtering methods are appropriate for different tasks. We assess methods based on their ability to bring the gene trees of single copy orthologs closer to the accepted species tree. Amino acid substitution models trained on filtered MSAs improve gene tree inference, with stricter filtering methods providing the biggest model improvements. In contrast, it is gentler filtering of single gene MSAs that provides additional improvements to gene tree inference, with CLOAK performing best.

The rapid rate of virus discovery renders manual curation by taxonomy experts increasingly impractical, creating a need for reliable software that can reproducibly assign viral contigs to taxa at all fifteen ranks of the virus taxonomy. We led an open community challenge for the computational taxonomic classification of viruses and assembled a dataset of virus sequences combining expert-curated and metagenomic sequences. Seventeen teams contributed a total of thirty-four automated, fully reproducible classification pipelines. Most tools correctly assigned viruses belonging to established species, genera, or families, but viruses that are unclassified at those lower ranks remain challenging. This study provides datasets, open-source software, novel approaches, and recommendations to benchmark computational taxonomic classification of viruses, and support organizing the many viruses discovered in big omics data.

Multiple Sequence Alignment (MSA) is a key step in phylogenetic analysis, and is prone to error. Unfortunately, algorithms that remove likely alignment errors from MSAs sometimes also remove informative residues, making phylogenetic tree inference worse. Here we present a novel MSA cleaning algorithm based on consensus between MSAs using a range of Hidden Markov Models and guide trees, named CLOAK ( CL eaning O n the basis of A lignment C( K )onsensus). CLOAK is a gentle filter, with a low false positive rate for removal from MSAs according to the BALiBASE benchmarks, while still removing a significant fraction of likely alignment errors. Gentle vs. stringent MSA filtering methods are appropriate for different tasks. We assess methods based on their ability to bring the gene trees of single copy orthologs closer to the accepted species tree. Amino acid substitution models trained on filtered MSAs improve gene tree inference, with stricter filtering methods providing the biggest model improvements. In contrast, it is gentler filtering of single gene MSAs that provides additional improvements to gene tree inference, with CLOAK performing best.

Machine learning has generated millions of high-quality predicted protein structures, creating a need for computationally efficient structure search algorithms and robust estimates of statistical significance at this scale. We show that unrelated proteins have a universal tendency towards convergent evolution of secondary and tertiary motifs, causing an excess of high-scoring false positive alignments. We investigate popular structure search and alignment algorithms, finding that previous methods routinely overestimate significance by up to six orders of magnitude. To address these issues, and to accommodate recent innovations in search algorithm design, we describe a novel method for estimating statistical significance. We show that its E -values are accurate, scale successfully with database size, and are robust against the (generally unknown) diversity of folds in the database. We implement our approach in an online structure search service based on Reseek at https://reseek.online .

Recent breakthroughs in protein fold prediction from amino acid sequences have unleashed a deluge of new structures, presenting new opportunities and challenges to bioinformatics. Reseek is a novel protein structure alignment algorithm based on sequence alignment where each residue in the protein backbone is represented by a letter in a “mega-alphabet” of 85,899,345,920 (∼10¹¹) distinct states. Reseek achieves substantially improved sensitivity to remote homologs compared to state-of-the-art methods including DALI, TMalign and Foldseek, with comparable speed to Foldseek, the fastest previous method. Scaling to large databases of AI-predicted folds is analyzed. Foldseek E-values are shown to be under-estimated by several orders of magnitude, while Reseek E-values are in good agreement with measured error rates. https://github.com/rcedgar/reseek. Supplementary data are available at Bioinformatics online.

Protein multiple alignment is an essential step in many bioinformatics analysis such as phylogenetic tree estimation, HMM construction and critical residue identification. Structure is conserved between distantly-related proteins where amino acid similarity is weak or undetectable, suggesting that structure-informed sequence alignments might offer advantages over alignments constructed from amino acid sequences alone. The advent of the AI folding era has unleashed millions of high-quality predicted structures, motivating the development and assessment of scalable multiple structure alignment (MStA) methods. Here, we describe Muscle-3D, a new MStA algorithm combining a rich sequence representation of structure context, the Reseek “mega-alphabet”, with state-of-the art alignment techniques from Muscle5 including a posterior decoding pair-HMM, consistency transformation, iterative refinement and ensemble construction. We show that Muscle-3D readily scales to thousands of structures. Comparative validation on several benchmark datasets using different quality metrics shows Muscle-3D to be among the higher-scoring methods, but we find that algorithm rankings from different metrics disagree despite low P-values according to the Wilcoxon rank-sum test. We suggest that these conflicts arise from the inherently fuzzy nature of structural alignment, and argue that a universal standard of MStA accuracy is not possible in principle. We describe contact map profiles for visualizing variation in inter-residue distances, and introduce a novel measure of local conformation similarity, LDDT-muw. Muscle-3D software is available at https://github.com/rcedgar/muscle .

[This corrects the article DOI: 10.7717/peerj.14055.].

The breadth of life’s diversity is unfathomable, but public nucleic acid sequencing data offers a window into the dispersion and evolution of genetic diversity across Earth. However the rapid growth and accumulation of sequence data have outpaced efficient analysis capabilities. The largest collection of freely available sequencing data is the Sequence Read Archive (SRA), comprising 27.3 million datasets or 5 × 10 ¹⁶ basepairs. To realize the potential of the SRA, we constructed Logan, a massive sequence assembly transforming short reads into long contigs and compressing the data over 100-fold, enabling highly efficient petabase-scale analysis. We created Logan-Search, a k -mer index of Logan for free planetary-scale sequence search, returning matches in minutes. We used Logan contigs to identify > 200 million plastic-degrading enzyme homologs, and validate novel enzymes with catalytic activities exceeding current reference standards. Further, we vastly expand the known diversity of proteins (30-fold over UniRef50), plasmids (22-fold over PLSDB), P4 satellites (4.5-fold), and the recently described Obelisk RNA elements (3.7-fold). Logan also enables ecological and biomedical data mining, such as global tracking of antimicrobial resistance genes and the characterization of viral reactivation across millions of human BioSamples. By transforming the SRA, Logan democratizes access to the world’s public genetic data and opens frontiers in biotechnology, molecular ecology, and global health.

Recent breakthroughs in protein fold prediction from amino acid sequences have unleashed a deluge of new structures, raising new opportunities for expanding insights into the universe of proteins and pursuing practical applications in bio-engineering and therapeutics while also presenting new challenges to protein search and analysis algorithms. Here, I describe Reseek, a protein alignment algorithm which improves sensitivity in protein homolog detection compared to state-of-the-art methods including DALI, TM-align and Foldseek, with improved speed over Foldseek, the fastest previous method. Reseek is based on alignment of sequences where each residue in the protein backbone is represented by a letter in a novel “mega-alphabet” of 85,899,345,920 ( ∼ 10 ¹¹ ) distinct states. Code is available at https://github.com/rcedgar/reseek .