Hybridisierung (Hybridization) 1 Sequencing by Hybridization SBH Zentrum für Bioinformatik der Universität des Saarlandes WS 2002/2003

1Hybridisierung (Hybridization)

Sequencing by HybridizationSBH

Zentrum für Bioinformatikder Universität des Saarlandes

WS 2002/2003


• Zwei komplementäre DNA-Einzelstränge können durch Wasserstoffbrückenbildung eine Doppel- helix bilden. Diesen Vorgang nennt man Hybridisierung.

Adenin

Thymin

Guanin

Cytosin

• Durch Erwärmung auf Temperaturen über 80 Grad C oder durch Zugabe von organischen Lösungs- mitteln (wie Formamid) können Doppelstränge in zwei Einzelstränge getrennt werden. Diesen Vorgang nennt man Denaturierung.


• Bestimmte DNA-Muster in Chromosomen oder mRNA kann man wie folgt nachweisen:

(1) Wohldefinierte DNA-Moleküle (Folgen von Basen) werden mit einer Oberfläche verlinkt:

(2) Die zu untersuchenden DNA-Moleküle werden mit einem Fluoreszenzfarbstoff markiert, der durch eine geeignete Lichtquelle zur Fluoreszenz angeregt wird.

(3) Durch Hybridisierung werden die Moleküle mit komplementären Strängen gebunden.


• Durch den Einsatz von photolithographischen Verfahren kann man zweidimensionale DNA-Arrays erzeugen, die Tausende von verschiedenen DNA-Sequenzen an wohldefinierten Orten auf dem Chip tragen.

• Zum Beispiel kann man Felder erzeugen, die alle möglichen Basenfolgen der Länge l (für kleines l) auf der Oberfläche präsentieren.

AA AC AG AT

CC CG CT CA

GG GC GT GA

TT TC TG TA


Gegeben ein unbekanntes DNA-Molekül, d.h., die Basenfolge ist unbekannt. Man möchtedie Basenfolge lesen (bestimmen).

??????????????????

ATGCAGGTCCTACGTCCAGG

Gegeben sei ein DNA-Array mit allen möglichen potentiellenFragmenten (Strings) der Länge k. (k-Fragmente).

AAATAGACTATTTGTCGAGTGGGCCACTCGCC

A T C G

• Kopien des mit Fluoreszenzfarbstoff markierten DNA- Moleküls werden in Lösung befindlich auf das Array aufgetragen.

• Die Kopien des Moleküls binden durch Hybridisierung an die Stellen des Arrays, wo komplementäre DNA- Einzelstränge (Fragmente) vorhanden sind.

ATG

AGG

TGC

TCC

GTC

GGT

GCA

CAG• Lokalisiere die k-Fragmente (k-Tupel) mittels spektroskopischer Detektoren.

Definition [1]: k-Spektrum einer Sequenz = Menge aller k-Fragmente in der Sequenz

„Sequencing by Hybridization“ (SBH) Problem

Gegeben das k-Spektrum einer Sequenz. Bestimme die Sequenz (Reihenfolge der Buchstaben).


In der vorhergehenden Vorlesung haben wir gelernt, dass man das SBH-Problem unter gewissen „idealen“ Bedingungen als ein Euler-Pfad-Problem interpretieren und lösen kann.

AAATAGACTATTTGTCGAGTGGGCCACTCGCC

A T C G

TCC

TGC

AGG

CAG

GCA

GGT

GTC

ATG

• k-Spektrum S = { ATG, TGC, GCA, CAG, AGG, GGT, GTC, TCC }

AT TG GC AG GG GT TCCA

Euler-Pfad-Ansatz:

Wir betrachten die Teilstrings der Länge k-1 der k-Fragmente

Die Kante führt vom Knoten mit den ersten (k-1) Buchstaben

zum Knoten mit den letzten (k-1) Buchstaben des k-Fragments.

Berechne den (einen) Euler-Pfad des Graphen..

Diese Teilstrings der Länge k-1 sind die Knoten des Graphen G.

Für jedes k-Fragment führen wir eine Kante in den Graph ein.

Definition [2]:

Der im Euler-Pfad-Ansatz definierte Graph heißt der „de Bruijn“ Graph.


