dada2-rs 🧬

Important

ARCHIVED REPOSITORY This repository is now archived and is no longer actively maintained, as other Rust implementations of DADA2 have already been developed.

dada2-rs is a high-performance, parallelized bioinformatic toolkit designed to recreate the core sequence denoising, error-learning, and amplicon processing capabilities of the popular R/C++ package DADA2 (Divisive Amplicon Denoising Algorithm 2) in pure, safe Rust.

By leveraging Rust's zero-cost abstractions, memory safety guarantees, and robust parallel programming ecosystem (rayon), dada2-rs delivers substantial speedups and memory footprint reductions for massive-scale amplicon sequencing studies (e.g., PacBio, Illumina, and Oxford Nanopore datasets).

---

🚀 Key Features & Pipeline Stages

• Zero-Copy FASTQ/FASTA Parsing: Low-overhead sequence ingestion of uncompressed or gzip-compressed files via needletail.
• Quality Filtering & Trimming (filterAndTrim): 3' quality score trimming, expected error ($EE$) thresholding, ambiguous base (N) filtering, and synchronized output in uncompressed or Gzip formats.
• Dereplication (derepFastq): Collapses identical reads into unique sequence abundances with positional quality score tracking matching R DADA2's derep-class.
• Iterative Error Learning (learnErrors): Employs an Expectation-Maximization loop to fit and normalize transition error probability matrices. Integrates Cleveland's robust C-based LOWESS scatterplot smoothing algorithm via FFI.
• Divisive Clustering Core (dada): budget budding, sequence shuffling, and exact Poisson probability calculations. Performance-tuned with:
  • Alignment Memoization (Caching): Reuses ends-free Needleman-Wunsch alignment outputs across EM iterations and expectations, bypassing redundant dynamic programming computations.
  • 5-mer Distance Pruning: Bypasses full alignments for obviously divergent sequences exceeding the 0.42 k-mer distance threshold.
• Paired-End Merging (mergePairs): Pairs forward and reverse ASVs by aligning overlapping boundaries, calculating consensus quality, and resolving mismatches.
• Multi-Sample Tabulation (makeSequenceTable): Generates 2D sample-by-ASV abundance matrices and outputs standard TSV tables.
• De Novo Chimera Removal (removeBimeraDenovo): Identifies PCR artifacts in linear time using a prefix-suffix index search across non-chimeric parent lists.
• Naive Bayesian Taxonomic Classifier (assignTaxonomy): RDP-style classifier using 8-mer conditional probabilities and multithreaded bootstrap resampling for robust taxonomic assignments.
• Native Language Bindings (PyO3): Full pipeline wrapped into a compiled native Python library (dada2_rs.so).

---

📦 Directory and Architecture Overview

The crate is structured around highly optimized modular components located in the src/ directory:

Module	File	Description
Models	models.rs	Pipeline data structures (DadaRecord, UniqueRecord, Derep, etc.).
I/O Parser	io.rs	Zero-copy stream parser supporting FASTQ and FASTA files.
Filtering	filter.rs	Quality score trimming, error constraints, and file compression.
Dereplication	derep.rs	Read collapsing and consensus quality aggregation.
K-Mer Metrics	kmers.rs	5-mer vector profiles and k-mer distance scoring.
Sequence Alignment	align.rs	Banded ends-free Needleman-Wunsch alignment with homopolymer discounts.
Divisive Clustering	cluster.rs	Cluster budding and shuffling with memoized caching and 5-mer pruning.
Error Learning	learn.rs	EM loop incorporating LOWESS regression via FFI.
Read Pairing	merge.rs	Overlap alignment and pairing of forward and reverse ASVs.
Tabulation	table.rs	2D sample-by-ASV abundance grid tabulation.
Chimera Filtering	chimera.rs	PCR bimera parent-offspring prefix-suffix search.
Taxonomy	taxonomy.rs	Naive Bayesian RDP-style classifier.
Python Bindings	py_bindings.rs	PyO3 bindings wrapping all core biological phases.

---

🛠️ Installation & Building

Prerequisites

You need the Rust toolchain and GCC (for the LOWESS C-routine compiler). If you do not have Rust, install it via rustup.rs:

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Compiling from Source

Clone the repository and compile with the Python feature enabled:

git clone https://github.com/dgutierrezcastillo/dada2-rs.git
cd dada2-rs
cargo build --release --features python

The native library will be compiled under target/release/libdada2_rs.so (or .dylib / .dll), which can be symlinked as dada2_rs.so for import inside Python environments.

---

🧪 Verification & Testing

Verify correctness and pipeline integration by executing the sequential unit test suite:

cargo test --features python

Running the CLI Showcase

Execute stand-alone denoising on sample sequences using the command line interface:

cargo run --release --features python -- /path/to/sequences.fasta

---

📄 License

This project is licensed under the GNU Lesser General Public License version 3.0 (LGPL-3.0) - see the LICENSE file for details. This license choice ensures compatibility with the original upstream R DADA2 project, which is also distributed under the LGPL-3.0.

---

📚 Citations & References

If you use these algorithms or ideas in your research, please cite the original DADA2 literature:

1. DADA2 Method Paper:

   Callahan BJ, McMurdie PJ, Rosen MJ, Han AW, Johnson AJ, Holmes SP (2016). DADA2: High-resolution sample inference from Illumina amplicon data. Nature Methods, 13(7), 581-583. doi:10.1038/nmeth.3869

2. Denoising Core Algorithm:

   Rosen MJ, Callahan BJ, Fisher DS, Holmes SP (2012). Denoising PCR-amplified metagenomic data. BMC Bioinformatics, 13(1), 283. doi:10.1186/1471-2105-13-283