Die Suche nach Signalen und Genen in DNA Zentrum für Bioinformatik der Universität des Saarlandes WS 2001/2002

Die Suche nach Signalen und Genen

in DNA

Zentrum für Bioinformatikder Universität des Saarlandes

WS 2001/2002

Was versteht man unter Signalen in DNA?

• Unter Signalen verstehen wir bestimmte in der Regel kurze Stücke von DNA, die wichtige Informationen für bestimmte Prozesse enthalten.

Transkriptionsfaktoren

ATGCGTGCAATGT..........AGGCACGCATGA

TGACGCA CACGTG GGGCGG CCAAT TATA ATG TGAExon Intron ExonPromoter

• In der Regel binden andere Moleküle an diese Signalketten und eine chemische Reaktion wird dadurch gestartet oder gestoppt.

Transcription factor binding sites regulation of gene expression transcription factors

Splicing sites splicing of exons (and introns)

Splicing site

Sites of the restriction enzym

transcription factor binding site

DNA cutting restriction enzymes

Beispiele

Transcription factor binding sites

Sites of the restriction enzym

TTGACAN17TATAAT E. coli promoter binding site

N {A,T,C,G}

GAATTC EcoRI

CCAN9TGG Xcm I restriction enzyme

PumCN40-2000PumC McrBC Endonuclease

Pu {A,G}

Wie kann man diese magischen Worte in einer vorgegebenen Menge von Sequenzen finden?

Der triviale Ansatz, alle Worte der Länge l in allen vorgegebenen Sequenzen zu suchen, istnatürlich nur bei kurzen Worten ohne Lücken und Mutationen erfolgreich.

Genereller Ansatz (Idee)

Annahme:

Ein populärer Ansatz in der DNA-Linguistik basiert auf der Annahme, dass DNA-Signale in der Regel Worte sind, die häufig oder selten vorkommen.

Wie kann man potentielle Signal-Muster finden und ihre statistische Signifikanz beweisen?

Ansatz:

(1) Man definiere ein Fitness-Maß (z.B. Häufigkeit des Auftretens).

(2) Berechne die Häufigkeit von jedem Wort in einer Menge von DNA-Fragmenten.

(3) Gebe das beste Wort oder die besten Worte als potentielle Signale aus.

Wie kann man entscheiden, ob ein Wort W häufig oder selten vorkommt?