Ein Graph kann verschiedene Euler-Pfade besitzen, d.h., jeder Euler-Pfad repräsentiert dann einenanderen Text T, aber nur ein Euler-Pfad repräsentiert den gesuchten Text.

• k-Spektrum S = { ATG, TGG, GGC, GCG, CGT, GTG, TGC, GCA }

AT TG GC

GG

GT CG

CA

T(1) = ATGCGTGGCA

T(2) = ATGGCGTGCA


Variante [1a]:

• Jedes Textfragment f F hat Länge k. √• Die Textfragmente enthalten keine Sequenzierungsfehler.• Alle Textfragmente f der Länge k von T sind in F enthalten.• Es gibt keine Repeats länger als k-2 in T.• T ist ein „echter“ Text (kein DNA Doppelstrang).

Leider funktioniert die Hybridisierung auf DNA-Arrays nicht perfekt. Daten, die mittels DNA-Arrays gewonnen wurden, sind in der Regel sehr stark „verrauscht“ und fehlerhaft.

Die realisierbare Länge k der Fragmente ist „zu klein“ (man benötigt für k = 10 schon ein DNA-Array mit 410 = 1048576 Punkten).SBH wurde Anfang der neunziger Jahre als mögliche Sequenzierungs-technik veröffentlicht und diskutiert. Diese Kombination von DNA-Arraysund Euler-Pfad-Konstruktion hat sich aber aus verschiedenen Gründennicht als Sequenzierungstechnik durchgesetzt.

Diese Überlegungen haben jedoch die Entwicklung der DNA-Arraysinitiiert. DNA-Arrays spielen heutzutage in anderen Bereichen der Bio-informatik und der Biotechnologie eine zentrale Rolle.


Variante [1a]:

• Jedes Textfragment f F hat Länge k. √• Die Textfragmente enthalten keine Sequenzierungsfehler.• Alle Textfragmente f der Länge k von T sind in F enthalten.• Es gibt keine Repeats länger als k-2 in T.• T ist ein „echter“ Text (kein DNA Doppelstrang).

Die heutige Sequenziertechnologie liefert in der Regel Fragmente,sogenannte „Reads“, deren Längen im Bereich zwischen 400 und700 Basen liegen.

Idury und Waterman haben 1995 die folgende Idee formuliert:

„Man imitiere das Fragment-Assembly-Problem als ein SBH-Problem.“

Man bestimme für ein vorgegebenes k (z.B. k = 20) alle k-Fragmente in den Reads und verwende den Euler-Pfad-Ansatz für den Graphen mit Knoten, die die k-1-Fragmente repräsentieren.


Beispiel [1]: k = 10

Read [1] = ATGCGTCTACACTTGGACTGCGTACGTACGT................ ATGCGTCTAC TGCGTCTACA GCGTCTACAC CGTCTACACT GTCTACACTT ..........

ATGCGTCTA TGCGTCTAC

Vorhandene Sequenzierungsfehler „zerstören“ den Euler-Pfad, d.h., der Graphzerfällt eventuell in mehrere Zusammenhangskomponenten.

Pevzner, Tang und Waterman haben im Jahr 2001 eine Technik zur Fehler-korrektur entwickelt, die in praktischen Tests bis zu 97,7 % der vorhandenenFehler korrigiert.


Pevzner&Tang&Waterman (2001):

Sei F = { f1 , ... , fn } die Menge der Fragmente (Reads).

Sei Fk das k-Spektrum aller Reads von F .

Sei U eine obere Schranke für die Zahl der Fehler in jedem der Fragmente.

Idee: Man minimiere die Größe |Fk| des k-Spektrums, indem man in jedem Fragment (Read) maximal U Korrekturen durchführt.

Jeder Fehler generiert k fehlerhafte k-Fragmente (< k falls der Fehler am Rand eines Reads auftritt).

Fehler


Definition [3]:

[a] Zwei k-Fragmente werden Nachbarn genannt, falls sie sich durch eine Mutation (Substitution) unterscheiden, d.h., an einer Position stehen verschiedene Buchstaben.

Fehler

A T G C CA A G C C

[b] Die Vielfachheit eines k-Fragments t ist die Zahl der Vorkommen von t in allen Reads von F. Wir bezeichnen die Vielfachheit mit m(t).

