Parallel Suffix Array Construction

Area

Substring Indices

Topic

Das Suffix Array speichert die Anfänge aller Suffixe eines (oder mehrerer) Texte in lexikographischer Reihenfolge und ermöglicht die effiziente Suche aller exakte Textvorkommen eines beliebigen Teilstrings. Es ist wichtigster Bestandteil des Enhanced Suffix Arrays (speichereffizienter Suffixbaum) und Ausgangspunkt für die Konstruktion des FM-Index (benutzt für die bzip2-Kompression und in Read Mappern wie BWA, Bowtie). Ziel der Arbeit ist, verschiedene parallele Algorithmen (1-3) für Shared-Memory zur Konstruktion des Suffix-Arrays einer oder mehrerer Sequenzen in SeqAn zu implementieren und auf Realwelt-Daten zu analysieren.

Timeline

References

1. Schürmann, K.-B., & Stoye, J. (2007). An incomplex algorithm for fast suffix array construction. Software: Practice and Experience, 37(3), 309–329. doi:10.1002/spe.768
2. Kulla, F., & Sanders, P. (2007). Scalable parallel suffix array construction. Parallel Computing, 33(9), 605–612.
3. Jeon JE, Park H, Kim DK (2005) Efficient construction of generalized suffix arrays by merging suffix arrays. J KISS: Comput Syst Theor 32(6):268–278