Motivation: Taxonomic classification is at the core of environmental DNA analysis. When a phylogenetic tree can be built as a prior hypothesis to such classification, phylogenetic placement (PP) provides the most informative type of classification because each query sequence is assigned to its putative origin in the tree. This is useful whenever precision is sought (e.g. in diagnostics). However, likelihood-based PP algorithms struggle to scale with the ever-increasing throughput of DNA sequencing.
Results: We have developed RAPPAS (Rapid Alignment-free Phylogenetic Placement via Ancestral Sequences) which uses an alignment-free approach, removing the hurdle of query sequence alignment as a preliminary step to PP. Our approach relies on the precomputation of a database of k-mers that may be present with non-negligible probability in relatives of the reference sequences. The placement is performed by inspecting the stored phylogenetic origins of the k-mers in the query, and their probabilities. The database can be reused for the analysis of several different metagenomes. Experiments show that the first implementation of RAPPAS is already faster than competing likelihood-based PP algorithms, while keeping similar accuracy for short reads. RAPPAS scales PP for the era of routine metagenomic diagnostics.
Availability And Implementation: Program and sources freely available for download at https://github.com/blinard-BIOINFO/RAPPAS.
Supplementary Information: Supplementary data are available at Bioinformatics online.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1093/bioinformatics/btz068 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Alignment-Free Viral Sequence Classification at Scale.
bioRxiv
December 2024
Centre for Epidemic Response and Innovation (CERI), School of Data Science and Computational Thinking, Stellenbosch University, Stellenbosch, South Africa.
Background: The rapid increase in nucleotide sequence data generated by next-generation sequencing (NGS) technologies demands efficient computational tools for sequence comparison. Alignment-based methods, such as BLAST, are increasingly overwhelmed by the scale of contemporary datasets due to their high computational demands for classification. This study evaluates alignment-free (AF) methods as scalable and rapid alternatives for viral sequence classification, focusing on identifying techniques that maintain high accuracy and efficiency when applied to extremely large datasets.
View Article and Find Full Text PDFSHARK enables sensitive detection of evolutionary homologs and functional analogs in unalignable and disordered sequences.
Proc Natl Acad Sci U S A
October 2024
Max Planck Institute of Molecular Cell Biology and Genetics, Dresden 01307, Germany.
Intrinsically disordered regions (IDRs) are structurally flexible protein segments with regulatory functions in multiple contexts, such as in the assembly of biomolecular condensates. Since IDRs undergo more rapid evolution than ordered regions, identifying homology of such poorly conserved regions remains challenging for state-of-the-art alignment-based methods that rely on position-specific conservation of residues. Thus, systematic functional annotation and evolutionary analysis of IDRs have been limited, despite them comprising ~21% of proteins.
View Article and Find Full Text PDFAlignment-free analysis of sequences has revolutionized the high-throughput processing of sequencing data within numerous bioinformatics pipelines. Hashing k-mers represents a common function across various alignment-free applications, serving as a crucial tool for indexing, querying, and rapid similarity searching. More recently, spaced seeds, a specialized pattern that accommodates errors or mutations, have become a standard choice over traditional k-mers.
View Article and Find Full Text PDFRapid alignment-free bacteria identification via optical scattering with LEDs and YOLOv8.
Sci Rep
September 2024
School of Materials Science and Innovation, Faculty of Science, Mahidol University, Nakhon Pathom, 73170, Thailand.
Rapid and accurate bacterial identification is essential for timely treatment of infections like sepsis. While traditional methods are reliable, they lack speed, and advanced molecular techniques often suffer from cost and complexity. The bacterial detection technology based on optical scattering system offers a rapid, label-free alternative but traditionally relies on complex lasers and analysis.
View Article and Find Full Text PDFMaptcha: an efficient parallel workflow for hybrid genome scaffolding.
BMC Bioinformatics
August 2024
School of Electrical Engineering and Computer Science, Washington State University, Pullman, WA, 99164, USA.
Background: Genome assembly, which involves reconstructing a target genome, relies on scaffolding methods to organize and link partially assembled fragments. The rapid evolution of long read sequencing technologies toward more accurate long reads, coupled with the continued use of short read technologies, has created a unique need for hybrid assembly workflows. The construction of accurate genomic scaffolds in hybrid workflows is complicated due to scale, sequencing technology diversity (e.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!