Hierzu benötigt man den Erwartungswert E(W) und die Varianz Var(W)=2(W) für die Zahl derVorkommen eines Worts W.

)()()()()()( 222 WEWEWEWEWEWVar

"Best Bet For Simpletons"

Für L > 2 gilt: Welches Wort der Spieler (1) auch auswählt, Spieler (2) kann immer ein Wortfinden, dass bessere Gewinnchancen hat.

Definition:

Gegeben zwei L-Worte A und B über dem binären Alphabet {0,1}.Die Korrelation AB = (c0 , ... , cL-1 ) ist ein L-Wort, dessen Komponenten wie folgt definiert sind:

Spiel mit zwei Spielern:

Spieler 1 wählt ein binäres Wort A der Länge L. Spieler 2 kennt das Wort, das Spieler 1 gewählt hat.

Spieler 2 wählt anschließend ein (anderes) binäres Wort B der Länge L.

Dann werfen Sie solange {0,1}-Münzen, bis entweder das Wort A oder das Wort B erscheint.

Spieler (1) wählt A = 00 Spieler (2) wählt B = 10 Münzwürfe: 0 1 1 0 = B

0

1ic

falls die ersten (L-i) Buchstaben von B gleich den letzten (L-i) Buchstaben von A sind.

sonst A = 01101B = 11011 11011 11011 11011 11011

AB = 0 001 1


Definition:

Gegeben zwei L-Worte A und B über dem binären Alphabet {0,1}.Die Korrelation AB = (c0 , ... , cL-1 ) ist ein L-Wort, dessen Komponenten wie folgt definiert sind:

0

1ic

falls die ersten (L-i) Buchstaben von B gleich den letzten (L-i) Buchstaben von A sind.

sonst

Das Korrelationspolynom definiert man als 1

110 ...)( LLAB tctcctK

Ferner sei KAB = KAB(1/2).

Mit HAB bezeichen wir die Menge der „Reste“ von A: Für jedes i mit ci = 1 fügt man die ersten i Buchstaben von A als Wort zu HAB.

AB =

A = 01101B = 11011 11011 11011 11011 11011

0 001 1 HAB = { 0, 0110}

Für jedes ci = 1 wird ein ergänzender Präfix von A zu HAB hinzugefügt (Rest ohne die überlappenden Teile).

Mit A * B bezeichnet man die Konkatenation von A und B. Sind X und Y zwei Wortmengen,

so bezeichnen wir mit X * Y die Menge aller aus X und Y konkatenierten Wörter. |X *Y|=| X | | Y |.


Definition:

Ein Wort W ist ein A-Gewinn, wenn A am Ende des Wortes steht und W das Wort B nicht enthält.Ein Wort W ist ein A-Vorgewinn, wenn W*A ein A-Gewinn ist.

Die Wahrscheinlichkeit P(W) eines binären Wortes W der Länge L ist gleich

LWP

2

1)(

Für eine Menge X von Worten sei

X

XPP )()(

Lemma: KAB(1/2) = P(HAB)

Ein Wort W ist ein B-Gewinn, wenn B am Ende des Wortes steht und W das Wort A nicht enthält.Ein Wort W ist ein B-Vorgewinn, wenn W*B ein B-Gewinn ist.

AB =

A = 01101B = 11011 11011 11011 11011 11011

0 001 1 HAB = { 0, 0110}

Für jedes ci = 1 wird ein ergänzender Präfix von A zu HAB hinzugefügt (Rest ohne die überlappenden Teile).

1110 ...)(

LLAB tctcctK


Wir betrachten die Wortmenge = { W | W ist weder A- noch B-Gewinn}.

Jedes Wort W*A mit W ist entweder ein A-Gewinn oder ein B-Gewinn.

Falls W*A ein A-Gewinn ist, W A

A

HAA

= (VGB*HBB) (VGA*HAB)

= (VGA*HAA) (VGB*HBA) A-Vorgewinn VGA

Falls W*A ein B-Gewinn ist, W A

B

B-Vorgewinn HBA

VGB

Falls W*B ein B-Gewinn ist, W B

B

B-Vorgewinn HBB

Falls W*B ein A-Gewinn ist, W B

A

A-Vorgewinn HAB

VGA

VGB


= (VGB*HBB) (VGA*HAB) (VGA*HAA) (VGB*HBA)

=> P(VGA *HAA) + P (VGB*HBA) = P(VGB*HBB) + P(VGA*HAB)

=> P(VGA ) P(HAA) + P (VGB) P(HBA) = P(VGB) P(HBB) + P(VGA) P(HAB)

=> P(VGA ) KAA + P (VGB) KBA = P(VGB) KBB + P(VGA) KAB Lemma

P(VGB ) KAA - KAB

P(VGA) KBB - KBA

=

Satz (Conway):

Die Wahrscheinlichkeit, dass das Wort B gegen A gewinnt, kann man durch den folgendenQuotienten der Wahrscheinlichkeiten der Vorgewinne von A und B abschätzen:

P(VGB ) KAA - KAB

P(VGA) KBB - KBA

=

Beweis: Siehe oben (Pevzner [1993]).

Li [1980]Guibas & Odlyzko [1981]).

Die Varianz von Worten in einem Bernouilli-Text

Gegeben ein Bernouilli-Text der Länge n über einem Alphabet mit r Buchstaben.

Wir nehmen an, dass der Text circulär ist.

Die Wahrscheinlichkeit, dass ein Buchstabe an einer bestimmten Position auftritt, ist (1/r).

Sei W ein Wort der Länge L.

Die Zufallsvariable xi hat den Wert 1, falls das Wort W an der i-ten Position im Text startet (0 sonst).

Die Zahl der Vorkommen von W wird durch die folgende Zufallsvariable beschrieben:

n

iixX

1

npr

nxEXEL

n

ii :

1)()(

1

)()()()()()(},1{

22ji

njiji xExExxEXEXEXVar

)()()(

)()()(

)()()(

}||0:),{(

}0|:|),{(

}|:|),{(

jiLjiji

ji

jijiji

ji

jiLjiji

ji

xExExxE

xExExxE

xExExxE

0

n(p-p2)

? (siehenächsteSeite)


n

i

L

tji

tjijjiji

Ljijiji xExExxExExExxE

1

1

1 }|:|{}||0:),{(

)()()()()()(

ii+t

0

1)( ttii r

pxxE

falls der t-te Koeffizient ct des Korrelations-polynoms KWW gleich 1 ist

sonst

tttii rpcxxE

1)(

)1)1

