SpaceEfficientBWTConstruction

Implementation of a fast and memory efficient BWT construction algorithm.

Background

The Burrows-Wheehler Transform transforms a text such that it can easily be compressed while offering the base for a fast suffix array like search. The construction is most often based on a suffix array (as in SeqAn). This dependents is a bottleneck because the suffix array construction is memory intensive, which poses a problem when large data sets, such as the human genome, are processed.

Topic

In this project the student is supposed to implement a fast and space efficient BWT construction algorithm which is based on blockwise suffix sorting [1]. The idea is to to sort the suffixes into buckets and construct the suffix array as well as the BWT bucket after bucket.

Requirements

• Implementation of the BWT construction scheme described in Juha Kärkkäinen
  • Implementation must be generic and in SeqAn style (templates, global functions)
  • Must work for Strings as well as StringSets
  • Suffices in a block must be sorted by a to be implemented string sorting algorithm
  • Assigning Suffices to blocks should make use of lcp values
  • The procedure should be parallelized (Open MP)
  • Usage of external memory
• Testing
• Documentation with (the new dddoc)
• Benchmarking (memory and speed)

First Steps

At the beginning after I learned something theoretical about the BWT I started with a naive implementation of BWT without SeqAn. The intention for this implementation was do understand how the BWT works with a self construction. About a SuffixArray structure I create a suffix array of a given text. The result was an array with all indices of the begin position for each suffix.

with this array I was able to construct the BWT. If I took the character before the given suffix index and at zero I took the last, than I got the values do built the BWT output.

It is important do say that I included an extra character to the input ("$"). The reason for this is that "$" is the the absolute minimal value of all characters.

This is necessary to create the suffix array and to reconstruct from the BWT, because now we know where is the first value of the first given input.

To find this we sort the BWT lexicographical and save the order. Now if we look at the position of previous order of "$", which is the first, because it is the smallest, we find the first value of given input. At carry on at the position of previous order of current value, we find the next one, and go on until we reach "$" again. This means that we are finish.

Weiteres Vorgehen

BWT mit Suffix Array:

Aus einem gegebenen Text T der Länge n werden alle Suffixe gebildet und diese lexikographisch sortiert. Es ist dabei nötig das Zeichen „$“ anzuhängen das dabei als das kleinstmögliche Zeichen im Alphabet steht. Das daraus erhaltenen Suffix Array wird zur Erzeugung der BWT genutzt.

(1)

if (SA[i]!=0) then BWT[i]=T[SA[i]-1]

else if (SA[i]==0) then BWT[i]=$

BWT mit block Suffix Sortierung: Text → T[0,n) = t0, t1,t2,...tn-1 Si → T[i,n) SA → Suffix Array Hierbei wird ähnlich wie zuvor ein Suffix Array genutzt und mit (1) der BWT erzeugt, allerdings wird die Erstellung des Suffix Arrays blockweise vorgenommen, in r vielen Blöcken.

Schritt 1: Es wird eine Menge C der Größe r-1 von Zufallszahlen aus [0,n) gebildet.

Schritt 2: Es wird die Menge Sc mit Si , wobei i ein Element von C ist, gebildet. Die Elemnte von Sc werden sortiert, so das es mit dem kleinsten Suffix beginnt und mit dem größten endet. Zudem werden Sn ,das kleinstmögliche Suffix an den Anfang und Smax ,das größtmögliche Suffix am Ende in Sc eingefügt.

Schritt 3: Für jedes k Element [0,r):

* Für jedes j Element [0,r) prüfe ob Sc[k] < Sj < Sc[k+1]gilt, wenn ja speichere j in Bk..

* Bilde SA[ik,ik+1] aus allen Suffixen von Bk.

* Bilde BWT nach (1) aus SA.

Zusammenfassung:

Es werden neben dem größten und dem kleinsten Suffix r-1 viele Suffixe zufällig ausgewählt und daraufhin werden alle andern Suffixe in die Bereiche sortiert und für jeden Bereich ein Suffix Array erstellt, welches in einen BWT übersetzt wird.

Details:

Zum sortieren kann ein String Sortieralgorithmus verwendet werden, bei einem festen kleinen Alphabet empfiehlt sich Radix Sort, alternativ akann auch Multikey quicksort verwendet werden, da hierbei kein festes Alphabet benötigt wird und auch bei großen Alpahbeten effizient ist.

Es werden beide Algorithmen Implementiert und ein Kriterium für die Wahl des Algorithmus angelegt.

Für das Sortieren in die Bereiche müssen alle Suffixe gefunden werden die kleiner als die Obergrenze und größer als die Untergrenze sind. Dazu wird

Dazu werden alle LCPs zwischen T und einem zweiten Teilstring P von T errechnet und diese werden genutzt um alle Suffixe zu sortieren.

Literatur

[1] Juha Kärkkäinen, Fast BWT in small space by blockwise suffix sorting, Theoretical Computer Science, Volume 387, Issue 3, 22 November 2007, Pages 249-257