[−][src]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. 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] );
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 | |
RawSuffixArraySlice |