((21

2)(1

1

1

1 }|:|{

rKp

rcpxxE WWt

L

tt

L

t tjijji

))1(2)1)1

((2()()()( 2

1}||0:),{(

pLr

KpxExExxEn

iWWji

Ljijiji

))1(2)1)1

((2( pLr

Knp WW


Gegeben ein Bernouilli-Text der Länge n über einem Alphabet mit r Buchstaben.

Wir nehmen an, dass der Text circulär ist.

Die Wahrscheinlichkeit, dass ein Buchstabe an einer bestimmten Position auftritt, ist (1/r).

Sei W ein Wort der Länge L.

Die Zufallsvariable xi hat den Wert 1, falls das Wort W an der i-ten Position im Text startet (0 sonst).

Die Zahl der Vorkommen von W wird durch die folgende Zufallsvariable beschrieben:

n

iixX

1

npr

nxEXEL

n

ii

1)()(

1

)()()()()()(},1{

22ji

njiji xExExxEXEXEXVar

)()()(

)()()(

)()()(

}||0:),{(

}0|:|),{(

}|:|),{(

jiLjiji

ji

jijiji

ji

jiLjiji

ji

xExExxE

xExExxE

xExExxE

0

n(p-p2)

))1(2)1)1

((2( pLr

Knp WW

))12()1)1

