Zusammenfassung von

A Database Index to Large Biological Sequences[1]
by E. Hunt, M.P. Atkinson, R.W. Irving

Überblick

Grundlagen

Die wichtigsten Information über Funktion und Bausweise lebender Organismen ist in den Sequenzen der Biomoleküle (zum größten Teil) gespeichert. Diese DNA-Sequenzen enthalten somit, mit A,C,G und T codiert, den "code of life". Eine Sequenz besteht aus einem Basis-Paar pro Buchstabe. Die Länge der DNA wird in Giga Base Pairs (Gbp) gemessen. Durch den Vergleich der Sequenzen (exakt und approximativ) will man Rückschlüsse auf die Struktur, die Funktion und das Zusammenspiel der einzelnen Komponenten ziehen. Deshalb spielt der Sequenzvergleich eine sehr große Rolle.

Viele Projekte (auch die der Autoren) befassen mit der Suche nach multiplen Genen der DNA, um Modellorganismen für Genfunktionen zu finden, die untersucht werden.

Bisher verwendete Such-Techniken sind

• der serielle Scan durch den gesamten Datenbestand mittels eines Filters,
• Stringvergleichsroutinen,
• Ausnutzen paralleler Rechnenprozesse

Das Problem

Die Methoden zur Bestimmung der Sequenzen von Biomolekülen haben sich in den letzten Jahren so sehr verbessert, dass man pro Tag mehrere Megabyte an Daten pro Tag produzieren kann. Große Datenmengen und große Anfragemengen überfordern jedoch die bisherigen Techniken. Die Ergebnisse sind mitunter nicht genau genug oder werden nicht schnell genug gefunden.

Das Problem liegt also bei den Algorithmen zum Sequenzvergleich bzw. -suche. Also versucht man diese zu beschleunigen. Wir benötigen eine Datenstruktur, welche das Suchen im Datensatz effizient gestaltet. Ein möglicher Ansatz, der in der Datenbankwelt generell sehr beliebt ist, ist die Verwendung von Indizes. Suffix-Trees sind eine solche Index-Struktur, die in diesem Zusammenhang große Beliebtheit erworben hat, und werden noch ausführlich vorgestellt.

Bei der Verwendung von Indizes sind jedoch folgende Schwierigkeiten zu beachten:

• Für die verschiedenen Index-Typen fanden bisher keine Untersuchungen bzgl. großen Datenmengen statt.
• Mitunter dauert die Konstruktion eines brauchbaren Index sehr lange. Dies ist jedoch verträglich, wenn man die Konstruktionszeit auf viele Anfragen (Batch = Anfragepaket) amortisiert.
• Um jedoch einen mehrmaligen Zugriff auf den Index zu ermöglichen müssen wir ihn persistent auf Disk speichern (bzw. erzeugen) können. Dies ist auch notwendig, wenn die Datenmenge bzw. die Größe des Index den Hauptspeicher übersteigt.

Indices

Im behandelten Paper wurden diverse Indices namentlich erwähnt und (sehr knapp) diskutiert. Der Information halber werden im folgenden die verschiedenen Indices erwähnt.
 

Suffix Trees

Beschreibung/Struktur

Gegeben ist ein Datensatz DNA in Form eines Strings S der Länge n und viele weitere Sequenzen A_i der Länge m_i. Wir gehen davon aus, dass die Sequenzen A_i viel kleiner als S sind, also m_i << n. Gesucht wird jeweils, ob und wie häufig die Sequenz A_i in S enthalten ist.

Einen Ansatz dazu bietet z.B. der Algorithmus von Bayer-Moore, der hier jedoch nur grob beschrieben wird. Im Wesentlichen machen wir einen linearen Scan durch S und prüfen dabei ob A in S enthalten ist (ohne jedesmal durch A laufen zu müssen). Für jede Sequenz A_i hat der Algorithmus somit eine Laufzeit von O(n).

