Module bio::data_structures::suffix_array

source ·
Expand description

Suffix arrays and related algorithms. The implementation is based on the lecture notes “Algorithmen auf Sequenzen”, Kopczynski, Marschall, Martin and Rahmann, 2008 - 2015. The original algorithm desciption can be found in: Ge Nong, Sen Zhang, Wai Hong Chan: Two Efficient Algorithms for Linear Time Suffix Array Construction. IEEE Trans. Computers 60(10): 1471–1484 (2011)

§Examples

use bio::data_structures::suffix_array::suffix_array;
let text = b"GCCTTAACATTATTACGCCTA$";
let pos = suffix_array(text);
assert_eq!(
    pos,
    vec![21, 20, 5, 6, 14, 11, 8, 7, 17, 1, 15, 18, 2, 16, 0, 19, 4, 13, 10, 3, 12, 9]
);

Structs§

Traits§

  • SuffixArray
    A trait exposing general functionality of suffix arrays.

Functions§

  • lcp
    Construct lcp array for given text and suffix array of length n. Complexity: O(n).
  • shortest_unique_substrings
    Calculate all locally shortest unique substrings from a given suffix and lcp array (Ohlebusch (2013). “Bioinformatics Algorithms”. ISBN 978-3-00-041316-2). Complexity: O(n)
  • suffix_array
    Construct suffix array for given text of length n. Complexity: O(n). This is an implementation of the induced sorting as presented by Ge Nong, Sen Zhang und Wai Hong Chan (2009), also known as SAIS. The implementation is based on the following lecture notes: http://ls11-www.cs.tu-dortmund.de/people/rahmann/algoseq.pdf

Type Aliases§