((2()( pLr

KnpXVar WW


Beispiel:

Für ein Alphabet mit vier gleich wahrscheinlichen Buchstaben A,T, C, G gilt:

13

21

)(

)(

ATVar

AAVar

59

99

)(

)(

ATGVar

AAAVar

Die folgenden Arbeiten präsentieren Approximations-Formeln für die Varianz von Texten,die durch Markov-Ketten generiert wurden:

• Fousler & Karlin [1987]

• Stuckle et al. [1990]

• Kleffe & Borodowsky [1992]

Die Grenzverteilung für die Zahl von Wortvorkommen im Markov-Modell haben

• Prum et al. [1995] veröffentlicht.

Exakte und approximative Formeln für den Erwartungswert, die Varianz und die Wahrscheinlichkeitvon approximativen Wortvorkommen haben

• Regnier & Szpankowski [1998] veröffentlicht.

Consensus-Wort-Analyse

Bezeichnung:

Für ein Wort W und eine Menge von Sequenzen bezeichnen wir mit nW(S) die Zahl der Vorkommenvon W in S.

Problem:

Suche das Wort W der Länge L, das am häufigsten vorkommt (mit maximalem nW(S)).

Lösung:

Trivial: Zähle alle Worte der Länge L in S.

Problem:

Suche das Wort W der Länge L, das approximativ am häufigsten vorkommt.Hierbei erlaubt man bis zu k Fehler (mismatches).

Lösung:

• Waterman et al. [1984]• Galas et al. [1985] haben TTGACA und TATAAT als Promoter-Signale von E.coli identifiziert.

Consensus-Wort-Analyse

Consensus-String-Problem (CSP):

Gegeben eine Menge S={s1, ... , sn} von Sequenzen und eine ganze Zahl L,

finde einen Median-String s der Länge L und einen Teilstring t i der Länge L für jede Sequenz si,

so dass die folgende Summe der Abstände (Hamming-Distanz) minimal ist.

),(1

i

n

iH tsd

Lösung:

Li et al. [1999] zeigten, dass CSP „NP-hard“ ist, und präsentierten ein PTAS (Polynomial Time Approximation Scheme).

CG-Inseln und Münzwürfe

Das seltenste Dinukleotid in vielen Genomen ist CG. Es existieren jedoch häufig sogenannteCG-Inseln in der Nähe von Genen, wo CG relativ gehäuft vorkommt.

Wie kann man feststellen, ob ein bestimmter Bereich mit einigen CGs eine CG-Insel ist?

Dieses Problem ist mit dem folgenden Münzwurfproblem (Durbin et al. [1998]) verwandt:

Ein Spieler hat zwei Münzen zur Verfügung, eine „normale“ Münze mit Wahrscheinlichkeit ½für Kopf (0) und Zahl (1) und eine „gezinkte“ Münze mit Wahrscheinlichkeit ¾ für Kopf (1) und¼ für Zahl (0).

Der Spieler kann diese Münzen während des Spiels auswechseln, ohne dass es die Mitspieler erkennen können. Er wechselt jedoch selten (Wahrscheinlichkeit 0.1) wegen der Gefahr, doch erwischt zu werden.

Sei x = x1x2....xn eine Folge von Münzwurfen ohne Vertauschen der Münzen:

n

n

iixpnormalxP

2

1)()|(

1

n

k

k

k

kn

n

iixpgezinktxP

4

3

4

3

4

1)()|(

1

k ist die Anzahl der Einsen (1)

nn

k

2

1

4

3 nk 23

)3(log2

nk wurde wahrscheinlich mit der gezinkten

Münze geworfen.

Ein einfaches Hidden-Markov-Model

HMM:

• sei ein Alphabet.

Beispiel: Münzwürfe mit normaler und gezinkter Münze:

• = { 0, 1} (Zahl oder Kopf).

• Q sei eine Menge von Zuständen, die Symbole aus produzieren.

• Q = { normal, gezinkt}, je nachdem, mit welcher Münze geworfen wird.

• A = (aij) ist eine |Q|x|Q| Matrix mit Wahrscheinlichkeiten von Zustandsübergängen.

• anormal,normal = agezinkt, gezinkt = 0.9 und anormal, gezinkt = agezinkt, normal = 0.1.

• P = (pq()) ist eine |Q|x|| Matrix mit „Produktionswahrscheinlichkeiten“.

• pnormal(0) = ½ , pnormal(1) = ½, pgezinkt(0) = ¼ , pgezinkt(1) = ¾ .

Ein Pfad q = q1q2...qn in einem HMM ist eine Folge von Zuständen, z.B., normal, gezinkt, normal, ....

Die Wahrscheinlichkeit, dass eine Folge x = x1x2 ... xn von Münzwürfen durch einen Pfad q generiertwurde, ist

)|()|()|( 11

iii

n

ii qqPqxPqxP 1,

11,0,

1, )()(

110

ii

n

iiqqq

n

iiqqq axpaaxpa

iiii

wobei a0 und an+1 die fiktiven Start- und Endzustände „begin“ und „end“ sind.


Dekodierungsproblem:

Man finde einen optimalen Pfad q* = arg maxq P(x|q) für x, so dass P(x|q) maximiert wird.

Das vorhergehende Model definiert die Wahrscheinlichkeit für eine gegebene Folge x von Münzwürfenund einen (bekannten) Pfad von Zuständen.

Normalerweise kennt jedoch nur der Spieler den Pfad, der die Münzen wirft.

Man spricht daher auch von einem „versteckten“ (hidden) Pfad.

Idee:

Man betrachte einen Präfix x1x2 ... xi+1 und man überlege, wie man den optimalen Pfad für diesen Präfix und einen beliebigen Status qi+1 rekursiv aus den optimalen Pfaden desPräfix x1x2 ... xi berechnen kann.

Sei wq(i) die Wahrscheinlichkeit des wahrscheinlichsten Pfades für den Präfix x1x2 ... xi ,der xi aus dem Zustand q produziert:

)1( iwq )( 1 iq xp

Initialisierung:

1)0( beginw und 0)0( kw für k begin.

})({max)|( ,*

endkkQk

anwqxP

Viterbi Algorithmus [1967]

})({max kqkQk

aiw

})({max kqkQk

aiw


1 0 1 0 1 1 0 1

normal 0

gezinkt 0

begin 1

end 0

0.45

0.075

0.2025

.016875

.091125

Die Berechnungen im Viterbi-Algorithmus werden in der Regel mit einer „logarithmischen Skala“durchgeführt:

))(log()( iwiW qq

)}log()({max))(log()1( 1 kqkQk

iqq aiWxpiW

Die Laufzeit des Viterbi-Algorithmus ist O(n|Q|).

Gene: Die Baupläne der molekularen Bausteine

• Gene kodieren die Baupläne für den Aufbau der molekularen Bausteine (Proteine, RNA).

Transkriptionsfaktoren



mRNA-Reifung plus Splicing

UACGCACGUUACGUGCGUACUBei der mRNA-Reifung undSplicing werden die Introns aus der mRNA herausgeschnitten.

UACGCACGUUAGT..........AGCGUGCGUACU

mRNA-MolekülTranskription

Bei der Transkription wird eine mRNA-Kopie (messenger RNA)des Gens erstellt.

Translation in Protein

Bei der Translation wird die in der mRNA gespeicherte Infor-mation übersetzt und der ent-sprechende Baustein (Protein)synthetisiert.

Tyr Ala Arg Tyr Val Arg Thr

Gen-Annotation

Wie kann man die Gene im Genom finden?

Man sucht statistisch nach charakteristischen Signalen (magischen Wörtern), die häufig inder Nähe eines Gens oder in einem Gen auftauchen und sonst selten.



Man sucht zum Beispiel nach „Open Reading Frames“ (ORFs). Ein ORF startet mit einem Start-Kodon (ATG), endet mit einem von drei Stopp-Kodons (z.B. TGA) und es gibt kein Stopp-Kodon dazwischen.

Die Durchschnittsdifferenz in zufälliger DNA zwischen Stopp-Kodons ist: 64/3 = 21.

Ein langes ORFs kann ein Indiz für ein potentielles Gen sein.

In kodierenden und nicht-kodierenden Bereichen trifft man auf unterschiedliche Kodon-Häufigkeiten (Häufigkeiten der Kodons in einem Fenster einer bestimmten Größe).

Am Anfang und am Ende von Introns treten gewisse Signale (magische) Worte auf.

Gen-Annotation

Wie kann man die Gene im Genom finden?



Ähnlichkeitssuche:

Gegeben ein noch nicht auf Gene untersuchtes DNA-Molekül. Man suche mit Hilfe vonAlignment-Algorithmen nach Sequenzen im DNA-Molekül, die zu bekannten Genen ähnlich sind.



UACGCACGUUACGUGCGUACU


Translation in Protein

Tyr Ala Arg Tyr Val Arg ThrDie Ähnlichkeitssuche (Alignment) kannjedoch auch von einem Genprodukt aus-gehen.

Ein solcher Ansatz wurde von Gelfandet al. 1996 veröffentlicht.

Die Methode wird als Spliced-Alignment-Verfahren bezeichnet.

Spliced-Alignment-Verfahren

Sei ferner E = { B1, B2, ... ,Bp } eine Menge von Teilstrings von G. Die Menge E erhält man, in dem man alle potentiellen Exons von G berechnet.





UACGCACGUUACGUGCGUACU


Sei G = g1g2 ... gn ein String (das neue DNA-Molekül). Seien ferner B = gi gi+1 ... gj und B‘ = gi‘gi‘+1 ... gi‘ Teilstrings von G. Wir schreiben B B‘ , falls j < i‘ ist.

Eine Folge = (B1 , B2 , . . . , Bs) von Teilstrings von G wird dann als Kette bezeichnet, wenn gilt:

B1 B2 ... Bs

Mit * = B1 * B2 * ... * Bs bezeichnen wir die Konkatenation der Bis.

Sei T = t1t2 ... tm eine Sequenz, die sogenannte Target-Sequenz (in unserem Beispiel die mRNA).


Spliced-Alignment-Problem:

Gegeben G, T und E = { B1, B2, ... Bp }, bestimme aus allen möglichen Ketten von E eine Kette von Strings in E mit optimalem Alignment, d.h., der Score D(*, T) von dem Alignment zwischender Konkatenation * der Strings von und dem String T ist optimal (maximal).

ATCAGTGCAATGCAGCCATGAKomplement dermRNA T = t1t2 ... tm

ATCAGTGCAATGT..........AGGCAGCCATGA

Exon Intron ExonG

E = { B1, B2, ... Bp }




Wir benötigen die folgenden Bezeichnungen:

• first(B) = f

• last(B) = l

• size(B) = l – f+1

• E(i) = {Bk E| last(Bk) < i }

• B(i) = gf ... gi

Sei B = gf ...gi ... gl ein Block aus E.

Sei = (B1 , ... , Bk , ... , Bt) eine Kette, so dass Bk die Position i (gi) enthält.

• *(i) = B1 * B2 * ... * Bk-1 * Bk(i)

Sei ))(),((max),,( * jTiDkjiD

enthaltendieBalleKetten k




Um das Spliced-Alignment-Problem zu lösen, muß man das folgende Maximum bestimmen:

(maxDk

),, km)( kBlast

Die folgende Rekursion ermöglicht die Berechnung dieses Maximums:

),,( kjiD

i first(Bk)),(),1,1( ji tgdkjiD i first(Bk)),(),,1( igdkjiD

),(),1,( jtdkjiD i = first(Bk)

i = first(Bk)

),(),1),((max)(

jiliBB

tgdljBlastDl

),(),),((max)(

il

iBBgdljBlastD

l

Documents

Die Suche nach Signalen und Genen in DNA Zentrum für Bioinformatik der Universität des Saarlandes WS 2001/2002