Module bio::data_structures::suffix_array
[−]
[src]
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 |