Hier greift der Vorteil von Suffix-Trees. Wir bilden zunächst in einem Preprocessing zum String S einen Suffix-Tree. Mittels Suffix-Links gelingt dies sogar in linearer Zeit, also O(n). Das Suchen von A_i kann man mittels dieses Suffix-Trees dann in O(m_i) erledigen. Ist also m_i << n, ist dies ein erheblicher Laufzeitgewinn beim Suchen, welcher bei genügend vielen Anfragen A_i auch das Preprocessing amortisiert aufwiegt.

Nun zur Konstruktion. Wir bilden einen Baum, dessen Kanten Buchstaben bzw Wörter darstellen. Ein Suffix Trie zum String S ist ein solcher Baum, bei dem alle Knoten (durch ihren Pfad zur Wurzel) je einen Teil-String von S repräsentieren und bei dem zu jedem Teilstring von S auch genau ein solcher Knoten existiert.
Der Platzbedarf als auch die Konstruktionszeit beträgt hier O(n²).

Suffix Trie

Aus diesem gewinnt man den Suffix Tree, indem wir innere Knoten vom Grad 2 durch Kontraktion mit dem Kind eleminieren. Dadurch wird der Baum verjüngt und enthält fast nur noch Knoten, die Suffixe des Strings S repräsentieren. Weiterhin merken wir uns nicht mehr in den Kanten die jeweiligen präsentierten Buchstaben, sondern ihre Positionen im String S. Diese Positionen bzw. Bereiche (durch Kontraktion) merken wir uns nun in den Knoten statt in den Kanten.
Durch diese Veränderungen sinkt der Platzbedarf auf O(n). Die Konstruktionszeit dieses Baumes ist im worst case O(n²), im average case O(n log n).

Suffix Tree

Nun gibt es Suffixe, die als Präfix in anderen Suffixen enthalten sind. Im Beispiel wäre dies der Suffix 8. Der Knoten, der solch einen Suffix repräsentiert, ist dann kein Blatt. Mittels eines Tricks, nämlich dem vorherigen Einfügen eines Terminatorsymbols $ (welches im bisherigen Alphabet nicht enthalten war) an das Ende von S erreichen wir, dass nun kein Suffix Präfix eines anderen ist. War zuvor Suffix 8 (A) ein Präfix von Suffix 3 (ATCTTA), so ist jetzt Suffix 8 (A$) ein Präfix von Suffix 3 (ATCTTA$). Damit können Knoten, die einen Suffix von S darstellen, keine inneren Knoten mehr sein und umgekehrt stellen alle Blätter einen Suffix dar. Dadurch sind die Suffix-Knoten von den verzweigenden (inneren) Knoten getrennt und es gibt eine eineindeutig Beziehung zwischen Blättern und Suffixen.

Bspl. Suffixe von ACATCTTA mit und ohne Terminatorsymbol
 

Der Suffix Tree kann mit Suffix Links erweitert werden. Der große Vorteil dieser Links ist, dass mit ihrer Hilfe der Suffix Tree in linearer Zeit erstellt werden kann, also O(n), und sie damit von großer Bedeutung sind. Der Suffix Link ist ein Pointer, den jeder innere Knoten enthält. Repräsentiert der Knoten den String aw, wobei a ein Buchstabe und w ein String ist, so zeigt sein Suffix Link auf den Knoten, der den String w darstellt.

Suffix Tree mit Links

Suffix-Link-Algorithmus

Ein Algorithmus, der Suffix Links benutzt, um den Suffix Tree in linearer Zeit zu konstruieren ist sehr kompliziert und soll hier nur wage skizziert werden.

Wir fügen zunächst den längsten Suffix ein, dann den nächstkürzeren usw. Im i-ten Schritt fügen wir den Suffix S_i ein. Alle inneren Knoten des Baumes, die bisher eingefügt wurden, besitzen einen Suffix Link. Wir sparen, wenn wir nach dem Einfügen eines Suffixes mit Hilfe eines Links in die Einfügstelle des nächsten Suffixes in konstanter Zeit springen können. Sollten wir beim Einfügen neue innere Knoten erzeugt haben, so müssen wir deren Suffix Links in konstanter Zeit auf den entsprechenden Wert updaten.

