Masterarbeit/StilVorlagen/Studienarbeit.md

Protein Similarity Measures as Kernels for
Proteochemometrics

Christoph Schw¨orer

1. November 2009

2
2

3
3
4
4
5
5
6
7
7
7
8
9
10
11
12
13

14

22

Inhaltsverzeichnis

1 Einleitung

1.1 Versuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Methodik

Substitution Kernel

2.1 SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Verwendete Kernel
. . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Tanimoto Kernel
2.2.2 Missmatch Kernel
. . . . . . . . . . . . . . . . . . . . . .
2.2.3 Gappy Kernel . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
2.2.4
2.2.5 Alignment Kernel
. . . . . . . . . . . . . . . . . . . . . .
Implementierung der Kernel . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Tanimoto Kernel
. . . . . . . . . . . . . . . . . . . . . .
2.3.2 Missmatch Kernel
2.3.3 Gappy Kernel . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . .
2.3.4
. . . . . . . . . . . . . . . . . . . . . .
2.3.5 Alignment Kernel
2.4 Die Daten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . .
2.5 verwendete Programme

Substitution Kernel

2.3

3 Ergebnisse

4 Diskussion

1

Kapitel 1

Einleitung

1.1 Versuche

2

Kapitel 2

Methodik

2.1 SVM

Eine Support Vektor Machine (SVM) ist ein Verfahren aus dem Bereich der
Mustererkennung zur Klassifikation von Objekten. Diese Objekte werden hier-
bei durch ihre Eigenschaften (features) (zB. L¨ange, Gewicht oder Sequenzfolge)
und ihre Klasse repr¨asentiert. Bei einer Gegebenen Anzahl d an Eigenschaften
k¨onnen diese als d-dimensionaler Vektor dargestellt werden. Der d-dimensionale
Raum der Eigenschaftsvektoren wird Eigenschaftsraum (feature space) χ ge-
nannt.
Das Ziel einer SVM ist es nun anhand gegebener Trainingsvektoren deren Klas-
se bereits bekannt ist unbekannte Objekte korrekt zu klassifizieren. Man hat
Beispielsweise 2 Klassen von l Objekten mit einer Anzahl d an Eigenschaften x
die als Paare (xi, yi), i = 1, . . . , n mit (cid:126)xl ∈ Rdund yi ∈ {−1, 1}n gegeben sind.
Sind die Datenpunkte im Eigenschaftsraum χ linear separierbar durch eine Hy-
perebene so ist das Problem trivial (Siehe Abb 2.1A). Sind die Daten aber nicht
linear separierbar (Siehe Abb 2.1B) so muss folgendes Optimierungsproblem

Abbildung 2.1: Beispiel f¨ur linear separierbare Daten (A) und nicht linear sepa-
rierbare Daten (B)

3

gel¨ost werden (Boser et al. 1992; Cortes, C. and Vapnik, V., 1995):

minw,b,ξ

1

2 wT w + C (cid:80)l

i=1 ξi

