Post on 07-Feb-2018
transcript
Scoring-Matrizen 1
Entwicklung von
Scoring-Schemata
Scoring-Matrizen 2
Sequenzalignment
Was sind die Eingabeparameter?
Querysequenz A
Sequenz B (aus Datenbank)
und das Scoring-Schema
dieses besteht aus
affinen Kostenfunktion (Lücken) Scoring-Matrix
Scoring-Matrizen 3
Auswahl einer Scoring-Matrix
die kritische Entscheidung
da keine Matrix für alle Anwendungen optimal
Wie und wozu werden Alignments verwendet?
Rekonstruktion evolutionärer Vorgänge
Identifikation von Protein-Domänen
Scoring-Matrizen 4
Theorie von Scoring-Matrizen
Statistik globaler Alignments unbekannt
Für lokale Aligments existiert ausgearbeitete Theorie
Diese wird im Folgenden ausgeführt.
Scoring-Matrizen 5
Substitutionsmatrix
Eine Substitutionsmatrix besteht aus einer Menge von Scores sai aj die den Ersatz der Aminosäure ai durch aj in einer Sequenz gewichten.
Scoring-Matrizen 6
Beispiel: BLOSUM 62
BLOSUM 62
Ala 4 Arg -1 5 Asn -2 0 6 Asp -2 -2 1 6 Cys 0 -3 -3 -3 9 Gln -1 1 0 0 -3 5 Glu -1 0 0 2 -4 2 5 Gly 0 -2 0 -1 -3 -2 -2 6 His -2 0 1 -1 -3 0 0 -2 8 Ile -1 -3 -3 -3 -1 -3 -3 -4 -3 4 Leu -1 -2 -3 -4 -1 -2 -3 -4 -3 2 4 Lys -1 2 0 -1 -3 1 1 -2 -1 -3 -2 5Met -1 -1 -2 -3 -1 0 -2 -3 -2 1 2 -1 5 Phe -2 -3 -3 -3 -2 -3 -3 -3 -1 0 0 -3 0 6 Pro -1 -2 -2 -1 -3 -1 -1 -2 -2 -3 -3 -1 -2 -4 7 Ser 1 -1 1 0 -1 0 0 0 -1 -2 -2 0 -1 -2 -1 4 Thr 0 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 1 5 Trp -3 -3 -4 -4 -2 -2 -3 -2 -2 -3 -2 -3 -1 1 -4 -3 -2 11 Tyr -2 -2 -2 -3 -2 -1 -2 -3 2 -1 -1 -2 -1 3 -3 -2 -2 2 7 Val 0 -3 -3 -3 -1 -2 -2 -3 -3 3 1 -2 1 -1 -2 -2 0 -3 -1 4
Ala Arg Asn Asp Cys Gln Glu Gly His Ile Leu Lys Met Phe Pro Ser Thr Trp Tyr Val
log odds ratios
CGTGYTRASGACDACCGWGWAIVSRACAIV CRTLYLRVRGGCGLN CNWGRTIVSRLCALI CITAYTRAIGNCDNG
i j
i ia a
i i
q(a , b )s logp(a )p(b )
=
Scoring-Matrizen 7
Exkurs
Statistische Grundlagen
Scoring-Matrizen 8
Grundlagen für Scoring-Matrizen
Vergleich zwei Hypothesen (Modelle) unter Verwendung einer Likelihood-Funktion
Nullhypothese H0, Z
Die Sequenzen sind nicht miteinander verwandt.
∏ ∏= =
=n
1i
n
1iii )p(b)p(aZ)P(A,B|
Scoring-Matrizen 9
Grundlagen
Alternativhypothese, H1, V
Sequenzen sind verwandt:
∏=
=n
1iii ), bq(aV)P(A,B|
Woher kommen Verbundwahrscheinlichkeit q(ai, bi) ?
Betrachtung evolutionärer Verwandtschaft
Vorkommen der ai und bi in alignierten Domänen
Scoring-Matrizen 10
Odds-ratio
∏∏ ∏
∏==
= =
=
)p(b)p(a), bq(a
)p(b)p(a
), bq(a
Z)P(A,B|V)P(A,B|
ii
iin
1i
n
1iii
n
iii
1
Logarithmiert ergibt sich additives Scoring-Schema:
i i
i ia b
i i
q(a , b )s logp(a )p(b )
=
Scoring-Matrizen 11
Ergebnis
Durch das Addieren der einzelnen Scores
i i
i ia b
i i
q(a , b )s logp(a )p(b )
=
berechnen wir
log( ) log( )i i
i i
q(a , b ) P(A,B | V)p(a ) p(b ) P(A,B | Z)
=∏
Scoring-Matrizen 12
Falldiskussion
1P(A,B | V) undP(A,B | Z)
>
P(A, B | V) > P(A, B | Z)
log( ) 0P(A,B | V)P(A,B | Z)
>
P(A, B | V) > P(A, B | Z)
1P(A,B | V) undP(A,B | Z)
< log( ) 0P(A,B | V)P(A,B | Z)
<
Scoring-Matrizen 13
log-odds-Scores
Nach Altschul (1991) in allgemeinster Form:
1 logλi i
i ia b
i i
q(a , b )sp(a ) p(b )
=
Jedes Scoring-System kann so dargestellt werden.
Wozu ist λ gut?
Vergleich mit Zufallssequenzen sollte Extremwertverteilung folgen.
Voraussetzung: Erwartungswert negativ
Kann mit λ eingestellt werden.
Scoring-Matrizen 14
Verbundwahrscheinlichkeit
Wie wird q(ai, bj) bestimmt?
Hängt von der
Fragestellung und
dem gewünschten Einsatz der Matrizen ab
Scoring-Matrizen 15
Einschub
Ausflug in die Testheorie
Scoring-Matrizen 16
Entwicklung von Scoring-Schemata
1 2( | ) ( | ) ( | ) ..... ( | )nP gene H p cdn H p cdn H p cdn H=
Für Gen gene = cdn1cdn2.....cdnn :
Unabhängigkeit
Schätzung
1 2( ) ( ) ..... ( )H H H nf cdn f cdn f cdn≈
Neyman-Pearson-LemmaFür den Test einer einfachen Hypothese H gegen eine zweite Ahat
maximale Macht.
c)H|X(P)A|X(P>
Scoring-Matrizen 17
Werte aus ScoringTabelle
Übergang zu Logarithmen:
1 2
1 2
( ) ( ) ..... ( )( | )( | ) ( ) ( ) ..... ( )
A A A n
H H H n
f cdn f cdn f cdnP gene AP gene H f cdn f cdn f cdn
=
1 2
1 2
( ) ( ) ... ( ) ( | )log log
( | ) ( ) ( ) ... ( ) A A A n
H H H n
f cdn f cdn f cdnP gene AP gene H f cdn f cdn f cdn
⎛ ⎞⎛ ⎞= ⎜ ⎟⎜ ⎟
⎝ ⎠ ⎝ ⎠
1
( ) ( | )log log
( | ) ( )
nA i
i H i
f cdnP gene AP gene H f cdn=
⎛ ⎞⎛ ⎞= ⎜ ⎟⎜ ⎟
⎝ ⎠ ⎝ ⎠∑
Neyman-Pearson-Testlog-likelihood-ratio (log odds scores)
1
1
( ) ( ) log ... log
( ) ( ) A A n
H H n
f cdn f cdnf cdn f cdn
⎛ ⎞ ⎛ ⎞= + +⎜ ⎟ ⎜ ⎟
⎝ ⎠ ⎝ ⎠
Scoring-Matrizen 18
Schwelle c
Neyman-Pearson-LemmaFür den Test einer einfachen Hypothese H gegen eine zweite Ahat
maximale Macht.
c)H|X(P)A|X(P>
Scoring-Matrizen 19
Wahl der Schwelle c
Fehler 2. Art Fehler 1. Art
Scoring-Matrizen 20
Datenquellen
Identifikation von Domänen
MSAs von Proteinsequenzen
Bewertung evolutionärer Distanzen
DNA- oder Proteinsequenzen evolutionärverwandter Genome/Proteine
Scoring-Matrizen 21
Promotor-Score
Sei p(ai, k) die Wahrscheinlichkeit, mit der das Symbol ai an Position k in den Strings und sei p(ai) die Wahrscheinlichkeit, mit der ai insgesamt in M vorkommt.Dann unterscheiden Scores der Art sai,k := log ( p(ai, k) / p(ai) ) optimaldie Elemente aus M von zufällig zusammengesetzten Zeichenketten.
s(ATGCTGCTTG)=
s(A,1)+
s(T,2)+
....
s(G,10)
Falls s > c:
String ist Promotor
Scoring-Matrizen 22
Beispiel: Promotor-Scores
Annahme:MSA M von Promotor-Sequenzen gegeben
CTGACTCTGGATAACTGTCGCCAAGTGAGAGTGGATCTGGCGCTTTCTCACTCGGTCTGG
Bestimmung von p(ai)
für alle Symbole
Bestimmung von p(ai, k)
für alle Symbole
Scoring-Matrizen 23
Scores für den PW-Sequenzvergleich
Scoring-Matrizen 24
PAM-Matrizen
PAM (M. Dayhoff, 78) steht für
„Akzeptierte Punktmutationen“ oder
„percent accepted mutations“
ist also eine
Einheit zur Divergenzbestimmung
Bezeichnet auch
Klasse von Substitutionsmatrizen
Scoring-Matrizen 25
Definition PAM-Einheit
Zwei Sequenzen A und B unterscheiden sich um eine PAM-Einheit, wenn B aus A durch eine Serie von akzeptiertenPunktmutationen entstanden ist und pro 100 Residuen im Schnitt eine Punktmutation auftrat.
akzeptiert heißt:
Mutation, die
vererbt wurdeund Funktion des Proteins nicht verändern
oder für Spezies von Vorteil ist.
Scoring-Matrizen 26
Beachte!
Rückmutationen möglich!
2 Sequenzen mit Abstand PAM 100 müssen sich nichtan jeder Stellen unterscheiden.
Selbst bei Abstand PAM 250:
Ist zu erwarten, dass im Mittel 25% der Positionen übereinstimmen.
Scoring-Matrizen 27
PAM-Matrizen
Scoring-Matrizen zur Bewertung evolutionärer Prozesseauf dem Aminosäureniveau.
Jeder Wert sai,aj einer PAM n –Matrix gibt an,
wie häufig der Ersatz von ai durch aj in Proteinen zu erwarten ist, die um n PAM-Einheiten divergieren.
Scoring-Matrizen 28
Ableitung
Ausgangspunkt
Sequenzen, die sich nur um wenige PAM-Einheiten unterscheiden.
Hieraus
Extrapolation von Matrizen mit höheren n-Werten.
Scoring-Matrizen 29
PAM-1→ n
Sei M eine PAM 1 Matrix. Sei M n die n-mal mit sich selbst multiplizierte Matrix M. Sei f(ai) die Häufigkeit, mit der die Aminosäure ai in den betrachteten Sequenzen vorkommt. Dann wird der Eintrag für (i, j) in der Matrix PAM nberechnet als
n ni i j i j
i j j
f(a ) M (a ,a ) M (a ,a )log log
f(a )f(a ) f(a )=
Scoring-Matrizen 30
PAM-n Matrizen
Anschließend
Werte mit 10 multipliziert
und auf Integer gerundet.
Scoring-Matrizen 31
Einsatz PAM 250
Bis zur Einführung der BLOSUM-Matrizen warPAM 250 die wichtigste Matrix.
ProblemIst der PAM-Abstand zweier Sequenzen bekannt?
Häufig nicht!
Pragmatisches Vorgehen
Mehrere Matrizen ausprobieren!
Scoring-Matrizen 32
PAM-250 Matrix
Cys 12 Gly -3 5 Pro -3 -1 6 Ser 0 1 1 1 Ala -2 1 1 1 2 Thr -2 0 0 1 1 3 Asp -5 1 -1 0 0 0 4 Glu -5 0 -1 0 0 0 3 4 Asn -4 0 -1 1 0 0 2 1 2 Gln -5 -1 0 -1 0 -1 2 2 1 4 His -3 -2 0 -1 -1 -1 1 1 2 3 6 Lys -5 -2 -1 0 -1 0 0 0 1 1 0 5 Arg -4 -3 0 0 -2 -1 -1 -1 0 1 2 3 6 Val -2 -1 -1 -1 0 0 -2 -2 -2 -2 -2 -2 -2 4 Met -5 -3 -2 -2 -1 -1 -3 -2 0 -1 -2 0 0 2 6 Ile -2 -3 -2 -1 -1 0 -2 -2 -2 -2 -2 -2 -2 4 2 5 Leu -6 -4 -3 -3 -2 -2 -4 -3 -3 -2 -2 -3 -3 2 4 2 6 Phe -4 -5 -5 -3 -4 -3 -6 -5 -4 -5 -2 -5 -4 -1 0 1 2 9 Tyr 0 -5 -5 -3 -3 -3 -4 -4 -2 -4 0 -4 -5 -2 -2 -1 -1 7 10 Trp -8 -7 -6 -2 -6 -5 -7 -7 -4 -5 -3 -3 2 -6 -4 -5 -2 0 0 17
Cys Gly Pro Ser Ala Thr Asp Glu Asn Gln His Lys Arg Val Met Ile Leu Phe Tyr Trp
Scoring-Matrizen 33
Grundlage des Protein-Sequenzvergleiches
Scoring-Matrizen 34
BLOSUM-Matrizen
Einsatzgebiet:
Entwickelt für den Vergleich von Proteindomänen.
Wie?
Aus der BLOCKS-Datenbank.
(Henikoff und Henikoff, 1992)
Scoring-Matrizen 35
BLOCKS-Datenbank
GrundlagePROSITE-Datenbank
Sammlung biologisch signifikanter Muster in Form von
regulären Ausdrücken
Beispiel: GATA-Zink-Finger
C-x-[DN]-C-x(4,5)-[ST]-x(2)-W-[HR]-[RK]-x(3)-[GN]-x(3,4)-C-N-[AS]-C
Scoring-Matrizen 36
BLOCKS-DB
Zu jedem Muster ist in der
PROSITE-DB eine Menge von Sequenzen deponiert.
1.) Mit PROTOMAT werden MSAs generiert.Es werden keine Lücken zugelassen.
2.) Hieraus werden nach heuristischem Verfahren BLÖCKE abgeleitet.
Scoring-Matrizen 37
Block zur PROSITE- Gruppe PS00344
AREA_EMENI|P17429 ( 673) CTNCFTQTTPLWRRNPEGQPLCNACGLFLKLHGVVRPL 7AREA_FUSMO|P78688 ( 694) CTNCFTQTTPLWRRNPEGQPLCNACGLFLKLHGVVRPL 7AREA_PENRO|O13508 ( 660) CTNCFTQTTPLWRRNPEGQPLCNACGLVLKLHGVVRPL 11GAF1_SCHPO|Q10280 ( 70) CTNCQTRTTPLWRRSPDGQPLCNACGLFMKINGVVRPL 16GAT1_YEAST|P43574 ( 310) CSNCTTSTTPLWRKDPKGLPLCNACGLFLKLHGVTRPL 17NIT2_NEUCR|P19212 ( 743) CTNCFTQTTPLWRRNPDGQPLCNACGLFLKLHGVVRPL 8NRFA_PENUR|Q92269 ( 665) CTNCFTQTTPLWRRNPEGQPLCNACGLFLKLHGVVRPL 7NUT1_MAGGR|Q01168 ( 663) CTNCATQTTPLWRRNPEGQPLCNACGLFLKLHGVVRPL 8CGPB_FUSSO|Q00858 ( 403) TDCGTLDSPEWRKGPSGPKTLCNACGLRWAKKEKKRNS 49WC2_NEUCR|P78714 ( 469) TDCGTLDSPEWRKGPSGPKTLCNACGLRWAKKEKKKNA 54DA80_YEAST|P26343 ( 31) CQNCFTVKTPLWRRDEHGTVLCNACGLFLKLHGEPRPI 17GZF3_YEAST|P42944 ( 131) CKNCLTSTTPLWRRDEHGAMLCNACGLFLKLHGKPRPI 17ELT1_CAEEL|P28515 ( 217) CVNCGVHNTPLWRRDGSGNYLCNACGLYFKMNHHARPL 17GA1A_XENLA|P23767 ( 178) CVNCGATVTPLWRRDMSGHYLCNACGLYHKMNGQNRPL 9GA1B_XENLA|P23768 ( 180) CVNCGATVTPLWRRDLSGHYLCNACGLYHKMNGQNRPL 9GA5A_XENLA|P43695 ( 183) CVNCGAMSTPLWRRDGTGHYLCNACGLYHKMNGMNRPL 6GA5B_XENLA|P43696 ( 184) CVNCGAMSTPLWRRDGTGHYLCNACGLYHKMNGINRPL 6GA6A_XENLA|Q91678 ( 182) CVNCGSVQTPLWRRDGTGHFLCNACGLYSKMNGLSRPL 9GA6B_XENLA|P70005 ( 182) CVNCGSVQTPLWRRDGTGHYLCNACGLYSKMNGLSRPL 7GAT1_CHICK|P17678 ( 110) CVNCGATATPLWRRDGTGHYLCNACGLYHRLNGQNRPL 11
spaltenweise f(ai ,aj)
Konserviertheit
Scoring-Matrizen 38
Berechnung von Score-Werten
Sei f(ai) die Häufigkeit mit der ai an allen Positionen innerhalb der Blöcke von BLOCKS vorkommt. Sei f(ai, aj) die Häufigkeit für das spaltenweise bestimmte Vorkommen der Paare ai , aj . Dann kann der Score sai aj definiert werden als:
2: logi j
i ja a
i j
f(a ,a )s
f(a ) f(a )=
Scoring-Matrizen 39
Ergebnis
BLOSUM 100-Matrix
Verfeinerung:Eliminiere von jedem Sequenz-Paar, das N% identische Residuen aufweist,eine Sequenz.
Ergebnis:Die Blöcke enthalten nur noch Sequenzen, die im paarweisen Vergleich nur noch zu max. N% identisch sind.
Motivation?Informationsgehalt PSI-BLAST
Scoring-Matrizen 40
BLOSUM N
N = 50 .... 80
ergibt Matrizen
BLOSUM 50 ,,, BLOSUM 80
Was wird am häufigsten eingesetzt?
Allrounder BLOSUM 62
Scoring-Matrizen 41
BLOSUM 62
Ala 4 Arg -1 5 Asn -2 0 6 Asp -2 -2 1 6 Cys 0 -3 -3 -3 9 Gln -1 1 0 0 -3 5 Glu -1 0 0 2 -4 2 5 Gly 0 -2 0 -1 -3 -2 -2 6 His -2 0 1 -1 -3 0 0 -2 8 Ile -1 -3 -3 -3 -1 -3 -3 -4 -3 4 Leu -1 -2 -3 -4 -1 -2 -3 -4 -3 2 4 Lys -1 2 0 -1 -3 1 1 -2 -1 -3 -2 5 Met -1 -1 -2 -3 -1 0 -2 -3 -2 1 2 -1 5 Phe -2 -3 -3 -3 -2 -3 -3 -3 -1 0 0 -3 0 6 Pro -1 -2 -2 -1 -3 -1 -1 -2 -2 -3 -3 -1 -2 -4 7 Ser 1 -1 1 0 -1 0 0 0 -1 -2 -2 0 -1 -2 -1 4 Thr 0 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 1 5 Trp -3 -3 -4 -4 -2 -2 -3 -2 -2 -3 -2 -3 -1 1 -4 -3 -2 11 Tyr -2 -2 -2 -3 -2 -1 -2 -3 2 -1 -1 -2 -1 3 -3 -2 -2 2 7 Val 0 -3 -3 -3 -1 -2 -2 -3 -3 3 1 -2 1 -1 -2 -2 0 -3 -1 4
Ala Arg Asn Asp Cys Gln Glu Gly His Ile Leu Lys Met Phe Pro Ser Thr Trp Tyr Val
Scoring-Matrizen 42
Scoring-Schemata: Anwendung
PAM-Matrizen
entwickelt aus stark homologen Sequenzen
und Extrapolation
Werden nicht mehr für das Studium vonProteindomänen empfohlen.
Hierfür: BLOSUM-Familie
Scoring-Matrizen 43
Scores für DNA-Sequenzen
s(Match) = 5s(Missmatch) = -4
Verweis auf s, s
s = -s : Alignment enthält mehr Matches als MM:
Kompakte Alignments