Struct SbwtIndex 

pub struct SbwtIndex<SS: SubsetSeq> { /* private fields */ }

The SBWT index data structure. Construct with SbwtIndexBuilder. For the SubsetSeq trait implementation, we recommend using the bit matrix implementation SubsetMatrix.

SBWT index

The SBWT index is a compressed index for searching for k-mers in a set of k-mers. It can be seen a version of the FM-index on sets of k-mers. Here we give a brief overview of the data structure and key concepts that are helpful for understanding the API. For further details, see the paper.

SBWT graph

To understand the SBWT index, it’s helpful to first understand the SBWT graph. The node-centric de Bruijn graph of a set of k-mers R (also called a k-spectrum) is a directed graph where the nodes are the k-mers in R, and there is an edge from x to y if x[1..k) = y[0..k-1). The label of the edge is the last character of y. The SBWT graph is a modified version of the node-centric de Bruijn graph. There are two modifications:

1. We add a set R’ of “dummy nodes”. First, the source set R’ ⊆ R is the subset of k-mers in R that do not have an incoming edge in the de Bruijn graph, that is x ∈ R’ iff x[0..k-1) is not the suffix of any k-mer in R. The set of dummy nodes is the set of all proper prefixes of the k-mers in R’. We pad the dummy nodes with dollar symbols from the left so that all dummy nodes have length k. The set R ∪ R’ is called the padded k-spectrum. We add all de Bruijn graph edges between overlaps of the padded k-spectrum, that is, for every x ∈ R ∪ R’ and y ∈ R ∪ R’ such that x[1..k) = y[0..k-1), we add an edge from x to y in the SBWT graph. As a special case, the empty string $^k is always included in R’, and the incoming self-loop edge labeled with $ is not included.
2. For every node in R ∪ R’ that has more than one incoming edge, we delete all incoming edges except the one that comes from the colexicographically smallest k-mer. A k-mer x is colexicographically smaller than k-mer y iff the reverse of x is lexicographically smaller than the reverse of y.

For example, below is the SBWT graph of all 4-mers of strings [“TGTTTG”, “TTGCTAT”, “ACGTAGTATAT”, “TGTAAA”]. The source node set is shown in blue, the dummy node set R’ in orange, and the de Bruijn graph edges that have been removed are shown in red.

SBWT definition

The SBWT is a sequence of subsets of {A,C,G,T} such that the i-th subset contains the edge labels of outgoing edges from the i-th k-mer in the SBWT graph in colexicographic order of the k-mers. If we take the example from above and stack the nodes in colexicographic order, we get:

The SBWT subset sequence in this example is the sequence of outgoing edge label sets read from top to bottom: {A,T}, {C}, {}, {A}, {T}, {T}, {A,G,T}, {}, {}, {G}, {T}, {T}, {T}, {T}, {C}, {G}, {A}, {}, {}, {A}, {A}, {A}, {A,T}, {T}, {G}. The key property that makes the SBWT index work is that the i-th outgoing edge with a given label on the right column in the picture is the same edge as the i-th incoming edge with the same label on the left column. Thanks to this property, once the subset sequnce has been constructed, the k-mers and the graph can be discarded, with no loss of information. That is, the k-mers and the graph can be reconstructed from the subset sequence alone.

Given the subset sequence, there is also an algorithm to search for a k-mer in O(k) time. The algorithm is essentially the same as the search algorithm on the FM-index. Given a k-mer P[0..k], at iteration i, we have the range of rows in the picture whose k-mers have P[0..i) as a suffix. When i = 0, we have the empty suffix P[0..0), which is a suffix of all k-mers. To update the range for the next iteration, we follow the edges labeled with the next character of the pattern, using the key property mentioned above, as shown in the figure below for query k-mer TATA. This update step can be implemented efficiently by preprocessing the SBWT set sequence for subset rank queries. See this paper for more on how to implement these rank queries. We provide an implementation based on a bit matrix at SubsetMatrix. Any struct implementing the SubsetSeq trait can be used to query the SBWT.

Implementations

impl<SS: SubsetSeq> SbwtIndex<SS>

pub fn n_kmers(&self) -> usize

Number of k-mers in the index, not counting dummy k-mers.

pub fn n_sets(&self) -> usize

Number of sets in the SBWT.

pub fn k(&self) -> usize

Length of the k-mers in the index.

pub fn char_idx(&self, c: u8) -> usize

Maps A,C,G,T to 0,1,2,3. Panics if c is not a DNA character.

pub fn alphabet(&self) -> &[u8]

Returns the alphabet ACGT of the index in ascii.

pub fn interval_of_empty_string(&self) -> Range<usize>

pub fn serialize<W: Write>(&self, out: &mut W) -> Result<usize>

Writes the index to the writer and retuns the number of bytes written. The array can later be loaded with SbwtIndex::load.

pub fn load<R: Read>(input: &mut R) -> Result<Self>