mit der Bedingung yi(wT φ(xi) + b‘1 − ξi,

ξi‘0.

(2.1)

C > 0 ist eine positive Konstante die als Strafparameter dient. Die Trainings-
vektoren wi werden zudem auf einen h¨oher dimensionalen Vektorraum durch die
Funktion φ : Rd1 → Rd2 , w → φ(w); d2 > d1 abgebildet um in diesem h¨oher
dimensionalen Raum eine Hyperebene zu finden die ihn linear separiert. Da die
Daten xi im Algorithmus zur L¨osung des oben genannten Problems nur in der
Form eines Skalarproduktes (cid:104)xi, xj(cid:105) im Raum Rd1 eingehen ist es m¨oglich diese
durch ein Skalarprodukt (cid:104)φ(xi), φ(xj)(cid:105) im Raum Rd2 zu berechnen. Hierzu kann
nun eine positiv-semidefinite Kernelfunktion verwendet werden mit:

k(xi, xj) = (cid:104)φ(xi), φ(xj)(cid:105)

(2.2)

Die in dieser Arbeit verwendeten Kernelfunktionen werden im folgenden Ab-
schnitt erl¨autert.

2.2 Verwendete Kernel

2.2.1 Tanimoto Kernel

Der einfachste implementierte Kernel ist der Tanimoto Kernel. Hierbei wird ein
|Σ|k-dimensionaler Vektorraum ¨uber {0,1} verwendet. Jede Koordinate wird
durch ein m¨ogliches k-mer α indexiert. Tritt das k-mer α auf, so wird der Wert
der Koordiante 1 ansonsten bleibt sie 0. Dies f¨uhrt zu folgender feature map:

wobei

ΦT animoto

k

(x) = (φα(x))α∈Σl

φα(x) =

(cid:26) 1,
0,

falls α in x vorkommt
sonst

(2.3)

(2.4)

F¨ur eine Sequenz x beliebiger L¨ange wird diese feature map nun ¨uber die Sum-
mation der einzelnen Vektoren f¨ur alle k-mere in x gebildet:

ΦT animoto

k

(x) =

(cid:88)

ΦT animoto

k

(α) = X

(2.5)

k−mere α in x

Der Tanimoto Koeffizienl T (X, Y ) f¨ur zwei Sequenzen x und y wird nun errech-
net durch den Tanimotokoeffizienten von X und Y

T (X, Y ) =

X · Y
||X||2 + ||Y ||2 − X · Y

(2.6)

Damit ergibt sich abschließend der Tanimoto Kernel

kT animoto
k

(x, y) = T (X, Y ) = T (ΦT animoto

k

(x), ΦT animoto
k

(y))

(2.7)

4

2.2.2 Missmatch Kernel

Zur Erh¨ohung des Realit¨atsgrads und der Ann¨aherung an die nat¨urlichen Gege-
benheiten muss es jedoch m¨oglich sein einen gewissen Grad von Ungenauigkeit
zu erm¨oglichen. Ein Kernel der dies erreicht darf also nicht nur abh¨angig von
genauen Vergleichen sein sondern muss ein Maß an ¨Ahnlichkeit implementie-
ren. Eine einfache M¨oglichkeit dieser Implementation ist es missmatches beim
Vergleich von k-meren zu erlauben. In Leslie et al. (2003b) wird hierzu ein
(k.m)-missmatch Kernel ¨uber eine feature map ΦM issmatch
realisiert. F¨ur ein
missmatch neigh-
gegebenes k-mer α = α1α2α3...αk, αi ∈ Σ wird hierzu ein
”
borhood“Nk,m(α) definiert. Dies ist die Menge aller k-mere die sich an maximal
m Stellen vom k-mer α unterscheiden. Die featur map f¨ur α ist demnach definiert
als:

(l,m)

wobei

ΦM issmatch

(k,m)

(α) = (φβ(alpha))β∈Σk

φβ(x) =

(cid:26) 1,
0,

falls β ∈ N(k,m)(α)
sonst

(2.8)

(2.9)

Wie schon beim Tanimoto Kernel wird auch hier wieder f¨ur eine Sequenz x be-
liebiger L¨ange die map durch Addition der einzelnen feature Vektoren gebildet:

ΦM issmatch

(k,m)

(x) =

(cid:88)

ΦM issmatch

(k,m)

(α)

(2.10)

k−mere α∈x

Im Gegensatz zum Tanimoto Kernel werden aber mehrfach vorkommende k-
mere auch mehrfach gewertet. Jedes k-mer tr¨agt somit zu allen Werten sei-
missmatch neighborhood“ bei. In diesem Fall Stellt die β Koordinate von
nes
”
ΦM issmatch
(x) also die Anzahl derjenigen k-mere in x dar, die maximal an m
(k,m)
Stellen abweichen. Der (k, m)-missmatch Kernel kM issmatch
(x, y) kann also dar-
gestellt werden als das Skalarprodukt der feature Vektoren von x und y:

(k,m)

kM issmatch
(k,m)

(x, y) = (cid:104)ΦM issmatch

(k,m)

(x), ΦM issmatch
(k,m)

(y)(cid:105)

(2.11)

2.2.3 Gappy Kernel

Alternativ zu missmatches m¨ussen in einem biologisch motivierten Kernel auch
L¨ucken erlaubt werden. Diese M¨oglichkeit ist mit dem Gappy Kernel gegeben.
Wie auch die beiden vorhergehenden Kernel wird f¨ur den (g, l)-gappy string
kernel (Leslie and Kuang, 2003) der gleiche |Σ|l-dimensionale Merkmalsraum
gappy“ matches
verwendet. In diesem Fall aber basiert die feature map auf
”
von g-meren zu l-meren (wobei g > l). Hierbei ist G(g,l)(α) die Menge aller
l-mere die als Teilfolgen der L¨ange l (mit g − l L¨ucken) aus einem gegeben g-
mer α = α1α2 . . . αg, αi ∈ Σ durch Konkatenation von Zeichen aus g gewonnen
werden k¨onnen. Wobei f¨ur alle Stringpositionen αi, αj gelten muß: i < j falls
i < j in g. Somit ergibt sich die feature map:

wobei

ΦGappy
(g,l)

(α) = (φβ(α))β∈Σl

φβ(α) =

(cid:26) 1,
0,

falls β ∈ G(g,l)(α)
sonst

(2.12)

(2.13)

5

Hierbei tr¨agt wieder jede Teilfolge zum Wert aller feature Vektoren bei in denen
sie vorkommt. Die feature map wird dann wieder erweitert auf eine beliebig
lange Sequenz x indem ¨uber alle feature Vektoren aller g-mere in x summiert
wird:

ΦGappy
(g,l)

(x) =

(cid:88)

φGappy
(g,l)

(α)

(2.14)

Der (g, l)-gappy kernel kGappy
(g,l)
dukt der feature Vektoren zweier Sequenzen x und y:

(x) wird wiederum erneut definiert als Skalarpro-

g−mere α∈x

kGappy
(g,l)

(x, y) = (cid:104)ΦGappy

(g,l)

(x), ΦGappy

(g,l)

(y)(cid:105)

(2.15)

2.2.4 Substitution Kernel

Eine erweiterte Variante des mismatch Kernels ist der substitution kernel (Les-
lie and Kuang, 2003). Anstelle des mismatch neighborhood wird hier jedoch ein
similarity neighborhood verwendet. Dieses basiert auf einem probabilistischen
Model zum Austausch von Zeichen in den betrachteten Sequenzen. Hierzu wer-
den paarweise Werte S(a, b) verwendet die sich aus gesch¨atzten evolution¨aren
Austauschwahrscheinlichkeiten ableiten (Henikoff and Hennikoff, 1992; Schwartz
and Dayhoff, 1978; Altschul et al., 1990). Um solch eine Matrix S zu generieren
werden einzelne Bl¨ocke von von Sequenzen homologer Proteine verglichen und
ein log odds-Ratio errechnet:

S(i, j) =

(cid:19)

(cid:18) 1
λ

log

(cid:19)

(cid:18) pij
qi ∗ qj

(2.16)

wobei pij die Wahrscheinlichkeit darstellt die Aminos¨auren i und j in einem
Alignment zu finden. qi und qj hingegen bezeichnen die H¨aufigkeiten der Ami-
nos¨auren. λ ist der Normalisierungsfaktor. Man definiert nun also den mutation
neighborhood M(k,σ)(α) eines k-mers α = a1a2 . . . ak folgendermaßen:

M(k,σ)(α) =

(cid:110)

β = b1b2 . . . bk ∈ Σk :

(cid:88)

(cid:111)

S(ak, bk)

(2.17)

Dabei l¨asst sich σ = σ(N ) w¨ahlen, so dass maxα∈Σk |Mk,σ(α)| < N . Dies
erm¨oglicht eine Kontrolle ¨uber die Gr¨oße des mutation neighborhood. Die sub-
stitution feature map definiert sich nun wie folgt:

wobei

ΦSubstitution

(k,σ)

=

(cid:88)

(φβ(α)β∈Σk )

k−mere α∈x

φβ(α) =

(cid:26) 1,
0,

falls β ∈ M(k,σ)(α)
sonst

(2.18)

(2.19)

Der substitution kernel kSubstitution
als:

(k,σ)

ist damit ¨uber das Skalarprodukt definiert

kSubstitution
(k,σ)

= (cid:104)ΦSubstitution
(k,σ)

(x), ΦSubstitution
(k,σ)

(y)(cid:105)

(2.20)

6

2.2.5 Alignment Kernel

Im Gegensatz zu den bisher angef¨uhrten Kerneln stellt der Alignment Kernel
keinen direkten ¨Ahnlichkeitsvergleich zweier Sequenzen dar. Vielmehr wird die-
ser Kernel durch Faltung mehrere local alignments gebildet da ein einzelnes local
alignment keinen g¨ultigen Kernel darstellt.(Vert, Jean-Philippe; Siago, Hiroto;
Akutsu, Tatsuya). Im folgenden wird nun ein g¨ultiger local alignment Kernel
definiert.
Gegeben sei hierzu eine Substitutionsmatrix S und eine gap penalty Funktion
g. Zus¨atzlich werden drei Kernel auf Basis einer Funktion aus S und g definiert.
Der erste Kernel k0 ist hierbei ein konstante Abbildung von auf 1 welche f¨ur
diejenigen Sequenzteile verwendet werden die außerhalb des matchings liegen:

k0(x, y) := 1, ∀(x, y) ∈ χ2

(2.21)

Der zweite Kernel ka wird zur Berechnung der ¨Ahnlichkeit von allinierten Sym-
bolen mit Hilfe von S verwendet:

k(β)
a (x, y) :=

(cid:26) 0,

exp(βS(x, y)),

falls |x| (cid:54)= 1 oder |y| (cid:54)= 1
sonst

(cid:27)

, ∀(x, y) ∈ χ2

(2.22)
mit β ≥ 0 als Parameter. Der dritte Kernel kg dient abschließend zur Darstellung
der gap penalty:

k(β)g(x, y) := exp[β(g(|x|) + g(|y|))]
wobei β ≥ 0 den gleichen Parameter wie in (2.20) bezeichnet und g eine g¨ultige
gap penalty Funktion .
Diese 3 Kernel werden nun durch Faltung zu einem g¨ultigen Kernel kn zusam-
mengef¨ugt:

(2.23)

k(β)
(n) := k0 ∗

a ∗ k(β)
k(β)

g

(cid:16)

(cid:17)(n−1)

∗ k(β)

a ∗ k0

(2.24)

Dieser Kernel definiert nun die ¨ahnlichkeit von zwei Strings x und y mit einem
local alignment der L¨ange n. Hierbei werden durch den Kernel alle m¨oglichen
a ∗ (k(β)
Dekompositionen von x und y erfasst. Dabei ist k0 der initiale Teil, (k(β)
)
Die Verteilung aller local alignments von genau n Symbolen die durch (n − 1)
gaps getrennt werden und das abschließende k0 der finale Teil.
Um nun bei einem Vergleich zweier Strings alle m¨oglichen lokalen alignments
zu ber¨ucksichtigen ist es Notwendig ¨uber alle n zu summieren so dass sich der
endg¨ultige local alignment kernel k(β)

g

LA ergibt:

k(β)
LA :=

∞
(cid:88)

i=0

k(i)

(2.25)

2.3

Implementierung der Kernel

2.3.1 Tanimoto Kernel

Um eine effiziente Berechnung zu gew¨ahrleisten wird eine Trie-Datenstruktur
verwendet. Hierbei wird jeweils ein Trie f¨ur jede der Sequenzen x und y gebil-
det. Die Tiefe des Tries entspricht dem Parameter k der verwendeten k-mere.
Jeder innere Knoten des Tries hat maximal |Σ| (im Fall von Aminos¨auren also

7

Abbildung 2.2: Beispiel f¨ur 2 Tries und deren Tanimoto Koeffizienzen

20) ¨Aste. der Pfad von der Wurzel des Baumes zu einem Blatt entspricht ei-
nem in der zugeh¨origen Sequenz auftretenden k-mer. An jedem inneren Knoten
wird beim Aufbau des Tries ¨uberpr¨uft ob ein k-mer mit der entsprechenden Zei-
chenfolge erweitert um ein Symbol aus Σ in der Sequenz existiert.Falls ja wird
der Trie um dieses Symbol erweitert. Die Bl¨attern des Tries, also jeweils ein
m¨ogliches k-mer, entsprechen hierbei also den Koordinaten der Vektoren des
Tanimoto Koeffizienten. Nach dem Aufbau der Tries wird der Tanimoto Ko-
effizient T (X, Y ) (Siehe Formel 2.4) der beiden Sequenzen anhand ihrer Tries
errechnet. Mehrfach auftretende k-mere werden bei diesem Trie und so auch im
Tanimoto Koeffizien auf eins reduziert.

2.3.2 Missmatch Kernel

Auch der mismatch Kernel nutzt zur Berrechnung eine Trie Struktur ¨ahnlich
der des Tanimoto Kernels. Im Gegensatz zu dem beim Tanimoto Koeffizienten
verwendeten Trie sollen aber bei dem hier verwendeten Trie auch alle mehrfach
vorkommenden k-mere gewertet werden. Hierzu wird jedem Knoten (auch den
Bl¨attern) eine Liste mit Pointern aller n-mere (wobei n die Tiefe des aktuel-
len Knotens ist) zugewiesen, die dem Pfad des Knotens von der Wurzel aus
entsprechen oder maximal m missmatches aufweisen. Es wird dazu bei jedem
erweitern des Tries um ein Symbol am aktuellen Knoten f¨ur jedes n-mer der

8

Abbildung 2.3: Teil des (6,1)-missmatch trees f¨ur die Sequenz ATGACATT. Es
werden l-mere der L¨ange 6 mit mit max. 1 missmatch berechnet. Der hier darge-
stellte Pfad zeigt den Teilbaum aller mit l-mer features mit Pr¨afix AL. In jedem
Knoten werden zu allen g¨ultigen Pr¨afixen die Anzahl an missmatches zwischen
dem Pr¨afix einer l-mer Instanz und dem Pr¨afix eines features gespeichert sowie
ein Pointer zum Startpunkt des jeweiligen Pr¨afixes.

Liste des Vorg¨angerknotens geschaut ob das (n+1)-mer noch innerhalb der m
missmatches liegt. Ist dies der Fall wird es in die Liste ¨ubernommen; ist dies
nicht der Fall wird es nicht ¨ubernommen. Die Liste der (n+1)-mere ist allso
in jedem Fall eine valide Teilmenge der Liste des Knotens des vorhergehenden
n-mers. Erreicht man auf diese Weise ein Blatt so ist die Liste der l-mere also
eine g¨ultige Liste aller l-mere die maximal m mismatches zum gesuchten l-mer
α aufweisen.
F¨ur eine Sequenz x sind also alle g¨ultigen l-mere die in N(l,m)(α) liegen also
¨aquivalent zu allen l-meren in den Listen des Bl¨attes des Tries mit dem Pfad α.
Alle l-mere der Liste tragen somit zur α Koortinate des feature vektors Φ(x) bei.
Man kann also nun einfach die Beitr¨age aller auftretenden Instanzen Summieren
und somit den Wert des Kernels aktualisieren:

k(x, y) := k(x, y) + nα(x) ∗ nα(y)

(2.26)

wobei nα(x) und nα(y) die Anzahl der Instanzen, einschließlich missmatches,
eines l-mers α in x und y sind.

2.3.3 Gappy Kernel

Wie bei den beiden vorhergehenden Kerneln wird auch f¨ur den (g, l)-gappy
Kernel ein Baum mit Tiefe l verwendet bei dem jeder innere Knoten |Σ| ¨Aste
hat. Der Aufbau des Baumes wird durch ein depth first traversal realisiert.
¨Ahnlich dem Missmatch Kernel wird jedem besuchten Knoten eine Liste mit
Pointern zu g-meren zugewiesen die dem aktuellen Pr¨afix, mit maximal g − l
gaps, entsprechen. F¨ur jedes g-mer wird hierbei zus¨atzlich ein Pointer zur letzten
g¨ultigen Position, also dem ersten Symbol nach letzen g¨ultigen Position des
Mutterknotens das der Bezeichnung des Astes entspricht, gespeichert. An der
Wurzel sind diese Pointer also alle 0 da noch keine Symbole in den g-meren
abgearbeitet wurden.
Bei jedem Schritt in den Baum hinein werden jeweils nur diejenigen g-mere

9

Abbildung 2.4: Teil eines (6,3)-gappy trees f¨ur die Sequenz ATGACATT. An
jedem Knoten werden die noch g¨ultigen g-mere gespeichert sowie die erste Stelle
des Auftretens des aktuellen Symbols nach dem letzten g¨ultigen Symbol. Im
gezeigten Bsp wird der Baum f¨ur das l-mer AAT gezeigt.

weitergegeben bei denen die letzte g¨ultige Position innerhalb des g-mers lag.
Wird kein g¨ultiges Symbol, das heißt ein Symbol das der Markierung des Astes
entspricht, zwischen dem letzten g¨ultigen und dem Ende des g-mers gefunden so
wird dieses verworfen. Findet man jedoch ein g¨ultiges Symbol so wird das g-mer
zusammen mit dem neuen Pointer an den Kindknoten weitergegeben. Wird bei
einem Schritt kein g-mer weitergegeben so muß dieser Teilbaum nicht weiter
bearbeitet werden.
Zum update des Kernelwertes f¨ur x und y muß nun nur f¨ur jedes feature k-
mer die Summe der g¨ultigen Pointer am, dem k-mer entsprechenden Blatt, zum
Kernelwert addiert werden.

2.3.4 Substitution Kernel

Die Berechnung des Substitution Kernels ¨ahnelt der des missmatch Kernels.
Auch hier wird ein trie der Tiefe l verwendet. An jedem Knoten der Tiefe d
wird eine Liste mit Pointern zu allen l-meren gespeichert. Zudem wird noch zu
jeder l-mer Instanz α die aktuelle mutation score (cid:80)d
i=1 S(ai, bi) im Verh¨altnis
zum aktuellen Pr¨afix des Pfades b1b2 . . . bd gespeichert. Bei jedem Schritt in den
Baum hinein wird an der Kante mit Beschriftung b der Tiefe d+1 zu jeder l-mer
Instanz α der Wert S(a, b) zur aktuellen mutation score addiert und zusammen
mit der l-mer Instanz α an den Kindknoten weitergegeben. Wie bei den bisheri-
gen Kerneln wird nun der Kernel Wert f¨ur ein l-mer erneuert indem die Summe
aller g¨ultigen Instanzen (also mit mutation score < σ) von l-meren im trie an
den Bl¨attern zum Kernel Wert f¨ur x und y addiert wird.

10

Abbildung 2.5: Beispiel f¨ur einen Substitution Kernel Trie der Tiefe 6 f¨ur das
Pr¨afix ANC. Die Werte f¨ur S(x,y) sind aus der BLOSUM62 (Siehe Tabelle 2.1)
entnommen.

2.3.5 Alignment Kernel

Da eine naive Berechnung des Kernels nach 2.23 zu einer exponentiellen Zu-
nahme der Komplexit¨at in Abh¨angigkeit von |x| und |y| f¨uhrt wurde einen
dynamic programming Ansatz gew¨ahlt. Hierbei handelt sich um eine Abwand-
lung des klassischen Smith-Waterman Algorithmus f¨ur affine gap penalties. Hier-
zu seien (x, y) ∈ χ2 zwei Sequenzen und g eine affine gap penalty Funktion mit

g(n) =

(cid:26) 0

d + e(n − 1)

falls n = 0 , oder
falls n ≥ 1

(2.27)

dann ist der LA Kernel kβ

LA(x, y) f¨ur x und y gleichwertig mit

kβ
LA(x, y) = 1 + X2(|x| , |y|) + Y2(|x| , |y|) + M (|x| , |y|)

(2.28)

wobei M (i, j), X(i, j), Y (i, j), X2(i, j) und Y2(i, j) f¨ur 0 ≤ i ≤ |x|, und 0 ≤ j ≤
|y| rekursiv definiert sind als






M (i, 0) = M (0, j) = 0,
X(i, 0) = X(0, j) = 0,
Y (i, 0) = Y (0, j) = 0,
X2(i, 0) = Y2(0, j) = 0,
Y2(i, 0) = Y2(0, j) = 0,

(2.29)

und





M (i, j) = exp(βS(xi, yj))[1 + X(i − 1, j − 1) + Y (i − 1, j − 1) + M (i − 1, j − 1)],
X(i, j) = exp(βd)M (i − 1, j) + exp(βe)X(i − 1, j),
Y (i, j) = exp(βd)[M (i, j − 1) + X(i, j − 1)] + exp(βe)Y (i, j − 1),
X2(i, j) = M (i − 1, j) + X2(i − 1, j),
Y2(i, j) = M (i, j − 1) + X2(i, j − 1) + Y2(i, j − 1),

(2.30)
β ist hierbei der frei w¨ahlbare Parameter, S ist die in Tabelle 2.1 gezeigte BLO-
SUM62 Matrix, d und e sind die gap open und gap extension penalties. Zur

11

A R N D C Q E G H I L K M F P S T W Y V B Z X *
A 4 -1 -2 -2 0 -1 -1 0 -2 -1 -1 -1 -1 -2 -1 1 0 -3 -2 0 -2 -1 0 -4
R -1 5 0 -2 -3 1 0 -2 0 -3 -2 2 -1 -3 -2 -1 -1 -3 -2 -3 -1 0 -1 -4
N -2 0 6 1 -3 0 0 0 1 -3 -3 0 -2 -3 -2 1 0 -4 -2 -3 3 0 -1 -4
D -2 -2 1 6 -3 0 2 -1 -1 -3 -4 -1 -3 -3 -1 0 -1 -4 -3 -3 4 1 -1 -4
C 0 -3 -3 -3 9 -3 -4 -3 -3 -1 -1 -3 -1 -2 -3 -1 -1 -2 -2 -1 -3 -3 -2 -4
Q -1 1 0 0 -3 5 2 -2 0 -3 -2 1
0 -3 -1 0 -1 -2 -1 -2 0 3 -1 -4
E -1 0 0 2 -4 2 5 -2 0 -3 -3 1 -2 -3 -1 0 -1 -3 -2 -2 1 4 -1 -4
G 0 -2 0 -1 -3 -2 -2 6 -2 -4 -4 -2 -3 -3 -2 0 -2 -2 -3 -3 -1 -2 -1 -4
H -2 0 1 -1 -3 0 0 -2 8 -3 -3 -1 -2 -1 -2 -1 -2 -2 2 -3 0 0 -1 -4
1 0 -3 -2 -1 -3 -1 3 -3 -3 -1 -4
-1 -3 -3 -3 -1 -3 -3 -4 -3 4 2 -3
I
L -1 -2 -3 -4 -1 -2 -3 -4 -3 2 4 -2
2 0 -3 -2 -1 -2 -1 1 -4 -3 -1 -4
K -1 2 0 -1 -3 1 1 -2 -1 -3 -2 5 -1 -3 -1 0 -1 -3 -2 -2 0 1 -1 -4
5 0 -2 -1 -1 -1 -1 1 -3 -1 -1 -4
M -1 -1 -2 -3 -1 0 -2 -3 -2 1 2 -1
F -2 -3 -3 -3 -2 -3 -3 -3 -1 0 0 -3
1 3 -1 -3 -3 -1 -4
0 6 -4 -2 -2
P -1 -2 -2 -1 -3 -1 -1 -2 -2 -3 -3 -1 -2 -4 7 -1 -1 -4 -3 -2 -2 -1 -2 -4
1 -1 1 0 -1 0 0 0 -1 -2 -2 0 -1 -2 -1 4 1 -3 -2 -2 0 0 0 -4
S
T 0 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 1 5 -2 -2 0 -1 -1 0 -4
W -3 -3 -4 -4 -2 -2 -3 -2 -2 -3 -2 -3 -1 1 -4 -3 -2 11 2 -3 -4 -3 -2 -4
Y -2 -2 -2 -3 -2 -1 -2 -3 2 -1 -1 -2 -1 3 -3 -2 -2
2 7 -1 -3 -2 -1 -4
V 0 -3 -3 -3 -1 -2 -2 -3 -3 3 1 -2
1 -1 -2 -2 0 -3 -1 4 -3 -2 -1 -4
B -2 -1 3 4 -3 0 1 -1 0 -3 -4 0 -3 -3 -2 0 -1 -4 -3 -3 4 1 -1 -4
Z -1 0 0 1 -3 3 4 -2 0 -3 -3 1 -1 -3 -1 0 -1 -3 -2 -2 1 4 -1 -4
X 0 -1 -1 -1 -2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2 0 0 -2 -1 -1 -1 -1 -1 -4
-4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 -4 1

Tabelle 2.1: Die BLOSUM62. Die Angegebenen Werte geben die log odds Ratio
der Aminos¨auren der Zeilen und Spalten an

Normierung der Ergebnisse und um das sogenannte diagonal dominance Pro-
blem zu vermeiden wird jeder Kernel wert kβ
LA(x, y) durch folgende Formel
aktualisiert

ln kβ

LA(x, y)

(2.31)

˜kβ
LA(x, y) =

2.4 Die Daten

1
β

Der in dieser Arbeit verwendete Datensatz bezieht sich auf den in (Rausch, C.;
Weber, T.; Kohlbacher, O; Wohlleben, W. und Huson, D.; 2005) verwendeten
Datensatz an NRPS Proteinen. NRPS steht f¨ur nonribosomalproteinsynthetase
und Bezeichnet eine Familie von Proteinen in Bakterien und Pilzen die durch
einzelnes Anf¨ugen von Aminos¨auren an eine Kette ein Protein erzeugen. In den
meisten F¨allen sind dies Peptidantibiotika die spezielle nicht kanonische Ami-
nos¨auren verwenden. Die NRPS Proteine sind nach der Art ihres spezifischen
Substrates in 8 Klassen aufgeteilt:

• aliphatische Kettenenden mit Wasserstoffbr¨ucken Donor

• apolare, aliphatische Seitenketten

12

• aromatische Seitenketten

• lange positiv geladene Seitenketten

• aliphate oder phenyle mit OH Gruppen

• polare ungeladene (Cys)

• zyklische Aliphate

• hydroxy benzoe S¨auren und derivate

Der vollst¨andige Datensatz enth¨alt 339 Sequenzen.

2.5 verwendete Programme

Zu Analyse der berechneten Kerneldaten aus den vorgestellten Kerneln wurde
das Programm LibSVM (frei erh¨altlich unter: http://www.csie.ntu.edu.tw/ cj-
lin/libsvm/) verwendet. Insbesondere der Programmteil svm-train der es erm¨oglich
sowohl vorberechnete Kernel zu verwenden als auch eine direkte n-fache Kreuz-
validierung erm¨oglich. Hierzu m¨ussen die Parameter −t 4 und −v [n] verwendet
werden. Bei der Auswertung der Kernel wurde im weiteren Verlauf der Parame-
ter n immer mit 5 gew¨ahlt. Als Ausgabe erfolgt das Ergebnis der Kreuzvalidie-
rung in % sowie eine Datei die das Model der SVM zur weiteren Verwendung
innerhalb des Programms enth¨alt.

13

Kapitel 3

Ergebnisse

14

Abbildung 3.1: blabla

15

Abbildung 3.2: blabla

16

Abbildung 3.3: blabla

17

Abbildung 3.4: blabla

18

Abbildung 3.5: blabla

19

Abbildung 3.6: blabla

20

Abbildung 3.7: blabla

21

Kapitel 4

Diskussion

22