Fragment-Assembly

Mit Hilfe des Shotgun-Verfahrens zerlegen wir das große DNA-Molekül in kleinere Teilsequenzen. Wir erhalten eine große Zahl von ``zufällig erzeugten'' DNA-Bruchstücken, die man Fragmente   nennt. Mit Hilfe der Gelelektrophorese extrahiert man eine gewisse Zahl von kurzen Fragmenten (<1000 bp). Aus der Menge von kurzen Fragmenten wählen wir zufällig eine bestimmte Zahl aus. Diese Fragmente werden dann mit Hilfe des Sanger-Gels (siehe Kapitel 1) sequenziert. Die Zahl der zufällig gewählten Fragmente spielt hierbei eine wichtige Rolle. Je größer die Zahl, desto kosten- und zeitintensiver gestaltet sich die Sequenzierung aller ausgewählten Fragmente. Ist die Zahl der Fragmente zu klein, so kann zu wenig Information für eine vollständige Rekonstruktion des zu sequenziernden DNA-Moleküls vorliegen. In der Regel wird die Zahl der Fragmente so gewählt, daß die Gesamtlänge aller Fragmente einen Faktor k (k<20) mal größer ist als die voraussichtliche Länge des zu sequenzierenden Moleküls. Die Länge des zu sequenzierenden Moleküls kann mit bis zu 10% Ungenauigkeit (Abweichung) geschätzt werden.

Das Fragment-Assembly-Problem   kann nun wie folgt definiert werden: Rekonstruiere die ursprüngliche DNA-Sequenz mit Hilfe der sequenzierten Fragmente.

Betrachten wir zunächst einmal ein Beispiel, wobei wir der Einfachheit halber von einer bekannten Sequenz (TTACCGTGC) ausgehen. Wir nehmen an, daß folgende vier Fragmente ausgewählt und sequenziert wurden:

                                     ACCGT
                                     CGTGC
                                     TTAC
                                     TACCGT

Dieses Fragment-Assembly-Problems kann mit Hilfe eines Multiple-Alignment-Ansatzes gelöst werden:

                                     --ACCGT--
                                     ----CGTGC
                                     TTAC-----
                                     -TACCGT--
                                     _________
                                     TTACCGTGC

Das obige Multiple-Alignment ist optimal bezüglich einer Bewertung, die Paare von gleichen Buchstaben in einer Spalte positiv (+1) und Paare von verschiedenen Buchstaben in einer Spalte negativ (-1) bewertet. Die Lücken (Gaps), die rechts oder links von den Fragmenten liegen, werden nicht bestraft, wohl aber Lücken in den Fragmenten (-1). Durch Auswerten der Spalten des Aligments erhalten wir die sogenannte Consensus-Sequenz,    die aus den am häufigsten in den Spalten auftretenden Buchstaben besteht. Die Consensus-Sequenz liefert uns in diesem Beispiel die gesuchte DNA-Sequenz.

Man kann also das Fragment-Assembly-Problem als ein Multipe-Alignment-Problem formulieren. Die Qualität der Resultate hängt hierbei wesentlich von der verwendeten Zielfunktion und dem verwendeten Multiple-Alignment-Algorithmus ab. Die einfache Bewertungsfunktion aus dem obigen kleinen Beispiel würde vermutlich für reale Fragment-Assembly-Probleme Consensus-Sequenzen liefern, die nur geringe Ähnlichkeit mit der gesuchten DNA-Sequenz hätten. Für das Fragment-Assembly-Problem wurden im Laufe der Zeit eine Reihe von Formulierungen entwickelt, die im wesentlichen auf der gleichen Idee basieren, nämlich eine Art von Multiple-Alignment der Fragmente aufzubauen und aus diesem Alignment die gesuchte Sequenz zu bestimmen. Die Ansätze unterscheiden sich jedoch in der Art und Weise wie das Alignment berechnet und aufgebaut wird. Die Tatsache, daß heute eine Reihe von unterschiedlichen Formulierungen für das Fragment-Assembly-Problem bekannt ist, ist auf Komplikationen zurückzuführen, die zum Teil durch Fehler beim Kopieren und Sequenzieren und zum Teil durch gewissen Eigenschaften der DNA-Moleküle verursacht werden:

(1) Fehler beim Kopieren und Sequenzieren: Diese Fehler führen meist dazu, daß einige Basen in den Sequenzen der Fragmente falsch sind. In dem folgenden Beispiel wurde die Base A in TACCGT durch G ersetzt. Dies führt jedoch zur gleichen Consensus-Sequenz, da im optimalen Alignment in Spalte (3) immer noch mehr A's als G's vorhanden sind.

            Eingabe:                    Ausgabe:

              ACCGT                       --ACCGT--
              CGTGC                       ----CGTGC
              TTAC                        TTAC-----
              TGCCGT                      -TGCCGT--
                                          _________
                                          TTACCGTGC

Erzeugt man die Kopien des zu sequenzierenden Moleküls mit Hilfe von Cloning, so kann es geschehen, daß ganze Fragmente des Hosts oder Vektors in der sequenzierten Fragment-Menge auftauchen (Contamination)  . Kennt man das Genom des Hosts, so kann man alle Fragmente mit dem Genom vergleichen und die vom Host stammenden Fragmente eliminieren.