Dazu zerlegen wir den Suffix S_i in u v w tail_i, wobei u der erste Buchstabe ist, uvw sei der längste Präfix von S_i (mit Wörtern v, w), der auch Präfix in einem bereits eingefügten Suffix ist. uv sei der längste Teil dieses Präfixes zudem ein innerer Knoten existiert. Es gibt also einen Pfad im Baum, der mit u anfängt und bei einem inneren Knoten d endet, der uv repräsentiert. Dieser Knoten hat einen Sohn, der mit S_i den Präfix uvw gemeinsam hat. Also müssen wir die Kante von d zu diesem Sohn aufspalten und einen Knoten h  einfügen, der uvw repräsentiert, und anschließend diesem noch einen Sohn hinzufügen, der dann uvw tail repräsentiert. Nun hat h noch keinen Suffix Link und wir müssen in die Einfügstelle des nächsten Suffix S_i+1 = vwtail_i gelangen. Dazu nutzen wir den Link des Knoten d, welcher uv repräsentiert und auf dessen Link auf den Knoten zeigt, der v repräsentiert. Von dort Scannen wir den Baum abwärts bis wir den Knoten finden, der vw repräsentiert. Auf diesen lassen wir den Link des Knoten h zeigen, der ja uvw repräsentiert. Damit haben wieder alle Knoten einen Suffix Link. Jetzt laufen wir weiter abwärts bis wir wieder die entsprechende Einfügstelle finden, usw.

Der Algorithmus zerfällt also in 3 Phasen. Nachdem ich den Link zum Knoten bzgl. v benutzt habe, setzt die RESCAN-Phase ein, in der ich den Knoten bzgl vw finde und den Suffix Link von h setze. Das Finden der richtigen Einfügestelle heißt SCAN-Phase. In der dritten und letzten Phase fügen wir die neuen Knoten ein und benutzen den Link zur nächsten Rescan-Ausgangspunkt. Man kann zeigen, dass durch das Benutzen des Links die Erzeugung des Baumes nur linear in n ist (Die Rescan-Phasen zusammengenommen sind nur linear und die Scan-Phasen zusammengenommen sind linear, die 3.Phase ist in jedem Schritt konstant). Natürlich ist die Konstruktion auch linear in der Größe des Alphabets |A|, da ich beim Suchen des richtigen Sohnes mitunter bis zu |A| Söhne testen muss.

Pro & Contra

Wir betrachten speziell diese Index-Struktur, da sie häufig benutzt wird. Dabei insbesondere in bekannten approximierenden Suchalgorithmen, biologischen Sequenz-Processings und vielen anderen biologischen Methoden. Sowohl der Platz als auch die Konstruktionszeit sind linear, was sehr vorteilhaft ist. Jedoch kann gezeigt werden, dass sich Suffix Trees mit Suffix Links nur eignen, solange sie in den Hauptspeicher passen. Anderenfalls entstehen durch die vertikale Baumstruktur und die horizontalen Suffix Links sehr häufig Disk-Zugriffe, wodurch die Performance in den Keller rutscht. Das gleiche Problem beim Erzeugen persistenter Suffix Trees entsteht durch die Pseudo-Zufallsstruktur der DNA, woraus Zufallszugriffe auf Disk und damit einen Menge Cache-Misses folgen.

Erzeugung persistenter ST

Deshalb hat man sich mit der Erzeugung persistenter Suffix Trees auseinandergesetzt, um zumindest kleine Datensätze bearbeiten zu können. Arbeiten hierzu gibt es von

• Bieganski[2], für Sequenzen bis 10 Mbp,
• Baeza-Yates & Navarro[3], für Sequenzen bis 1 Mbp (bei 64 MB MM) zusammen mit dem Beweis, dass sich Suffix Trees nur für Hauptspeicher-Größen eignen.
• Farach[4], mit einer theoretischen Arbeit, die das I/O-Problem bearbeitet durch ein Disk-Zugriffsmodell und die Baum-Erzeugung auf das Sortierproblem reduziert.
• Kurtz[5], welcher durch spezielle Knoten-Kompressionsverfahren den Speicherplatzbedarf pro Buchstabe auf 13 Byte senkt und damit im Hauptspeicher größere Instanzen erzeugen kann. Jedoch erhöhen zu kompakte Bäume wiederum die Disk-Zugriffe.

