Module bio::data_structures::suffix_array

Suffix arrays and related algorithms. The implementation is based on the lecture notes "Algorithmen auf Sequenzen", Kopczynski, Marschall, Martin and Rahmann, 2008 - 2015.

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 Definitions

LCPArray
RawSuffixArray