Shortest-Superstring-Problem

Wir untersuchen nun eine weitere abstrakte Formulierung des Fragment-Assembly-Problems.

Definition 15   Sei $F= \{f_1,\ldots,f_k\}$ eine Menge von Strings (Fragmenten). Ein Superstring von F ist ein String, der jede Sequenz von F als Teilstring enthält. Mit S_m(F) bezeichnen wir den kürzesten Superstring (Shortest-Superstring)  der Menge F.

Unter gewissen Voraussetzungen ist es wahrscheinlich, daß die gesuchte DNA-Sequenz der kürzeste Superstring aller Fragmente von F ist. Wir können das Fragment-Assembly-Problem also als ein Shortest-Superstring-Problem auffassen, d.h., wir suchen den kürzesten String, der alle Fragmente der Menge F enthält. Das Shortest-Superstring-Problem ist NP-hard und MAX-SNP-hard [BJL⁺94]. Es existiert kein Polynomial-Time-Approximation-Scheme (PTAS),    d.h., es existiert also kein Polynomialzeit-Algorithmus, der für ein beliebiges aber festes $\epsilon > 0$ eine $\epsilon$-Approximation der optimalen Lösung liefert. Es existieren jedoch Polynomialzeit-Algorithmen, die Approximationen der optimalen Lösung für eine feste Approximationsschranke wie 3 liefern. Der beste bekannte Algorithmus [Swe95] erreicht eine Approximationsschranke von 2.5, d.h., die Strings, die der Algorithmus als Resultat liefert, sind höchstens 2.5 mal so lang wie der kürzeste Superstring.

Wir werden nun einen Algorithmus beschreiben, der eine 4-Approximation liefert. Zunächst führen wir jedoch neue Definitionen ein

Definition 16  

• Für eine Menge F von Strings bezeichnen wir mit $\Vert F\Vert$ die Summe der Längen |f_i| aller Strings.
• Seien f_i und f_j zwei Strings, dann bezeichnen wir mit ov(f_i,f_j) den längsten Suffix von f_i, der auch Präfix von f_j ist. Entfernen wir diesen Suffix am Ende von f_i, so erhalten wir einen String, den wir mit $f_i\setminus f_j$ bezeichnen.
• Sei $L=\{f_{i_1},f_{i_2},\ldots,f_{i_t}\}$ eine geordnete Teilmenge von Strings aus F, dann definieren wir den von L erzeugten String S(L) wie folgt:
  
  $$S(L) = (f_{i_1}\setminus f_{i_2})(f_{i_2}\setminus f_{i_3}) \ldots (f_{i_{t-1}}\setminus f_{i_t}) f_{i_t}.$$
  
  

Sei L = {AATTG,TTGCC,GCCAA}, dann ist der von L erzeugte String S(L) = AATTGCCAA.

Die Richtigkeit der folgenden Aussage folgt direkt aus der Definition des erzeugten Strings.

Lemma 2   Für jede Permutation $\pi(F)= (f_{i_1},\ldots,f_{i_k})$ einer Menge F von k Strings gilt: Der von $\pi(F)$ erzeugte String ist ein Superstring von F der Länge

$$\sum_{j=1}^{k-1} \vert(f_{i_j}\setminus f_{i_{j+1}})\vert + \vert f_{i_k}\vert.$$

Auch der kürzeste Superstring S_m(F) der Menge F wird von einer Permutation der Menge F erzeugt. Dies folgt aus der folgenden Beobachtung: Da kein String von F in einem der anderen Strings enthalten ist, muß ein String f_i, der in S_m(F) vor einem String f_j startet, auch vor f_j enden. Ferner starten (enden) alle Strings in verschiedenen Positionen von S_m(F). Indem wir die Strings nach ihren Anfangspositionen sortieren, erhalten wir eine Permutation, die S_m(F) erzeugt.

Da $\vert(f_{i_j}\setminus f_{i_{j+1}})\vert = \vert f_{i_j}\vert - \vert ov(f_{i_j},f_{i_{j+1}})\vert$ ist, kann man die Länge des Strings $S(\pi(F))$, der von einer Permutation $\pi(F)= (f_{i_1},\ldots,f_{i_k})$ von F erzeugt wird, wie folgt berechnen:

 

$$\Vert S(\pi(F))\Vert \vert f_{i_k}\vert + \sum_{j=1}^{k-1} \vert(f_{i_j}\setminus f_{i_{j+1}})\vert$$ = (1)

