Der Bauplan des Menschen Sequencing by Hybridization SBH Zentrum für Bioinformatik der Universität des Saarlandes WS 2001/2002

Der Bauplan des Menschen

Sequencing by HybridizationSBH

Zentrum für Bioinformatikder Universität des Saarlandes

WS 2001/2002

Hybridisierung (Hybridization)

• 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.

DNA-Arrays oder DNA-Chips

• 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 DNA-Moleküle, in denen man diese Basenfolge nachweisen möchte, 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.

DNA-Arrays oder DNA-Chips

• Durch den Einsatz von photolithographischen Verfahren kann man zweidimensionale DNA-Chips 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

Graphen

• Ein Graph besteht aus Knoten und Kanten.

Hamburg

Berlin

Dresden

Nürnberg

MünchenStuttgart

Saarbrücken

Köln

Frankfurt

Mannheim

300 km

200 km

200 km

200 km

150 km

250 km

50 km

100 km

450 km

400 km

300 km

200 km

200 km

• G = (V,E), wobei V die Menge der Knoten (vertices) und E die Menge der Kanten E (edges) ist.

• Der Grad eines Knoten ist gleich der Zahl der Kanten, die im Knoten enden.

Graphen




v1

v3

v2 v4

v5

v6 v7

v8

v9

v10

e1=(v1,v2)

e2=(v1,v3)

e5=(v3,v5)e4=(v3,v4)

e7=(v4,v7)

e6=(v4,v5)

e12=(v7,v8)

e3=(v2,v5)

e9=(v5,v7)

e13=(v8,v9)

e10=(v6,v9)

e8=(v5,v6)e11=(v6,v10)

Graphen




v1

v3

v2 v4

v5

v6 v7

v8

v9

v10

e1=(v1,v2)

e2=(v1,v3)

e5=(v3,v5)e4=(v3,v4)

e7=(v4,v7)

e6=(v4,v5)

e12=(v7,v8)

e3=(v2,v5)

e9=(v5,v7)

e13=(v8,v9)

e10=(v6,v9)

e8=(v5,v6)e11=(v6,v10)

Ein Pfad von Knoten vi nach Knoten vj ist eine Folge von Knoten vi , v?, ...., vj , wobei jedes Paar von aufeinander folgen-den Knoten vk, vl durch eine Kante (vk, vl) verbunden ist.

Ein Pfad wird als einfach bezeich-net, wenn jeder Knoten in der Pfadbeschreibung genau einmalvorkommt.

Graphen




v1

v3

v2 v4

v5

v6 v7

v8

v9

v10

e1=(v1,v2)

e2=(v1,v3)

e5=(v3,v5)e4=(v3,v4)

e7=(v4,v7)

e6=(v4,v5)

e12=(v7,v8)

e3=(v2,v5)

e9=(v5,v7)

e13=(v8,v9)

e10=(v6,v9)

e8=(v5,v6)e11=(v6,v10)



Ein Pfad wird als Circuit bezeich-net, wenn der erste und der letzteKnoten des Pfades identisch sind.

v3 v5 v6 v9 v8 v7 v5 v3

Graphen




v1

v3

v2 v4

v5

v6 v7

v8

v9

v10

e1=(v1,v2)

e2=(v1,v3)

e5=(v3,v5)e4=(v3,v4)

e7=(v4,v7)

e6=(v4,v5)

e12=(v7,v8)

e3=(v2,v5)

e9=(v5,v7)

e13=(v8,v9)

e10=(v6,v9)

e8=(v5,v6)e11=(v6,v10)



Ein Pfad wird als Circuit bezeich-net, wenn der erste und der letzteKnoten des Pfades identisch sind.

v3 v5 v6 v9 v8 v7 v5 v3

Ein Circuit (Rundgang) wird alseinfach (oder als Kreis) bezeich-net, falls alle Knoten außer demersten und dem letzten nur einmalauftreten: v3 v5 v6 v9 v8 v7 v4 v3

Graphen

• Ein bipartiter Graph besteht aus zwei disjunkten Mengen von Knoten (rot, blau).

Mitarbeiter Aufgaben

• Es gibt nur Kanten zwischen einem roten und einem blauen Knoten.

• Haben die Kanten eine Richtung, so spricht man von einem gerichteten Graphen (andernfalls von einem ungerichteten Graphen).

Graphen

Existiert zwischen jedem Knotenpaar eine Kante, so spricht man von einem vollständigen Graphen.

Euler-Graphen