Trotzdem bedarf es einer grundlegenden Änderung, um Suffix Trees auch für große Sequenzen nutzen zu können.

Der neue Index

Idee

Um Suffix Trees auch für große Sequenzen erzeugen und nutzen zu können, muss zum einen der erforderliche Speicherplatz minimiert werden und zum zweiten (und wesentlichen) die Anzahl Disk-Zugriffe möglichst gering gehalten werden.

Dies wird durch folgende Ideen verwirklicht:

• Verzicht auf Suffix Links
  Dadurch ist der Zugriff auf (physisch) weit entfernte und bereits abgearbeitete Teile des Baumes nicht mehr nötig. Ein solcher erzeugter Teilbaum, in dem nichts mehr geändert wird, nennen wir "checkpointed partition". Untersuchungen ergeben, dass ohne Links eine mittlere Konstruktionszeit in O(n log n) zu erwarten ist, sich dieser Mehraufwand jedoch bei Hauptspeichergrößen nicht bemerkbar macht. Siehe dazu die Auswertung.
• Partitionierung des Baumes
  Jede Partition entspricht einem disjunkten Bereich von Suffixen. Sind einmal alle Suffixe einer Partition im Baum erzeugt, so ist auf diese Partition kein Zugriff oder Update mehr nötig. Aus dem gleichen Grund können Datenstrukturen von "checkpointed partitions", die zur Erzeugung der Partition notwendig waren, freigegeben werden.

Partitionierung

Bei langen DNA-Sequenzen übersteigt die Größe des Baumes auch ohne Links ein Vielfaches der Hauptspeichergröße. Wir müssen ihn also zerlegen, ihn bzw. die Menge der Suffixe in Partitionen einteilen. Die Anzahl der erwarteten Partitionen ergibt sich wie folgt:

p = #Partitionen = Baumgröße div MainMemory.

Für die Art der Partitionierung gibt es zwei Vorschläge:

1. Scannen und Verteilen
   Suffixe, deren Anfangssequenz, bestehend aus den ersten k Buchstaben, übereinstimmt, fassen wir (imaginär) zu Gruppen zusammen. Wir scannen nun einmalig seriell den Datenstring und zählen die Größe einer jeden Gruppe. Anschließend ordnen wir die Gruppen mittels BinPacking möglichst optimal auf die verschiedenen Partitionen. Mit einem weiteren Scan können wir den Baum erstellen und jeden Teilbaum entsprechen seiner Anfangssequenz in der entsprechenden Partition speichern.
    
2. Gleichmäßig Schneiden
   Gehen wir von einer Pseudo-Zufallsverteilung der DNA aus, so folgt daraus eine gleichmäßige Verteilung des Baumes und damit auch annähernd gleiche Gruppengrößen.
   Wir bestimmen deshalb die Partition eines Suffix Si anhand seiner Anfangssequenz und der Formel

   P_i = c_i a^k-1 + c_i+1 a^k-2 +...+ c_i+k-1 a⁰

   wobei wir die Alphabet-Größe mit a und die Position des k-ten Zeichens von S im Alphabet mit ck bezeichnen. Dadurch entspricht P_i einer Zahl zur Basis a, deren Ziffern aus den Positionen der ersten k Buchstaben des Suffixes im Alphabet bestimmt werden. Die Suffixe sind somit "der Größe nach" geordnet, wobei ihre Zeichen als Ziffern entsprechend der Reihenfolge im Alphabet benutzt werden. P_i gibt dabei nicht die Nummer der entsprechenden Partion an. Die möglichen Werte von P_i  liegen zwischen 0 <= P_i < a^k - 1. Diese verteilen wir gleichmäßig auf die Partitionen, wodurch wir eine Intervallgröße von r = (a^k - 1) div p erhalten. Damit gilt: Suffix i liegt in Partition j gdw. jr <= P_i  < jr + r.

partitionierter Suffix Tree