Chimären   sind Fragmente, die sich (vor der Sequenzierung) aus zwei regulären Fragmenten zusammengesetzt haben. welche von weit entfernten Teilen des zu sequenzierenden Moleküls stammen. In unserem Beispiel wäre die Sequenz TTATGC eine Chimäre, die sich aus den regulären Fragmenten TTA und TGC zusammengesetzt hätte. Chimären lassen sich meist erst während der Berechnung oder mit Hilfe des Alignments erkennen und eliminieren.

(2) Unbekannte Orientierung: Die Fragmente, die sequenziert wurden, können natürlich von beiden Strängen stammen. Daher weiß man in der Regel nicht, von welchem der Stränge das Fragment stammt. Man weiß jedoch, daß beide Stränge vom (5')-Ende zum (3')-Ende gelesen werden. Wir müssen also sowohl die Fragmente als auch ihre invertierten Komplementärstränge berücksichtigen.

            Eingabe:                    Ausgabe:

              ACGGT                    <-   --ACCGT--
              CGTGC                    ->   ----CGTGC
              GTAA                     <-   TTAC-----
              TGCCGT                   ->   -TGCCGT--
                                            _________
                                            TTACCGTGC

(3) Repeats:  Repeats sind Teilsequenzen, die mindestens zweimal in der gesuchten Sequenz auftauchen. Zum Beispiel enthält die Sequenz ATGGCTCATAGGCTCGAG zweimal die Sequenz GGCTC.

  Eingabe:                    Ausgabe:          gesuchtes Alignment:

     GGCTC                      --GGCTC---      ----------GGCTC---
     TGGCT                      -TGGCT----      -TGGCT------------
     ATGGC                      ATGGC-----      ATGGC-------------
     GCTCAT                     ---GCTC-AT      ---GCTCAT---------
     TAGGCT                     TAGGCT----      --------TAGGCT----
     GGCTCG                     --GGCTCG--      ----------GGCTCG--
     GCTCGA                     ---GCTCGA-      -----------GCTCGA-
     CTCGAG                     ----CTCGAG      ------------CTCGAG
                                __________      __________________
                                ATGGCTCGAG      ATGGCTCATAGGCTCGAG

Das obige Beispiel zeigt eine Tendenz auf, die bei fast allen Fragment-Assembly-Verfahren zu beobachten ist: Teilsequenzen, die in der gesuchten Sequenz mehrfach vorkommen, tauchen in der berechneten Sequenz nur einmal auf. In unserem Beispiel ist der Wert des gesuchten Alignments sehr viel kleiner als der Wert des optimalen Alignments (bezüglich der einfachen Bewertungsfunktion, die wir oben beschrieben haben).

(4) Lücken in der Überdeckung:  Da wir die Fragmente zufällig auswählen, kann es geschehen, daß bestimmte Bereiche der gesuchten DNA-Sequenz überhaupt nicht durch Fragmente überdeckt werden. Diese Art von Fehler kann man erst während oder nach der Berechnung identifizieren. Entdeckt man am Ende der Berechnung, daß es mehrere unzusammenhängende Bereiche gibt, so versucht man die Lücken mit Hilfe der sogenannten direkten Sequenzierung zu schließen. Hierbei stellt man zunächst spezielle Primer her, die die Enden der zusammenhängenden Bereiche markieren. Mit Hilfe des PCR-Verfahrens synthetisiert man dann die Sequenzen, die den zusammenhängenden Bereichen (Contig)   benachbart sind. Diese Bereiche werden dann sequenziert und schließlich werden die noch vorhandenen Lücken aufgefüllt.

Wir präsentieren nun Lösungsansätze für den abstrakten Fall, daß

• keine Kopier- und Sequenzierfehler auftreten,
• keine Lücken in der Überdeckung vorhanden sind,
• keine (langen) Repeats in der gesuchten Sequenz vorhanden sind und
• daß die Orientierungen der Fragmente bekannt sind.

Im Anschluß an die Präsentation der Algorithmen für den abstrakten Fall diskutieren wir dann, wie man diese Algorithmen so ausbauen kann, daß sie auch in der Praxis eingesetzt werden können. Wie man Lücken in der Überdeckung beseitigen kann, haben wir bereits oben erwähnt. Wie man Repeats entdecken kann, ist ein weitgehend ungelöstes Problem, an dem zur Zeit intensiv von verschiedenen Gruppen gearbeitet wird. Wir nehmen ferner an, daß kein Fragment unserer Fragment-Menge F eine Teilsequenz eines anderen Fragments in F ist. Dies können wir wie folgt sicher stellen: Wir berechnen für alle Paare von Fragmenten in F den längsten gemeinsamen Teilstring (longest common substring). Ist der längste gemeinsame Teilstring identisch mit einem der beiden getesteten Fragmente, so wird dieses Fragment aus der Menge F entfernt. Pro Paar kostet die Berechnung mit Hilfe von modifizierten Suffix-Bäumen (siehe Übung 3) Zeit O(n), wobei n die Länge des längsten der beiden Fragmente ist. Die Gesamtzeit für alle Tests ist also O(|F|² n).