(1) Fehlerhafte k-Fragmente haben in der Regel „korrekte“ Nachbarn.(2) Die „korrekte“ Nachbarn haben in der Regel die größere Vielfachheit.

„korrekte“ Nachbar


Definition [4]:

[a] Ein k-Fragment heißt solide, wenn es in mehr als M Reads vorkommt.

[b] Ein k-Fragment t heißt Orphan (Waise), wenn

1. es nicht solide ist, d.h., m(t) M, 2. es genau einen Nachbarn t‘ hat und 3. m(t) m(t‘).

Für jedes Read f aus F führen wir die folgenden Operationen durch:

1. ZahlDerKorrekturen = 0;

2. Solange (ZahlDerKorrekturen < U)

a. Suche Orphan t aus f mit Nachbar t‘ in Fk, so dass MUTATION(f, t ->t‘) |Fk| um k verkleinert.

b. ZahlDerKorrekturen++;

bis zu 97.7 % FehlerreduzierungProzedur für die Fehlerkorrektur:

MUTATION(f, t->t) ersetzt in dem Read f einen Buchstaben, so dass andieser Stelle nicht mehr t sondern t‘ als k-Fragment auftaucht.


Definition [5]:

Ein Pfad v1 , .... , vn in einem de Bruijn Graph heißt Repeat, falls

a. indegree(v1) > 1b. outdegree(vn) > 1c. indegree(vi) = outdegree(vi) = 1 für i { 2, ..., n }

v2v1 vnvn-1

Die Kanten, die in der Verzweigung v1 enden, heißen Eingänge.

Die Kanten, die in der Verzweigung vn starten, heißen Ausgänge.

Ein Knoten v in einem Graphen wird Quelle genannt, falls indegree(v) = 0 ist. Ein Knoten v wird Senke genannt, falls outdegree(v) = 0 ist. Ein Knoten v wird Verzweigung genannt , falls indegree(v) * outdegree(v) > 1.


v2v1 vnvn-1

Wir nehmen nun an, dass die Vielfachheit der Kanten bekannt ist und dass mindestens ein Euler-Pfad existiert.

Frage: Wie findet man den richtigen Euler-Pfad?

Ein de Bruijn Graph, der den obigen Teilgraphen (das Repeat)enthält, kann nur dann einen Euler-Pfad besitzen, wenn die mittleren Kanten zweimal verwendet werden dürfen, d.h., wenn wir die mittleren Kanten verdoppeln (Multi-Graph) oder wir diesen Kanten eine Vielfachheit von zwei geben.

Man beachte: Falls Text-Repeats und damit auch Repeats im Graphen vorhandensind, muss zunächst für jede Kante die richtige Vielfachheit berechnet werden, sodass der modifizierte Graph überhaupt einen Euler-Pfad besitzt.

In vielen Fällen ist dieses Problem nicht lösbar. In dem Originalpapier von Pevzner,Tang und Waterman (RECOMB 2001) wird dieses Problem ignoriert.


v2v1 vnvn-1

Jedes Vorkommen eines Text-Repeats besitzt einen Eingang und einen Ausgang.Die Information, welcher Ausgang mit welchem Eingang gekoppelt ist (zu einemVorkommen eines Repeats gehört), geht im de Bruijn Graph verloren.

Idee: Jeder Read f (jedes Fragment) aus F entspricht einem Read-Pfad P(f) in dem de Bruijn Graphen.

Falls es einen Read-Pfad gibt, der einen Eingang des Repeats, alle Kanten in der Mitte des Repeats und einen Ausgang des Repeats enthält, dann liefertuns dieser Read-Pfad eine Paarung von einem Eingang und einem Ausgang.

Definition [6]:

Existiert für ein Repeat kein Read-Pfad, der es enthält, so nennt man dasRepeat „Gewirr“ (tangle).


Euler-Superpfad-Problem (Pevzner, Tang, Waterman 2001): Gegeben ein de Bruijn Graph G und einem Menge von Pfaden

P = { P(f1), ... , P(fn) } (Pfade, welche die Reads repräsentieren)

v2v1 vnvn-1

pi

pj