Algorithmus

Der Algorithmus arbeitet die Partitionen der Reihe nach ab und füllt sie jeweils mit den Suffixen, die ihm zugeordnet sind. Für jeden dieser Suffixe wird ein Knoten angelegt und eingefügt. Nach erfolgreichem Auffüllen der Partition wird dieser ein Checkpoint verpasst, dh. sie wird geschlossen und während der Konstruktion nicht mehr geladen.

Creation-Algorithm
For All Partitions j
  begin
  For All Suffixes i
    if (Suffix i is in Partition j) then
          begin
          New Node(i);
          Insert(i);
          end;
  CheckPoint;   //Close Partition j
  end;

Datenstruktur

NodePtr = ObjectPointer
  Child: NodePtr;       //erster Sohn
  Sibling: NodePtr;     //nächstälteres Geschwister
  LeftIndex: Integer;   //Linker Index des Kanten-Worts
end;

Der Knotentyp enthält sein erstes Kind, seinen nächstälteren Bruder und den linken Index des Teilwortes, den seine Kante zum Vater präsentiert. Er enthält nicht wie üblich einen Suffix Link, die Suffix Nummer oder den rechten Wort-Index. Indem sich jeder Knoten nicht seine Kinder sondern einen seiner Geschwister merkt, müssen die Knotenobjekte nicht dynamisch angelegt werden, sondern haben eine feste Größe. Diese setzt sich zusammen aus

• 3 x 4 Byte Objektvariablen
• 8 Byte Objektheader (Java)
• 8 Byte Organisationsstruktur (PJama)
• 8 Byte PJama Struktur

dh. 36 Byte pro Knoten.

Für einen String der Länge n werden im Baum zwischen 1.6n und 1.8n Knoten angelegt. Damit ergibt sich bei einer Knotengröße von 36 Bytes eine Gesamtgröße von 58n bis 65n Bytes, dh bis zu 65 Bytes pro Buchstabe. Eine Programmierung ohne Objekte benötigt nur 12 Bytes pro Knoten, was nur 21 Bytes pro Buchstabe entspricht. Mit Hilfe der Kompression von Kurtz benötigt man nur 13 Byte je Buchstabe.

Knoten Einfügen

Beim Anlegen des Knotens setzten wir Child und Sibling auf Null, den LeftIndex setzen wir auf die Nummer des Suffixes Si. Das Einfügen setzt sich zusammen aus dem Suchen der passenden Stelle und dem direkten Einfügen des Knotens.

Die Suche startet bei der Wurzel, und geht abwärts entsprechend jeweils dem Kind, welches einen Prefix von Si repräsentiert. Die Suche liefert den Knoten zurück, dessen String der längste repräsentierte Prefix von Si ist. Der LeftIndex soll den linken Index des Strings wiedergeben, den die Kante zum Vater repräsentiert. Während der Suche wird dieser Wert entsprechend der bereits vorhandenen Baumstruktur aktualisiert.

Beim Einfügen gibt es zwei Arten.

1. Gibt es ein Kind des gefundenen Knotens, dessen String einen Prefix hat, der mit einem Prefix von Si übereinstimmt und noch länger als der String des Vaters ist, so wird die Kante zum Kind aufgespalten. Dh. es wird ein weiterer Knoten zwischen Vater und Kind eingefügt, welcher genau diesen Prefix des Kindes präsentiert und als weiteres Kind den einzufügenden Si-Knoten erhält.
2. Existiert kein solches Kind, so kann der neue Knoten als erstes Kind oder als Bruder der bisherigen Kinder eingefügt werden.

Insert Routine

Knoten Suchen

Die Suche beginnt bei der Wurzel und läuft abwärts entsprechend dem Kind, welches einen Prefix mit einem Prefix von Si gemeinsam hat, der länger ist als der des Vaters. Die Suche verläuft entweder erfolglos oder liefert den Knoten mit dem kürzesten String zurück, der den gesuchten String vollständig als Prefix enthält.

