Celera Assembler

Der Celera Assembler, ein Genom-Assembler, wurde ursprünglich von der Firma Celera Genomics entwickelt und wird nun als Open-Source-Projekt weitergeführt. Er wird dazu genutzt, um aus vielen kurzen genomischen Fragmenten, die durch eine Whole-Genome- Shotgun-Sequenzierung gewonnen wurden, eine lange zusammenhängende Sequenz zu rekonstruieren.

Dabei werden mit einem Seed-and-Extend-Ansatz Überlappungen zwischen den bereinigten Fragmenten gesucht. Daraus wird der Overlap Graph konstruiert. Eine Spanning-Forest-Heuristik setzt die Fragmente zu Unitigs zusammen. Diese wiederum werden vom Greedy Path-Merging Algorithmus mit Hilfe der Mate-Pair-Informationen und dem Contig-Mate-Graph zu Scaffolds arrangiert. Die Lücken zwischen den Contigs können eventuell mit bisher ungenutzten Fragmenten und Mate-Pairs heuristisch gefüllt werden. Am Ende wird die Konsensussequenz durch ein Multialignment aller Fragmente über den gefundenen Scaffolds berechnet.

Theoretische Betrachtungen

Ein Assembly lässt sich durch folgendes Problem beschreiben.

Es sei eine Menge $F={f_{2},f_{2},\dotsb ,f_{n}}$ von Strings gegeben. Gesucht ist ein String S mit folgenden Eigenschaften:

1. Jedes $f_{i}$ ist Substring von S, $\forall f_{i}\in F:f_{i}\in S$
2. S ist minimal, $\forall S'$ mit 1. gilt $|S|\leq |S'|$

Dieses Problem ist als Shortest Common Superstring bekannt. Es ist NP-vollständig.

Im biologischen Kontext kommt verschärfend hinzu, daß die Sequenzen fehlerhaft sein können und stets zwei mögliche Orientierungen eines Fragmentes zu berücksichtigen sind. Außerdem ist es aus biologischer Sicht nicht immer sinnvoll eine minimale Sequenz zu ermitteln, da Fragmente aus repeathaltigen Regionen zu überkomprimierten Ergebnissen führen können. Das und die kombinatorische Komplexitiät bewirken, daß das hier vorgestellte Verfahren stark heuristisch ist.

Celera und der Assembler

Die Firma Celerea Genomics verfolgt, wie oben erwähnt, konsequent den Whole-Genome Shotgun Ansatz. Der dabei verwendete Assembler lässt sich nach [MSD+00] in mehrere, aufeinander aufbauende Stufen (Abbildung 2) einteilen, welche alle heuristisch sind. Das Herzstück des Assemblers bildet der Greedy Path-Merging Algorithmus.

Eingabedaten

Die Gewinnung der Sequenzfragmente geschieht mit Hilfe der "Double Barrel" Shotgun Sequenzierung (Abbildung 3). Dabei wird ein Klon von beiden Seiten ansequenziert und man erhält ein sogenanntes Mate-Pair von Reads. Dabei verwendete Klone haben typische Längen von 2kb, 10kb, 50kb und 150kb und die sequenzierten Reads eine Durchschnittslänge von 550 Basen. Die ursprünglichen Reads werden daraufhin auf ein Intervall mit Basen 98%iger Sicherheit gekürzt. Die den gelesenen Basen zugeordneten Qualitätswerte werden im weiteren Prozeß nicht berücksichtigt. In den Reads enthaltene Teile von Klonierungs- oder Sequenzierungsvektoren werden ebenfalls radikal entfernt. Die verbleibenden Stücke hoher Qualität sind die Eingabe des Assemblers. Diese werden im folgenden als Fragmente oder Reads bezeichnet.

Screener

Die Sequenzfragmente werden zunächst nach bekannten Repeats durchsucht. Fragmente, welche Repeatmuster enthalten, werden maskiert und später gesondert betrachtet. Die bereinigten Fragmente bilden die Eingabe für den nächsten Schritt.

Literatur

• "Algorithms in Bioinformatics II", Kapitel 17, Prof. Dr. Daniel Huson, Universität Tübingen, 2004 (engl.)
• "Der Celera Assembler", Seminararbeit, 2005

Weblinks

• Projektseite auf SourceForge