2 releases
0.1.1 | Jun 19, 2024 |
---|---|
0.1.0 | Jun 11, 2024 |
#249 in Biology
475KB
368 lines
🔪🧅 Diced ![Star me](https://img.shields.io/github/stars/althonos/mincer?style=social&label=Star&maxAge=3600)
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, and is much faster. The Diced implementation is available as a Rust library for convenience.
This is the Python version, there is a Rust crate 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.
- single dependency: Pyrodigal is distributed as a Python package, so you can add it as a dependency to your project, and stop worrying about the Prodigal binary being present on the end-user machine.
- 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 asRc<str>
orArc<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, thememchr
crate can be used as a fast SIMD-capable implementation of thememmem
function.
💡 Example
Diced supports any sequence in string format.
import Bio.SeqIO
import diced
record = Bio.SeqIO.read("diced/tests/data/Aquifex_aeolicus_VF5.fna", "fasta")
sequence = str(record.seq)
for crispr in diced.scan(sequence):
print(
crispr.start,
crispr.end,
len(crispr.repeats),
crispr.repeats[0],
)
💭 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
- 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.
- Boyer, R. S. and & Moore, J. S. (1977). 'A fast string searching algorithm'. Commun. ACM 20, 10 762–772. doi:10.1145/359842.359859
- Crochemore, M. & Perrin, D. (1991). 'Two-way string-matching'. J. ACM 38, 3, 650–674. doi:10.1145/116825.116845
Dependencies
~5–11MB
~75K SLoC