$$\sum_{j=1}^k \vert f_{i_j}\vert - \sum_{j=1}^{k-1} \vert ov(f_{i_j},f_{i_{j+1}})\vert$$ = (2)

$$\Vert F\Vert - \sum_{j=1}^{k-1} \vert ov(f_{i_j},f_{i_{j+1}})\vert.$$ = (3)

Hieraus folgt, daß wir das Shortest-Superstring-Problem auch als Maximierungs-Problem mit Zielfunktion $\sum_{j=1}^{k-1} \vert ov(f_{i_j},f_{i_{j+1}})\vert$ auffassen können.

Definition 17   Der unendliche String, der durch Konkatenation unendlich vieler Kopien eines Strings f gebildet wird, heißt der unendliche Zyklus von f und wird mit uz(f) bezeichnet. Ein String f heißt periodisch , wenn er aus zwei oder mehreren vollständigen Kopien eines Teilstrings s besteht. Der Teilstring s wird dann als Periode von f bezeichnet.

Der String ATGATGATGATG hat die Perioden ATG und ATGATG. Der Teilstring ATG ist die kürzeste Periode des Strings. Man beachte, daß man den unendlichen Zyklus uz(f) eines Strings f auch als zyklischen String auffassen kann, in dem der Anfangsbuchstabe von f mit dem Endbuchstaben von f verbunden ist. Man spricht in diesem Zusammenhang auch vom zyklischen String z(f) von f. Sowohl dem zyklischen String als auch dem unendlichen Zyklus ordnet man als Länge die Größe des Strings f zu, d.h. |f| = |z(f)| = |uz(f)|. Die beiden Modelle (Begriffe) ``zyklischer String'' und ``unendlicher Zyklus'' sind äquivalent, ermöglichen aber den Einsatz unterschiedlicher Beweistechniken.

Definition 18   Sei F eine Menge von Strings. Eine Menge Z(F) heißt eine zyklische Überdeckung von F, wenn jeder String $f\in F$ ein Teilstring eines unendlichen Zyklus uz(g) eines Strings $g\in Z(F)$ ist. Die Länge $\Vert Z(F)\Vert$ einer zyklischen Überdeckung Z(F) ist die Summe der Längen der Strings in Z(F). Die zyklische Überdeckung von F mit minimaler Länge bezeichnen wir mit Z_m(F).

Man beachte, daß die Länge der kürzesten zyklischen Überdeckung Z_m(F) einer Menge F immer kleiner gleich der Länge des kürzesten Superstrings S_m(F) ist, da der unendliche Zyklus uz(S_m(F)) von S_m(F) eine zyklische Überdeckung von F mit Länge kleiner gleich |S_m(F)| ist. Besitzt der kürzeste Superstring eine Periode, so bildet seine kürzeste Periode eine zyklische Überdeckung von F. Dieses Beispiel zeigt, daß die Länge der kürzesten zyklischen Überdeckung kleiner ist als die Länge des kürzesten Superstrings. Die kürzeste zyklische Überdeckung kann aber, im Gegensatz zum kürzesten Superstring, in Polynomial-Zeit berechnet werden. Aus Zeitmangel können wir den Polynomial-Zeit-Algorithmus für die Berechnung der kürzesten zyklischen Überdeckung im Rahmen der Vorlesung nicht vorstellen (siehe [Gus97]).

Wir beschreiben im folgenden einen Approximations-Algorithmus, der mit Hilfe der kürzesten zyklischen Überdeckung eine Approximation des kürzesten Superstrings berechnet:

• Berechne die kürzeste zyklische Überdeckung Z_m(F) der Menge F und ordne jedem String $f\in F$ den String $g\in Z_m(F)$ zu, dessen unendlicher Zyklus uz(g) den String f enthält. Falls es für einen String $f\in F$ mehrere Strings in Z_m(F) mit dieser Eigenschaft gibt, dann wähle einen beliebigen aus.
• Für jeden String $g\in Z_m(F)$ betrachten wir die Menge F_g von Strings in F, die g zugeordnet sind, und führen die folgenden Operationen aus: Sortiere die Strings in F_g bezüglich der Startpositionen der ersten Kopien der Strings in uz(g) bzw. g. Man beachte, daß die Startposition der ersten Kopie eines jeden Strings von F_g in dem Bereich zwischen 1 und |g| von uz(g) liegt. Wir nehmen nun der Einfachheit halber an, daß $F_g = \{f_{i_1},\ldots,f_{i_t}\}$ schon entsprechend der Startpositionen sortiert ist. Berechne den von F_g erzeugten String
  
  $$S(F_g) = (f_{i_1}\setminus f_{i_2}) \ldots (f_{i_{t-1}}\setminus f_{i_t}) f_{i_t}.$$
  
  
  der ein Superstring der Menge F_g ist.
