Struct bio::data_structures::fmindex::FMIndex

pub struct FMIndex<DBWT: DerefBWT + Clone, DLess: DerefLess + Clone, DOcc: DerefOcc + Clone> { /* fields omitted */ }

The Fast Index in Minute space (FM-Index, Ferragina and Manzini, 2000) for finding suffix array intervals matching a given pattern.

Methods

impl<DBWT: DerefBWT + Clone, DLess: DerefLess + Clone, DOcc: DerefOcc + Clone> FMIndex<DBWT, DLess, DOcc>

fn new(bwt: DBWT, less: DLess, occ: DOcc) -> Self

Construct a new instance of the FM index.

Arguments

• sa - the suffix array (or sample)
• bwt - the BWT
• k - the sampling rate of the occ array: every k-th entry will be stored (higher k means less memory usage, but worse performance)
• alphabet - the alphabet of the underlying text, omitting the sentinel

Trait Implementations

impl<DBWT: DerefBWT + Clone, DLess: DerefLess + Clone, DOcc: DerefOcc + Clone> FMIndexable for FMIndex<DBWT, DLess, DOcc>

fn occ(&self, r: usize, a: u8) -> usize

Get occurrence count of symbol a in BWT[..r+1].

fn less(&self, a: u8) -> usize

Also known as

fn bwt(&self) -> &BWT

Provide a reference to the underlying BWT.

fn backward_search<'b, P: Iterator<Item = &'b u8> + DoubleEndedIterator>(
    &self,
    pattern: P
) -> Interval

Perform backward search, yielding suffix array interval denoting exact occurrences of the given pattern of length m in the text. Complexity: O(m).