🔪🧅 Diced

A Rust re-implementation of the MinCED algorithm to Detect Instances of CRISPRs in Environmental Data.

🗺️ Overview

MinCED is a method developed by Connor T. Skennerton to identify Clustered Regularly Interspaced Short Palindromic Repeats (CRISPRs) in isolate and metagenomic-assembled genomes. It was derived from the CRISPR Recognition Tool [1]. It uses a fast scanning algorithm to identify candidate repeats, combined with an extension step to find maximally spanning regions of the genome that feature a CRISPR repeat.

Diced is a Rust reimplementation of the MinCED method, using the original Java code as a reference. It produces exactly the same results as MinCED, corrects some bugs (minced#35), and is much faster. The Diced implementation is available as a Rust library for convenience.

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

📋 Features

• library interface: The Rust implementation is written as library to facilitate reusability in other projects. It is used to implement a Python library using PyO3 to generate a native extension.
• zero-copy: The Scanner which iterates over candidate CRISPRs is zero-copy if provided with a simple &str reference, but it also supports data behind smart pointers such as Rc<str> or Arc<str>.
• fast string matching: The Java implementation uses a handwritten implementation of the Boyer-Moore algorithm[2], while the Rust implementation uses the str::find method of the standard library, which implements the Two-way algorithm[3]. In addition, the memchr crate can be used as a fast SIMD-capable implementation of the memmem function.

💡 Example

Diced supports any sequence in string format.

let mut reader = std::fs::File::open("tests/data/Aquifex_aeolicus_VF5.fna")
    .map(std::io::BufReader::new)
    .map(noodles_fasta::Reader::new)
    .unwrap();
let record = reader.records().next().unwrap().unwrap();
let seq = std::str::from_utf8(record.sequence().as_ref()).unwrap();

for crispr in diced::Scanner::new(&seq) {
    println!("{} to {}: {} repeats", crispr.start(), crispr.end(), crispr.len());
    for repeat in crispr.repeats() {
        println!(" - at {}: {}", repeat.start(), repeat.as_str());
    }
}

💭 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, or later. The code for this implementation was derived from the MinCED source code, which is available under the GPLv3 as well.

This project is in no way not affiliated, sponsored, or otherwise endorsed by the original MinCED authors. It was developed by Martin Larralde during his PhD project at the Leiden University Medical Center in the Zeller team.

📚 References

• [1] Bland, C., Ramsey, T. L., Sabree, F., Lowe, M., Brown, K., Kyrpides, N. C., & Hugenholtz, P. (2007). 'CRISPR recognition tool (CRT): a tool for automatic detection of clustered regularly interspaced palindromic repeats'. BMC bioinformatics, 8, 209. PMID:17577412 doi:10.1186/1471-2105-8-209.

• [2] Boyer, R. S. and & Moore, J. S. (1977). 'A fast string searching algorithm'. Commun. ACM 20, 10 762–772. doi:10.1145/359842.359859

• [3] Crochemore, M. & Perrin, D. (1991). 'Two-way string-matching'. J. ACM 38, 3, 650–674. doi:10.1145/116825.116845