• Konkateniere alle Superstrings S(F_g) für $g\in Z_m(F)$ zu einem String S. Der String S ist offensichtlich ein Superstring von F.

Wir werden nun beweisen, daß der String S höchstens 4 mal so lang wie der kürzesten Superstring von F ist, d.h., S ist eine 4-Approximation des kürzesten Superstrings. Für den Beweis benötigen wir die folgenden beiden Aussagen:

Lemma 3   Für den Superstrings S gilt:

$$\vert S\vert\leq \Vert Z_m(F)\Vert + \sum_{f\in L} \vert f\vert \leq \vert S_m(F)\vert + \sum_{f\in L} \vert f\vert.$$

Hierbei ist L die folgende Menge: Aus jeder Teilmenge F_g fügen wir den letzten String zu L hinzu. Der letzte String hat die größte Startposition.

Beweis: Die linke Ungleichung folgt aus der Tatsache, daß die Startpositionen aller Strings in F_g im Bereich [1:|g|] von uz(g) liegen. Die rechte Ungleichung ist trivial, da $\Vert Z_m(F)\Vert$ immer kleiner gleich |S_m(F)|.

Lemma 4   Seien g und g' zwei Strings der Menge Z_m(F) und seien f und f' zwei Strings von F, die g bzw. g' zugeordnet sind. Dann ist |ov(f,f')| < |g| + |g'|.

Beweis: Der Beweis der obigen Aussage basiert auf dem folgenden Satz.

Satz 13   Wenn ein String f zwei Perioden der Länge p und q mit q<p und $\vert f\vert \geq p + q$ hat, dann hat f auch eine Periode der Länge ggT(p,q).

Der Beweis der beiden obigen Aussagen ist eine Übungsaufgabe.

Satz 14   Die Länge des Superstrings S ist kleiner gleich der vierfachen Länge des kürzesten Superstrings S_m(F).

Beweis: Aufgrund der Ungleichung aus Lemma 3 genügt es zu zeigen, daß $\sum_{f\in L} \vert f\vert$ kleiner gleich 3 |S_m(F)| ist. Für jede Permutation $\pi=(f_{i_1},\ldots,f_{i_t})$ der Menge L der ``letzten'' Strings gilt nach Lemma 4:

$$\sum_{j=1}^{t-1} \vert ov(f_{i_j},f_{i_{j+1}})\vert \leq 2 \Vert Z_m(F)\Vert.$$

Aus dieser Ungleichung und aus Gleichung 3 folgt:

$$\vert S_m(F)\vert \geq \vert S_m(L)\vert \geq \sum_{f\in L} \... ...m(F)\Vert\geq \sum_{f\in L} \vert f\vert - 2 \vert S_m(F)\vert.$$

Durch Addition von 2 |S_m(F)| erhalten wir schließlich die gesuchte Ungleichung.

Wie haben uns in den vorhergehenden Abschnitten mit abstrakten Problemen beschäftigt, die mit dem Fragment-Assembly-Problem verwandt sind. In der Praxis werden zur Lösung dieses Problems Heuristiken verwendet, die zum Teil auf den hier vorgestellten Ideen basieren. Die meisten Verfahren basieren auf Multiple-Alignment-Algorithmen, die in der Regel bei einer kleinen Rate von Kopier- und Sequenzierfehler gute Resultate liefern. Es existiert jedoch noch kein Verfahren, daß das Repeats-Problem zufriedenstellend löst. Deshalb werden die berechneten Alignments noch auf mögliche Fehler überprüft und korrigiert. Zum Beispiel kann man überprüfen, ob bestimmte Abschnitte der berechneten Sequenz von sehr vielen Fragmenten überdeckt werden. Eine zu hohe Überdeckung deutet auf Repeats hin. In diesem Fall muß das Alignment neu berechnet werden. Hierbei versucht man mit Hilfe von Heuristiken, die verschiedenen Vorkommen der wiederholten Teilsequenz zu separieren.