Loads an index that was previously serialized with SbwtIndex::serialize.

pub fn inlabel(&self, i: usize) -> Option<u8>

Returns the edge label on the incoming edge to the i-th node in colexicographic order in the SBWT graph (not the same graph as the de Bruijn graph!), or None if the node has no incoming edge. This is well-defined since every node in the SBWT graph has at most 1 incoming edge.

pub fn build_select(&mut self)

Build select support for the SBWT subset sequence. This is required for SbwtIndex::inverse_lf_step and SbwtIndex::access_kmer.

pub fn lf_step(&self, i: usize, char_idx: usize) -> usize

A low-level function returning C[char_idx] + SBWT.rank(char_idx, i).

pub fn inverse_lf_step(&self, i: usize) -> Option<usize>

The inverse function of SbwtIndex::lf_step. Requires that the select support has been built. Returns None if called on the source node of the SBWT graph.

pub fn push_kmer_to_vec(&self, colex_rank: usize, buf: &mut Vec<u8>)

Requires that the select support has been built. Accesses the k-mer associated with the node with colexicographic rank colex_rank. Note that this k-mer may contain dollar symbols if it’s a dummy node. The k-mer string is pushed to buf.

pub fn access_kmer(&self, colex_rank: usize) -> Vec<u8>

Requires that the select support has been built. Accesses the k-mer associated with the node with colexicographic rank colex_rank. Note that this k-mer may contain dollar symbols if it’s a dummy node. The k-mer is retuned as a Vec<u8>. To push to an existing buffer for better performance, see SbwtIndex::push_kmer_to_vec.

pub fn search(&self, pattern: &[u8]) -> Option<Range<usize>>

Returns the colexicographic interval of the pattern, if found. The pattern is given in ascii characters.

pub fn search_from( &self, interval: Range<usize>, pattern: &[u8], ) -> Option<Range<usize>>

Searches the pattern starting from the given colexicographic interval. Returns the colexicographic interval after searching the pattern, if found. The pattern is given in ascii characters.

pub fn reconstruct_padded_spectrum(&self, n_threads: usize) -> Vec<u8>

where Self: Sync,

Reconstruct all k-mers in the padded k-spectrum in the data structure. The reconstructed k-mers concatenated into a single ascii string in colexicographic order. The i-th k-mer starts at position i*k in the string.

pub fn set_lookup_table(&mut self, prefix_lookup_table: PrefixLookupTable)

Set the prefix lookup table of the data structure.

pub fn get_lookup_table(&self) -> &PrefixLookupTable

Get the prefix lookup table of the data structure.

pub fn sbwt(&self) -> &SS

Get the SBWT set sequence of the data structure.

pub fn from_subset_seq( subset_rank: SS, n_kmers: usize, k: usize, precalc_prefix_length: usize, ) -> Self

Construct from existing crate::subsetseq::SubsetSeq.

pub fn push_all_labels_forward( &self, labels_in: &[u8], labels_out: &mut [u8], n_threads: usize, )

where Self: Sync,

Push labels forward along the SBWT graph. The effect is this: if labels_in is a list of labels, one for each node in the SBWT in colex order, then the output is those labels pushed forward along the edges in the SBWT graph. Those nodes that do not have a predecessor (just the root of the graph) get a dollar.

pub fn push_all_labels_forward_compact( &self, labels_in: &CompactIntVector<3>, labels_out: &mut CompactIntVector<3>, n_threads: usize, )

where Self: Sync,

A version of SbwtIndex::push_all_labels_forward that stores the labels as compact integer vectors with elements {0,1, …, 4}. The symbol 0 is the “dollar” and symbols 1,2,3,4 are A,C,G and T. (see the documentation of SbwtIndex::push_all_labels_forward.

pub fn build_last_column(&self) -> Vec<u8>

Build the last column of the SBWT matrix.

pub fn build_last_column_compact(&self) -> CompactIntVector<3>

Build the last column of the SBWT matrix.

pub fn compute_dummy_node_marks(&self) -> BitVec

Compute a bit vector marking the dummy nodes in the SBWT

Trait Implementations

impl<SS: Clone + SubsetSeq> Clone for SbwtIndex<SS>

fn clone(&self) -> SbwtIndex<SS>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<SS: Debug + SubsetSeq> Debug for SbwtIndex<SS>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<SS: SubsetSeq> ExtendRight for SbwtIndex<SS>

fn extend_right(&self, I: Range<usize>, c: u8) -> Range<usize>

Right extensions implemented time O(t), where t is the time for a rank query in the subset rank query implementation of SS. This is O(1) for SubsetMatrix.

impl<SS: PartialEq + SubsetSeq> PartialEq for SbwtIndex<SS>

fn eq(&self, other: &SbwtIndex<SS>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<SS: Eq + SubsetSeq> Eq for SbwtIndex<SS>

impl<SS: SubsetSeq> StructuralPartialEq for SbwtIndex<SS>