Der Schweitzer Mathematiker Leonard Euler hat sich 1736 mit der folgenden Fragestellung, dem sogenannten Königsberger-Brückenproblem, beschäftigt:

A

B

C DPregel

Ist es möglich, von irgendeinem Punkt in der Stadt loszulaufen und zu diesem Punkt wiederzurückzukehren und dabei genau einmal über jede der sieben Brücken zu wandern.

Euler-Graphen


A

B

C DPregel


Euler-Graphen


A

B

C D

= Gibt es einen Circuit in diesem Graphen, der jede Kante nur einmal „begeht“ (verwendet)?

Multi-Graph: Mehrere Kanten zwischenzwei Knoten sind erlaubt.


Nein! Warum kann es keinen solchen Circuit geben?

Euler-Graphen


A

B

C D

Multi-Graph: Mehrere Kanten zwischenzwei Knoten sind erlaubt.

Nein! Warum kann es keinen solchen Circuit geben?

Antwort: Es gibt Knoten mit ungeradem Grad (3 und 5). Ein solcher Circuit kann aber nur existieren, wenn alle Knoten geraden Grad haben und der Graph zusammenhängend ist.

Ein Graph heißt zusammenhängend(connected), wenn man von jedem Knoten aus jeden anderen Knoten über einen Pfad erreichen kann.

Euler-Graphen

Definition: Ein Graph heißt Euler-Graph, wenn jeder Knoten einen geraden Grad hat und der Graph zusammenhängend ist.

Satz: Ein Graph besitzt genau dann einen Euler-Circuit, wenn der Graph ein Euler-Graph ist.

A

B

C D

E F

G

H

I

Wir beweisen die schwierigere Richtung (Euler-Graph => Euler Circuit)mittels vollständiger Induktion über die Anzahl m der Kanten:Induktionsstart: m = 2 (trivial).Induktionsannahme: Jeder zusammenhängende Graph mit weniger alsm Kanten, dessen Knoten alle geraden Grad haben, besitzt eine Euler-Tour.

Sei G=(V,E) ein Euler-Graph mit m Kanten.1. Bestimme in G einen Kreis. Zum Beispiel K=ACBDA.2. Lösche die Kanten von K.

Euler-Graphen

Definition: Ein Graph heißt Euler-Graph, wenn jeder Knoten einen geraden Grad hat und der Graph zusammenhängend ist.


A

B

C D

E F

G

H

I

Wir beweisen die schwierigere Richtung (Euler-Graph => Euler Circuit)mittels vollständiger Induktion über die Anzahl m der Kanten:Induktionsstart: m = 2 (trivial).Induktionsannahme: Jeder zusammenhängende Graph mit weniger alsm Kanten, dessen Knoten alle geraden Grad haben, besitzt eine Euler-Tour.

Sei G=(V,E) ein Euler-Graph mit m Kanten.1. Bestimme in G einen Kreis. Zum Beispiel K=ACBDA.2. Lösche die Kanten von K. Den neuen Graphen nennen wir G‘.

Alle Knoten von G‘ haben geraden Grad.Aber der Graph G‘ kann aus mehreren Zusammenhangskom-ponenten (ZKs) mit weniger als m Kanten bestehen:

Z(1) = {A}, Z(2) = {D}, Z(3) = {H,I,C}, Z(4)={B,E,G,F}

3. Bestimme die Zusammenhangskomponenten von G‘4. Starte für alle Zusammenhangskomponenten diesen (rekursiven) Algorithmus zur Berechnung eines Euler-Circuits: Circ(Z(3)) = CIHC Circ(Z(4)) = BEGFB5. Mische den Kreis K und die Euler-Circuits der ZKs:

Circuit = ACIHCBEGFBDA

Wie durchsucht man einen Graphen?

v1

v3

v2 v4

v5

v6 v7

v8

v9

v10

Zusammenhangskomponenten: Gegeben ein ungerichteter Graph G=(V,E) und ein Knoten v.

ZK (G,v):

1. Markiere v;

2. Für alle Kanten (v,w) führe die folgenden Operationen aus:

a. Falls w nicht markiert ist, dann starte

ZK(G,w);

Bestimme die Zusammenhangskomponente, zu der v gehört.

