pub struct FmdIndex { /* private fields */ }Expand description
Bidirectional FM-Index (FMD-Index) for strand-aware DNA search.
Indexes the concatenation text#reverse_complement(text)$ to enable
efficient bidirectional extension for finding super-maximal exact matches (SMEMs).
Implementations§
Source§impl FmdIndex
impl FmdIndex
Sourcepub fn new(seq: &[u8]) -> Self
pub fn new(seq: &[u8]) -> Self
Build an FMD-Index from a DNA sequence.
The input seq should contain only A, C, G, T characters.
Internally constructs the concatenation seq#rev_comp(seq)$ and builds
both the forward and reverse FM-indexes.
§Example
use cyanea_seq::fmd_index::FmdIndex;
let fmd = FmdIndex::new(b"ACGT");
let interval = fmd.backward_search(b"ACG");
assert!(!interval.is_empty());Sourcepub fn init_interval(&self, c: u8) -> BiInterval
pub fn init_interval(&self, c: u8) -> BiInterval
Initialize a bi-interval for a single character.
Returns the interval representing all suffixes starting with c in both
the forward and reverse indexes.
Sourcepub fn extend_backward(&self, interval: &BiInterval, c: u8) -> BiInterval
pub fn extend_backward(&self, interval: &BiInterval, c: u8) -> BiInterval
Extend the bi-interval by prepending character c (backward extension).
This performs a standard backward search step on the forward index and updates the reverse interval accordingly.
Sourcepub fn extend_forward(&self, interval: &BiInterval, c: u8) -> BiInterval
pub fn extend_forward(&self, interval: &BiInterval, c: u8) -> BiInterval
Extend the bi-interval by appending character c (forward extension).
This performs a backward search step on the reverse index and updates the forward interval accordingly.
Sourcepub fn locate(&self, interval: &BiInterval) -> Vec<usize>
pub fn locate(&self, interval: &BiInterval) -> Vec<usize>
Retrieve text positions from a bi-interval.
Returns all suffix array positions within [0, text_len) — i.e., positions
in the original sequence (not its reverse complement).
Sourcepub fn backward_search(&self, pattern: &[u8]) -> BiInterval
pub fn backward_search(&self, pattern: &[u8]) -> BiInterval
Full backward search for an exact pattern.
Processes the pattern from right to left using the forward index, returning the final bi-interval. The interval may be empty if the pattern is not found.
Sourcepub fn smems(
&self,
query: &[u8],
min_len: usize,
) -> Vec<(usize, usize, BiInterval)>
pub fn smems( &self, query: &[u8], min_len: usize, ) -> Vec<(usize, usize, BiInterval)>
Find all Super-Maximal Exact Matches (SMEMs) of query against the index.
Returns a vector of (query_start, query_end, interval) triples, where
query_start..query_end is the matching substring of the query. An SMEM is
a maximal exact match that is not contained within any longer match at the
same query position.
Only matches of length >= min_len are returned.
§Algorithm
For each starting position in the query, extend backward as far as possible, recording the maximal intervals. Then filter to retain only super-maximal matches — those not properly contained in another match.