Finde einen Euler-Pfad in G, der alle Pfade in P als Teilpfade enthält.

Das Euler-Pfad-Problem ist ein Spezialfall des Euler-Superpfad-Problems:(1) mit der leeren Menge als Pfadmenge oder(2) oder jede Kante kann auch als eigener Pfad betrachtet werden.


Lösungsansatz:

Führe eine Reihe von Äquivalenztransformationen aus,

(G,P) (G1,P1) (Gk,Pk)

so dass es eins-zu-eins Beziehung zwischen den Euler-Superpfaden in den Gi gibt (so dass der Text der gesuchten Lösung beibehalten wird).

Ziel:

Ein Graph Gk, in dem jeder Pfad aus Pk aus einer Kante besteht, d.h.,

das Euler-Pfad-Problem in Gk liefert dann eine Lösung des Superpfad-Problems in G.

Frage:

Welche Art von Transformation ermöglicht es, Pfade zu Kanten zu reduzieren.

vin

x=(vin,vmid)vmid

vout

y=(vmid,vout)

A T

AT


Transformation:

Zwei aufeinander folgende Kanten können unter gewissen Vorraussetzungen zu einer Kante verschmolzen werden.

Pfade, die im Graph Gi über beide Kanten direkt nacheinander gehen, gehennach der Transformation im Graph Gi+1 über die neue Kante. Ihre Pfadlänge wird hierdurch (um 1) verkleinert.

Fragen:

Unter welchen Vorraussetzungen ist eine solche Transformation erlaubt?

Wann erhält eine solche Transformation die gesuchte Lösung und wann nicht?

Welche Pfade, die nicht beide Kanten verwenden, werden durch eine Verschmelzung der beiden Kanten beeinflusst?

Wir diskutieren im folgenden die einfachen Fälle. Die vollständige Fall-unterscheidung finden Sie in dem RECOMB 2001 Papier von Pevzner,Tang und Waterman.


Transformation bei einfachen Kanten (keine multiplen Kanten).

Py-> = {p| p startet mit y}

P->x = {p| p endet mit x} Px,y = {p| p enthält x und y}

vin

x=(vin,vmid)vmid vout

y=(vmid,vout)

vor Transformation

Wir betrachten zunächst den Fall, dass zwei aufeinander folgende Kanten x und y mit Vielfachheit 1 transformiert werden sollen.

txty

Die Pfade in P, die weder die Kante x noch die Kante y enthalten, werdendurch die Transformation von x und y nicht beeinflusst und müssen deshalbhier nicht betrachtet werden.

Drei Pfadmengen P->x , Px,y , Py-> (siehe Abbildung) müssen in diesem Fall diskutiert werden.


z

vin vmidvout

nach Transformation

1. Ersetze x und y in allen Pfaden in Px,y

durch z.

2. Ersetze y durch z in allen Pfaden in Py->

3. Ersetze x durch z in allen Pfaden in P->x

Py-> = {p| p startet mit y}

P->x = {p| p endet mit x} Px,y = {p| p enthält x und y}

vin

x=(vin,vmid)vmid vout

y=(vmid,vout)

vor Transformation

txty

tz = txty


P->x = {p| p endet mit x}

Beispiel mit mutiplen Kanten: vor Transformation

vin

x=(vin,vmid)vmid

vout1y1 =(vmid,vout1)

vout2y2 =(vmid,vout2)

Px,y1 = {p| p enthält x und y1}

Py1-> = {p| p startet mit y1}

Problem:Wie enden diePfade in P->x ?

Beispiel mit multiplen Kanten: nach Transformation

vin x=(vin,vmid)vmid

vout1z

vout2

y2 =(vmid,vout2)P->x

tz=txty1


Für jeden Pfad p P->x muß entschieden werden, ob (1) x durch z ersetzt wird.(2) er (weiter) mit x endet (Richtung y2).

Definition[6]: Zwei Pfade heißen konsistent, wenn ihre Vereinigung wieder ein Pfad ist.

Ein Pfad p ist konsistent mit einer Menge von Pfaden P,

wenn p zu jedem Pfad in P konsistent ist.




vout1z

vout2


tz=txty1


Sei p P->x : Fall 1: p ist mit genau einer der Pfadmengen Px,y1 und Px,y2 konsistent

