Crate papasmurf 

🧙‍♂️ PAPASMURF

A Platform-Accelerated Package for Alignment-free SMURF analysis.

🗺️ Overview

SMURF (Short MUltiple Region Framework) is a method proposed by Fuks et al.[1] in 2018 for taxonomic profiling of 16S sequencing data. It uses several PCR-amplified regions inside the 16S rRNA gene to reach high taxonomic resolution despite the use of short read sequencing.

PAPASMURF is a Rust reimplementation of the SMURF method from scratch. It does not aim at being a 1-to-1 reimplementation of the original MATLAB implementation, but allows more control over the parameters used in the original to support sequencing data of lesser quality.

This is the Rust version, there is a Python package available as well.

📋 Features

• primer profiles: The primers defining each regions are converted into a Position-Specific Scoring Matrix (PSSM) to allow for the fast extraction of 16S gene regions when building the database.
• sparse matrices: The mapping and reconstruction algorithms are entirely implemented with sparse matrices, reducing the memory consumption and accelerating dot-product computations[2].
• fast k-mer matching: The full-scan k-mer matching in the mapping phase is implemented using SIMD to compare each read to all the k-mers in a database. While of $O(kn)$ runtime complexity, this is actually faster than using a dedicated data structure (such as a trie) to recover k-mers with mismatches.

💭 Feedback

⚠️ Issue Tracker

Found a bug ? Have an enhancement request ? Head over to the GitHub issue tracker if you need to report or ask something. If you are filing in on a bug, please include as much information as you can about the issue, and try to recreate the same bug in a simple, easily reproducible situation.

📋 Changelog

This project adheres to Semantic Versioning and provides a changelog in the Keep a Changelog format.

⚖️ License

This library is provided under the open-source GPLv3 license.

This project is in no way not affiliated, sponsored, or otherwise endorsed by the original SMURF authors. It was developed by Martin Larralde during his PhD project at the European Molecular Biology Laboratory in the Zeller team with support and testing from Fabian Springer.

All brand names and product names used in this material are trademarks or registered trademarks of their respective owners. The author/owner is not affiliated with, endorsed by, or sponsored by any product, organization, or company mentioned. Smurf is a registered trademark of Studio Peyo S.A.

📚 References

• [1] Fuks, Garold, Michael Elgart, Amnon Amir, Amit Zeisel, Peter J. Turnbaugh, Yoav Soen, and Noam Shental. ‘Combining 16S RRNA Gene Variable Regions Enables High-Resolution Microbial Community Profiling’. Microbiome 6 (26 January 2018): 17. doi:10.1186/s40168-017-0396-x.
• [2] Gustavson, Fred G. ‘Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition’. ACM Transactions on Mathematical Software 4, no. 3 (September 1978): 250–69. doi:10.1145/355791.355796.

Modules

io

matrix

Various formats of sparse and dense matrices.

Structs

Builder

A builder for incremental construction of a new database.

Database

A database storing forward and backward k-mers for each region.

Mapper

A helper for mapping 16S reads from a sample to a k-mer database.

MapperResult

The results of a database mapping.

Paired

A pair of values for paired-end reads.

Primer

A sequencing primer marking the boundary of a 16S region.

Region

A single 16S region from a database, defined by a pair of primers.

Enums

Error