LT FM-Index

lt-fm-index is library for locate and count nucleotide sequence (ATGC) string.
lt-fm-index using k-mer lookup table (As you noticed, LT stands for lookup table).

Description

• Fm-index is a data structure used for pattern matching.
• K-mer lookup table(KLT) is precalculated count table containing all kmer occurrences.
• With KLT, you can find the first k-mer pattern at once.
• Supports two types of text.
  • FmIndexOn supports a text with only genetic nucleotide sequence (ACGT).
  • FmIndexNn supports a text containing non-nucleotide sequence.
  • FmIndexNn treats all non-nucleotide as the same character.
• CAVEAT! This crate is not stable. Functions can be changed without notice.

Features

• Fm-index using KLT with specified k-mer size.
• Suffix array compression with sampling ratio.
• BWT and suffix array are generated using libdivsufsort library.
• BWT(burrow wheeler transformed) string and occurrence array (OA) are aligned in one block of 64 strings.
• There are two main functions.
  • count: Count the number of patterns in the text
  • locate: Locate pattern index in text (KLT can be specified to enable or not)

Examples

Use FmIndexConfig to generate FmIndex

```rust use ltfmindex::FmIndexConfig;

// (1) Define configuration for fm-index let fmiconfig = FmIndexConfig::new() .setkmerlookuptable(8) .setsuffixarraysamplingratio(4) .containnonnucleotide(); // Default is true

// (2) Generate fm-index with text let text = b"CTCCGTACACCTGTTTCGTATCGGANNN".tovec(); let fmindex = fmiconfig.generatefmindex(text); // text is consumed

// (3) Match with pattern let pattern = b"TA".tovec(); // - count let count = fmindex.count(&pattern); asserteq!(count, 2); // - locate without k-mer lookup table let locations = fmindex.locatewoklt(&pattern); asserteq!(locations, vec![5,18]); // - locate with k-mer lookup table let locations = fmindex.locatewklt(&pattern); assert_eq!(locations, vec![5,18]); ```

Use FmIndexOn and FmIndexNn struct to generate FmIndex

```rust use ltfmindex::{FmIndexConfig, FmIndex, FmIndexOn, FmIndexNn};

// (1) Define configuration for fm-index let fmiconfig = FmIndexConfig::new() .setkmerlookuptable(8) .setsuffixarraysamplingratio(4) .containnonnucleotide();

// (2) Generate fm-index with text // - Use FmIndexOn struct directly let textonlync = b"CTCCGTACACCTGTTTCGTATCGGA".tovec(); let fmindexon = FmIndexOn::new(&fmiconfig, textonlync); // only_nucleotide field of config is ignored // - Use FmIndexNn struct directly let textnonnc = b"CTCCGTACACCTGTTTCGTATCGGANNN".tovec(); let fmindexnn = FmIndexNn::new(&fmiconfig, textnonnc);

// (3) match with pattern let pattern = b"TA".tovec(); // - count let counton = fmindexon.count(&pattern); let countnn = fmindexnn.count(&pattern); asserteq!(counton, countnn); // - locate without k-mer lookup table let locationson = fmindexon.locatewoklt(&pattern); let locationsnn = fmindexnn.locatewoklt(&pattern); asserteq!(locationson, locationsnn); // - locate with k-mer lookup table let locationson = fmindexon.locatewklt(&pattern); let locationsnn = fmindexnn.locatewklt(&pattern); asserteq!(locationson, locationsnn); `` - What's the difference? - TheFmIndexConfig::generate_fmindex()generatesBoxtype, while thenew()function of structs generate struct that are not surrounded byBox`.

Write and read FmIndex

```rust use ltfmindex::{FmIndexConfig, FmIndex, FmIndexOn, FmIndexNn};

// (1) Generate FmIndex let fmiconfig = FmIndexConfig::new() .setkmerlookuptable(8) .setsuffixarraysamplingratio(4); let text = b"CTCCGTACACCTGTTTCGTATCGGA".tovec(); let fmindexpre = FmIndexOn::new(&fmiconfig, text); // text is consumed

// (2) Write fm-index to buffer (or file path) let mut buffer = Vec::new(); fmindexpre.writeindexto(&mut buffer).unwrap();

// (3) Read fm-index from buffer (or file path) let fmindexpro = FmIndexOn::readindexfrom(&buffer[..]).unwrap();

asserteq!(fmindexpre, fmindex_pro); ```

Future works

• Support SIMD for BWT block compression.
• Length of texts can be 32bit integer

  Repository

https://github.com/baku4/lt-fm-index

Doc

https://docs.rs/lt-fm-index/

Reference

• Ferragina, P., et al. (2004). An Alphabet-Friendly FM-Index, Springer Berlin Heidelberg: 150-160.
• Anderson, T. and T. J. Wheeler (2021). An optimized FM-index library for nucleotide and amino acid search, Cold Spring Harbor Laboratory.
• Wang, Y., X. Li, D. Zang, G. Tan and N. Sun (2018). Accelerating FM-index Search for Genomic Data Processing, ACM.
• Yuta Mori. libdivsufsort