vin

x=(vin,vmid)vmid

vout1

vout2

Px,y1

Px,y2

p

(1) x wird durch z in p ersetzt.




vout1z

vout2


tz=txty1


Sei p P->x : Fall 1: p ist mit genau einer der Pfadmengen Px,y1 und Px,y2 konsistent.

vin

x=(vin,vmid)vmid

vout1

vout2

Px,y1

Px,y2

p(2) p endet (weiter) in x.




vout1z

vout2


tz=txty1


Es existiert keine Lösung des Superpfad-Problem

Sei p P->x : Fall 2: p ist inkonsistent mit beiden Pfadmengen Px,y1 und Px,y2

vin

x=(vin,vmid)vmid

vout1

vout2

Px,y1

Px,y2

p




vout1z

vout2


tz=txty1


Existiert ein p P->x mit dieser Eigenschaft, so nennt man x nicht-auflösbar.Nicht-auflösbare Kanten x werden zum Schluss behandelt.

Sei p P->x : Fall 3: p ist konsistent mit beiden Pfadmengen Px,y1 und Px,y2

vin

x=(vin,vmid)vmid

vout1

vout2

Px,y1

Px,y2

p




vout1z

vout2


tz=txty1


Sei x eine nicht-auflösbare Kante (siehe Beispiel unten). In diesen Situationen wendet man Cut-Techniken an.

vin

x=(vin,vmid)vmid

vout1

vout2

Px->

Px->

P->x

P->x

Man kürze die Pfade um x.

vin

x=(vin,vmid)vmid

vout1

vout2


Euler-Schema: Gegeben eine Fragmentmenge F (Menge von Reads).

• Führe Fehlerkorrektur durch.

• Konstruiere den de Bruijn Graphen G von F mit der Read-Pfadmenge P.

• Führe Äquivalenztransformationen durch und berechne Gk.

• Berechne den (einen) Euler-Pfad von Gk.

• Bestimme mittels des Euler-Pfades die gesuchte Sequenz T.


Neisseria Meningitidis

What is meningitis?

Meningitis is an infection of the fluid of a person's spinal cord and the fluid that surrounds the brain. People sometimes refer to it as spinal meningitis. Meningitisis usually caused by a viral or bacterial infection. Knowing whether meningitis is caused by a virus or bacterium is important because the severity of illness and the treatment differ. Viral meningitis is generally less severe and resolves without specific treatment, while bacterial meningitis can be quite severe and may result inbrain damage, hearing loss, or learning disability. For bacterial meningitis, it is also important to know which type of bacteria is causing the meningitis because antibiotics can prevent some types from spreading and infecting other people. Before the 1990s, Haemophilus influenzae type b (Hib) was the leading cause of bacterial meningitis, but new vaccines being given to all children as part of their routine immunizations have reduced the occurrence of invasive disease due to H. influenzae. Today, Streptococcus pneumoniae and Neisseria meningitidis are the leading causes of bacterial meningitis.


Resultate von Pevzner&Tang&Waterman für „Neisseria Meningitidis“:

• Länge des Genoms: 2,184,406 bp.

• 53263 Fragmente mit durchschnittlicher Länge 400 bp.

• 126 perfekte Repeats bis zu einer Länge von 3832bp.

• 255631 Fehler in den Fragmenten (4.8 per Fragment, 1.2 % Fehlerrate).

• 234410 Fehler wurden durch die „Waisenprozedur“ (M=2) eliminiert.

• 1452 Fehler wurden durch die „Waisenprozedur“ produziert.

• l = 20 Tuple-Größe wurde verwendet.

• 4,081,857 = Zahl der Knoten im de Bruijn Graph vor den Äquivalenztransformationen.

• 999 = Zahl der Knoten im de Bruijn Graph nach den Äquivalenztransformationen.

• 1023 = Zahl der Kanten im de Bruijn Graph nach den Äquivalenztransformationen.

• 122 Zusammenhangskomponenten

• 5 Stunden Laufzeit auf einer Sun Enterprise E4500/5500

Documents

Hybridisierung (Hybridization) 1 Sequencing by Hybridization SBH Zentrum für Bioinformatik der Universität des Saarlandes WS 2002/2003