Die Laufzeit von ZK(G,v) ist O(#Kanten in ZK(v)).


v4

v1

v3

v2

v5

v6 v7

v8

v9

v10


ZK (G,v, NummerDerZK):

1. Markiere v mit NummerDerZK;



ZK(G,w,NummerDerZK);

Bestimme alle Zusammenhangskomponenten von G.

Die Laufzeit von ZK(G,v, ..) ist O(#Kanten in ZK(v)).

1

1

1

1

1

1 1 1

1

1

Zusammenhangskomponenten(G): NummerDerZK = 0;Solange es in G einen unmarkierten Knoten v gibt:NummerDerZK++;

Die Laufzeit des obigen Algorithmus ist O(|V|+|E|).


v4

v1

v3

v2

v5

v6 v7

v8

v9

v10


ZK (G,v, NummerDerZK):

1. Markiere v mit NummerDerZK;



ZK(G,w,NummerDerZK);

Bestimme alle Zusammenhangskomponenten von G.

Die Laufzeit von ZK(G,v, ..) ist O(#Kanten in ZK(v)).

Zusammenhangskomponenten(G): NummerDerZK = 0;Solange es in G einen unmarkierten Knoten v gibt:NummerDerZK++;

Die Laufzeit des obigen Algorithmus ist O(|V|+|E|).

1

1

1

1

1

2 2 2

2

2

Euler-Graphen

Definition: Ein gerichteter Graph heißt Euler-Graph, wenn der Graph zusammenhängend und balanciert ist.


Definition: Ein Knoten v eines gerichteten Graphen ist balanciert, wenn die Zahl der in v endenden Kanten gleich der Zahl der in v startenden Kanten ist.

Definition: Ein gerichteter Graph ist balanciert, wenn jeder Knoten des Graphen balanciert ist.

Beweis: Analog zum konstruktiven Beweis im Falle des ungerichteten Graphen.

Definition: Ein Graph besitzt einen Euler-Pfad, wenn es einen Pfad im Graphen gibt, der jede Kante genau einmal verwendet bzw. genau einmal über diese Kante geht.

Definition: Ein Knoten v eines gerichteten Graphen ist semi-balanciert falls | indegree(v) – outdegree(v) | = 1.

Euler-Graphen

Definition: Ein Graph besitzt einen Euler-Pfad, wenn es einen Pfad im Graphen gibt, der jede Kante genau einmal verwendet bzw. genau einmal über diese Kante geht.

Definition: Ein Knoten v eines gerichteten Graphen ist semi-balanciert falls | indegree(v) – outdegree(v) | = 1.

Satz: Ein zusammenhängender Graph besitzt genau dann einen Euler-Pfad, wenn er höchstens zwei semi-balancierte Knoten besitzt und alle anderen balanciert sind.

Beweis: Analog zum Beweis der Existenz eine Euler-Circuit (mit mehr Fallunterscheidungen).

Sequencing by Hybridization (SBH)

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 l-Tupeln (alle Basenfolgen der Länge l).

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 l-Tuple vorhanden sind.

ATG

AGG

TGC

TCC

GTC

GGT

GCA

CAG• Lokalisiere die l-Tuple mittels spektroskopischer Detek- toren.

• Rekonstruiere die Sequenz anhand ihrer l-Tuple mit Hilfe von kombinatorischen Algorithmen.

Definition: l-Spektrum einer Sequenz = Menge aller l-Tuple, die in der Sequenz auftreten.

Shortest Superstring Problem

• Rekonstruiere die Sequenz anhand ihres l-Spektrums mit Hilfe von kombinatorischen Algorithmen.

Shortest-Superstring-Problem: Gegeben eine Menge von Strings { S1, ... , Sm }.Man berechne einen kürzesten (Super) String S, der alle Si als Teilstrings enthält.

Das Shortest-Superstring-Problem ist NP-vollständig.Es kann als eine Variante des Traveling-Salesman Problem formuliert werden. Jeder String Si wird durch einen Knoten eines gerichteten vollständigen Graphen G=(V,E) repräsentiert.

ATG

TGC GCA

CAG

AGG

GGTGTC

TCC

Die Kante von Si nach Sj erhält ein Gewicht von „– overlap(Si , Sj)“, wobei der „Overlap“ die Länge des maximalen Präfixes von Sj ist, das auch Suffix von Si ist.

-2

00

-2-2

-2-2

-2

-2

Hamiltonian Path: Berechne den kürzesten Pfad,

der jeden Knoten genau einmalbesucht.

Euler-Pfad-Ansatz

• Rekonstruiere die Sequenz anhand ihres l-Spektrums mit Hilfe von kombinatorischen Algorithmen.

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

AT TG GC AG GG GT TCCA

Euler-Pfad-Ansatz: Wir betrachten alle (l-1)-Tuple.

Für jedes l-Tuple im l-Spektrum führen wir eine Kante in den Graph ein.

Die Kante führt vom Knoten mit den ersten (l-1) Buchstaben des l-Tuple

zum Knoten mit den letzten (l-1) Buchstaben des l-Tuple.

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

Ein Graph kann mehrere (viele) Euler-Pfade besitzen.

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

AT TG GC

GG

GT CG

CA

Euler-Pfad-Ansatz

Wie kann man testen, ob ein Euler-Graph einen eindeutig bestimmten Euler-Circuit besitzt?

• Man zerlege den Euler-Graph in einfache Kreise.

A

B

C D

E F

G

H

I

„Einfach“ bedeutet, dass jede Kante zu genau einem Kreis gehört.

K1 K2

K3

Der Schnittgraph G= (V, E) dieser Kreise ist wie folgt definiert:

Die Kreise des Graphen sind die Knoten V = { K1 , ... , Kn }.

Für jeden Knoten, den Ki und Kj gemeinsam haben, wird eineKante zwischen Ki und Kj eingeführt.

Satz:

Ein Euler-Graph hat genau dann einen eindeutig bestimmtenEuler-Circuit, wenn der Schnittgraph ein Baum ist.

Probleme mit SBH und dem Euler-Pfad-Ansatz

Fehler bei der Hybridisierung oder bei der Auswertung des DNA-Arrays? Eliminieren den Euler-Pfad.

Repeats länger als (l-1) Buchstaben. Eliminieren den Euler-Pfad.

ATCTG.....TTCTA

AT TG

TA

CTTC

TT

Mit DNA-Arrays (SBH) kann man nur sehr kurze DNA-Moleküle sequenzieren.Man hat auch nur sehr kurze l-Tuple (l=8) zur Verfügung.

Euler-Superpfad-Problem

Fragment-Sequence-Assembly-Problem:

(5) Assemblieren

ATGCGGTTGCTACGT ATCGGTGACCA ATTCATGCGGTTGC CGTCGTATCG GACCACGGTT TCATGCGG ACGTCGT TCGGTGACCACGGTTATTCATG GGTTGCTAC CGTATCG ACCACGG--------------------------------------ATTCATGCGGTTGCTACGTCGTATCGGTGACCACGGTT

ATGGCCTCGTCAATGCATGCCGGTGCATGCATGGCCTCGTCAA

• Man suche alle Paare von Text- fragmenten, die sich überlappen, d.h., das Ende des einen Frag- ments ist identisch oder ähnelt dem Anfang des anderen Frag- ments oder umgekehrt.

• Mit Hilfe dieser Überlappungs- informationen versucht man das riesige Textpuzzle zusammen- zusetzen und den Originaltext zu rekonstruieren.

Gegeben eine große Zahl (10 x Überdeckung) von sequenzierten Fragmenten der Länge ca. 500 bp.



(5) Assemblieren


Idury & Waterman (1995): Idee: SBH Nachahmen.

Zerlege jedes Fragment der Länge n in (n-l+1) l-Tuple (z.B. l = 20).

AATGCCCGTTGCTACTGCGACGTCACGTGCATGCG........................................................AATGCCCGTTGCTACTGCG ATGCCCGTTGCTACTGCGA TGCCCGTTGCTACTGCGAC GCCCGTTGCTACTGCGACG CCCGTTGCTACTGCGACGT CCGTTGCTACTGCGACGTC usw.

Generiere Graph wie bei SBH mit den entsprechenden (l-1) Tuples.

Berechne den (einen) Euler-Pfad.



(5) Assemblieren


Idury & Waterman (1995): Idee: SBH Nachahmen.

Zerlege jedes Fragment der Länge n in (n-l+1) l-Tuple (z.B. l = 20).

Generiere Graph wie bei SBH mit den entsprechenden (l-1) Tuples.

Berechne den (einen) Euler-Pfad.

Dieser Ansatz funktioniert, falls 1. perfekte Daten (keine Fehler) vorliegen.

2. keine Repeats, die länger als (l-2) sind, vorkommen.

Wie kann man die Zahl der Fehler reduzieren?

Pevzner&Tang&Waterman (2001):

Sei S = { s1 , ... , sn } die Menge der Fragmente. Sei Sl-1 das (l-1)-Spektrum von S.

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

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

Jeder Fehler generiert (l-1) fehlerhafte Tuple (< (l-1) falls am Rand eines Fragments).

Brute-Force-Ansatz (Greedy):

Für alle Fragmente:

1. ZahlDerKorrekturen = 0;

2. Solange (ZahlDerKorrekturen < U)

a. Bestimme Korrektur, so dass |Sl-1| um (l-1) verkleinert wird.

b. ZahlDerKorrekturen++;

Tests von Pevzner&Tang&Waterman (2001) zeigen, dass die Zahl der Sequenzierungsfehler um

86.5 % reduziert werden.

Wie kann man die Zahl der Fehler reduzieren?



Ein (l-1) Tuple heißt solide, wenn es in mehr als M Fragmenten vorkommt.

Beispiel: M = 5 (2) für 10 x Überdeckung.

Zwei (l-1) Tuple heißen Nachbarn, wenn sie eine Mutation voneinander „entfernt“ sind.

Ein (l-1) Tuple t heißen 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 alle Fragmente:

1. ZahlDerKorrekturen = 0;

2. Solange (ZahlDerKorrekturen < U)

a. Suche Orphan t, so dass ERSETZE(t durch t‘) |Sl-1| um (l-1) verkleinert.b. ZahlDerKorrekturen++;

97.7 % Fehlerreduzierung




G(Sl-1) = (V,E) sei der sogenannte de Bruijn Graph mit

V = (l-1) Spektrum von S.

E = {(vi , vj) | vi und vj repräsentieren „benachbarte“ (l-1) Tuples }

Genauer: Jede Kante in G entspricht einem l-Tuple t von S.

vi repräsentiert die ersten (l-1) Buchstaben von t.

vj repräsentiert die letzten (l-1) Buchstaben von t.

Bemerkung: Der de Bruijn Graph besitzt einen (eindeutigen) Euler-Pfad, wenn

1. keine Sequenzierungsfehler in den si vorliegen,

2. keine Repeats, die länger als (l-2) sind, in den si vorkommen und

3. der Graph zusammenhängend ist (keine Überdeckungslücken vorkommen).

Contig 1 Contig 2



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

a. indegree(v1) > 1

b. outdegree(vn) > 1

c. indegree(vi) = outdegree(vi) = 1 für i {2, ..., n}

v2v1 vnvn-1

Ein Euler-Pfad besucht diesen Teilpfad mehrmals (Multiplizität der Kanten ?, Multigraph?).

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

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

Jedes Vorkommen eines Repeats besitzt einen Eingang und einen Ausgang.

Die Information, welcher Ausgang mit welchem Eingang gekoppelt ist (zu einem Vorkommen eines Repeats gehört), geht im de Bruijn Graph verloren.



Euler-Superpfad-Problem: Gegeben ein de Bruijn Graph G und einem Menge von Pfaden P

v2v1 vnvn-1

(die Pfade, die den Fragmenten entsprechen).

pi

pj

Finde einen Euler-Pfad in diesem Graph, der

alle Pfade von P als Teilpfade enthält.

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.



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.

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.

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


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

vin vmidvout

z

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


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,y = {p| p enthält x und y1}

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

Beispiel mit multiplen Kanten: nach Transformation

P->x

vin x=(vin,vmid)vmid

vout1z

vout2

y2 =(vmid,vout2)



Problem:Wie enden diePfade in P->x ?



P->x


vout1z

vout2

y2 =(vmid,vout2)




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

Definition: 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.



P->x


vout1z

vout2

y2 =(vmid,vout2)




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

vin

x=(vin,vmid)vmid

vout1

vout2

Px,y1

Px,y2

p

(1) x wird durch z in p ersetzt.



P->x


vout1z

vout2

y2 =(vmid,vout2)




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

vin

x=(vin,vmid)vmid

vout1

vout2

Px,y1

Px,y2

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



P->x


vout1z

vout2

y2 =(vmid,vout2)




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



P->x


vout1z

vout2

y2 =(vmid,vout2)




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


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


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 eliminiert.

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

• 4,081,857 = Zahl der Knoten im de Bruijn Graph bevor das Superpfad-Problem gelöst wurde.

• 999 = Zahl der Knoten im de Bruijn Graph nachdem das Superpfad-Problem gelöst wurde.

• 1023 = Zahl der Kanten im de Bruijn Graph nachdem das Superpfad-Problem gelöst wurde.

• 122 Zusammenhangskomponenten

• 5 Stunden Laufzeit auf einer Sun Enterprise E4500/5500

Documents

Der Bauplan des Menschen Sequencing by Hybridization SBH Zentrum für Bioinformatik der Universität des Saarlandes WS 2001/2002