Nun wird der Teilbaum, der den gefundenen Knoten als Wurzel enthält, vollständig durchlaufen und als Ergebnis werden alle Suffixe zurückgegeben, die innerhalb dieses Teilbaum repräsentiert werden. Die Suffix Nummern, welche nicht explizit innerhalb der Knoten gespeichert sind, werden während des Durchlaufens des Baumes berechnet anhand der Länge der jeweils präsentierten Strings. Ebenso ergeht es dem RightIndex, der den rechten Index des durch eine Kante präsentierten Strings enthält. Dieser ist für Blätter nämlich immer gerade n, da die Blätter genau die Suffixe darstellen. Bei den inneren Knoten berechnet man den RightIndex aus dem LeftIndex des ältesten Kindes durch Subtraktion von 1.

Der Aufwand für das Suchen setzt sich aus der Länge k der Anfrage und aus der Anzahl der Matchings m innerhalb des abzusuchenden Teilbaumes zusammen, also O(k + m). Die zu erwartende Größe des zurückgelieferten Ergebnisses kann ebenfalls berechnet werden. Wenn a die Größe des Alphabets ist, so gibt es a^k verschiedene Wörter mit Länge k. Folglich wird bei einer Anfrage der Länge k ein Teilbaum der Größe 1/a^k des Gesamtbaumes zurückgeliefert, wenn wir aufgrund der Zufallsverteilung der DNA auf eine Balance des Baumes schließen. Sind die Anfragen kurz, so kann dies sehr viel sein und somit das Benutzen des Indexes Overhead bedeuten. In diesem Fall mixt man die Algorithmen, dh. für kleine Anfragen benutzt man weiterhin den Seriellen Scan der Daten, für größere Anfrage (k > 10) den Index.

Tests

Mit und ohne Links

Getestet wurden die Erzeugungszeiten von Suffix Trees mit und ohne Links. Die Zeitkomplexität bei verlinkten Suffix Trees ist O(n), bei nicht verlinkten im worst case O(n²). Da jedoch die DNA eine Pseudo-Zufallsstruktur hat, ergibt sich ein average case von O(n log n). Nun können verlinkte Suffix Trees nur für "kleine" DNA-Längen (25 Mbp) persistent erzeugt werden und in dieser Größenordnung ist im Zeitverhalten kein Vorteil gegenüber unverlinkten Suffix Trees festzustellen.

Cold & Warm Store

Anfrage gleicher Länge werden zu Batches zusammengefasst. Dadurch macht es sich die Ausnutzung des Cache bemerkbar. Tests auf "warm store" schnitten sehr viel besser ab.

Anfragelänge

Das Auswerten einer Anfrage setzt sich wie oben beschrieben aus zwei Teilschritten zusammen. Zum einen dem Suchen des entsprechenden Knotens, was unabhängig der Anfragelänge sehr schnell geht. Zum anderen jedoch muss bei erfolgreichem Finden dieses Knotens der gesamte Kinderbaum durchsucht werden. Dies sind jedoch bei kurzen Anfrage sehr große Bäume mit vielen Ergebnissen. Folglich benötigt die Auswertung von kurzen Anfragen hier sehr viel mehr Zeit als die gleiche Menge von längeren Anfrage.

Das wars.

Referenzen

[1] 
E.Hunt, M.P.Atkinson, R.W.Irwing, A Database Index to Large Biological Sequences, Univ. of Glasgow G12 8QQ, UK2001
[2] 
P.Bieganski, Genetic Sequence Data Retrieval and Manipulation based on Generalized Suffix Trees, PhD thesis, Univ. of Minnesota, USA 98
[3] 
R.Baeza-Yates, G.Naravvo, A Hybrid Indexing Method for Approximate String Matching;
R.Baeza-Yates, G.Naravvo, A new indexing method for approcimate string matching, in CPM99, LNCS 1645, p 163-185, 1999
[4] 
M.Farach, P.Ferragina, S.Muthukrishnan, Overcoming the Memory Bottleneck in Suffix Tree Construction, In FOCS98, p 174-185, 1998
[5] 
S.Kurtz, Reducing the space requirement of suffix trees Softw. Pract. Exp. 29:1149-1171, 1999