Post on 14-Jan-2016
description
transcript
Martina Fröhlich - Aktuelle Themen der Bioinformatik 1
Predicting RNA Secondary Structures
with Arbitrary Pseudoknots by Maximizing the Number of Stacking
Pairs
Martina Fröhlich - Aktuelle Themen der Bioinformatik 2
Predicting RNA Secondary Structures
• Einleitung
• Ein approximativer Algorithmus für planare Sekundärstrukturen
• Ein approximativer Algorithmus für allgemeine Sekundärstrukturen
• NP-Vollständigkeit
Martina Fröhlich - Aktuelle Themen der Bioinformatik 3
RNA
• Lineare Polymere, aufgebaut aus Nukleotiden
• Jeder Nukleotid aufgebaut aus Ribose, Phosphatrest und einer der 4 Basen Adenin, Guanin, Cytosin, Uracil
• Im Gegensatz zur DNA einzelsträngig• bildet über Watson-Crick-Paarungen
dreidimensionale Struktur aus
Martina Fröhlich - Aktuelle Themen der Bioinformatik 4
Sekundärstruktur
Sei S=s1s2…sn eine RNA-Sequenz aus n Basen.
Eine Sekundärstruktur P ist eine Menge von Watson-Crick-Basenpaaren (si1,sj1),…,(sip,sjp), so dass gilt sir+2 ≤ sjr für alle r = 1,...,p, wobei keine Base gleichzeitig zu zwei Paaren gehören kann.
jiS
Martina Fröhlich - Aktuelle Themen der Bioinformatik 5
Häufigste RNA-Strukturen
• Hairpin Loop
• Internal Loop
• Multi-branched Loop
• Bulge
• Stacking Pair
Martina Fröhlich - Aktuelle Themen der Bioinformatik 6
Stacking Pair• Von zwei aufeinanderfolgenden Basenpaaren
(si,sj) und (si+1,sj-1) gebildete Schleife mit i+4≤j• Enthalten keine ungepaarten Basen, haben
negative Freie Energie und stabilisieren die Sekundärstruktur
• q aufeinanderfolgende Stacking Pairs
(si,sj), (si+1,sj-1); (si+1,sj-1), (si+2,sj-2)…
(si+q-1, sj-q+1),(si+q,sj-q ) von P werden durch (si,si+1,…, si+q; sj-q ,…, sj-1,sj) dargestellt.
Martina Fröhlich - Aktuelle Themen der Bioinformatik 7
Die Herausforderung: Pseudoknots
• Sei S eine RNA-Sequenz. Ein Pseudoknot wird gebildet aus zwei überlappenden Basenpaaren (si,sj) und (sk, sl) der Form i<k<j<l
• Pseudoknots machen die Bestimmung einer optimalen Sekundärstruktur NP-hart
Martina Fröhlich - Aktuelle Themen der Bioinformatik 8
Definitionen• Der ungerichtete Graph G(P) einer gegebener
Sekundärstruktur P sei derart aufgebaut, dass die Basen von S die Knoten in G(P) darstellen. (si,sj) ist eine Kante in G(P), wenn j = i+1 oder (si,sj) ein Basenpaar in P ist.
• Eine Sekundärstruktur P ist planar, wenn G(P) planar ist• Eine Sekundärstruktur P enthält einen
„interleaving block“, wenn sie drei Stacking Pairs der Form (si,si+1;sj-1,sj), (si`, si+1;sj´-1,sj´), (si´´,si´´+1;sj´´-1,sj´´) enthält, bei denen i<i´<i´´<j<j´<j´´ ist.
Martina Fröhlich - Aktuelle Themen der Bioinformatik 9
Nonplanare Sekundärstruktur
• Wenn eine Sekundärstruktur P einen „Interleaving Block“ enthält, ist sie nonplanar
Martina Fröhlich - Aktuelle Themen der Bioinformatik 10
Beweis• Angenommen P enthält einen „interleaving block“ der
o.B.d.A. von folgenden Stacking pairs gebildet wird (s1,s2;s7,s8), (s3,s4;s9,s10) und (s5,s6;s11,s12)
• Der Subgraph dieser Stacking Pairs kann nicht planar abgebildet werden
• G(P) ist nicht planar P ist nicht planar
Martina Fröhlich - Aktuelle Themen der Bioinformatik 11
Predicting RNA Secondary Structures
• Einleitung
• Ein approximativer Algorithmus für planare Sekundärstrukturen
• Ein approximativer Algorithmus für allgemeine Sekundärstrukturen
• NP-Vollständigkeit
Martina Fröhlich - Aktuelle Themen der Bioinformatik 12
Definitionen
• Die Stacking Pairs einer Sekundärstruktur P können in ein Rasterfeld eingebettet werden
• Die Basen der dazugehörigen RNA-Sequenz werden nacheinander durch Gitterpunkte auf einer horizontalen Linie L des Feldes dargestellt
• Ein Stacking Pair (si,si+1;sj-1,sj) wird in der Art dargestellt, dass die Punkte si bzw. si+1 mit sj bzw. sj-1 derart verbunden sind, dass sich beide Linien entweder unter oder oberhalb von L befinden
Martina Fröhlich - Aktuelle Themen der Bioinformatik 13
Stacking Pair - Einbettung
Martina Fröhlich - Aktuelle Themen der Bioinformatik 14
Lemma
• Die Einbettung E von Stacking Pairs einer planaren Sekundärstruktur P ist planar
• P planar => E planar
wird bewiesen durch
⌐ E planar => ⌐ P planar
Martina Fröhlich - Aktuelle Themen der Bioinformatik 15
Beweis• P hat keine planare Stacking-Pair-Einbettung => P enthält
einen „interleaving block“
• P enthält einen „interleaving block“ => P ist nonplanar
Martina Fröhlich - Aktuelle Themen der Bioinformatik 16
Algorithmus MaxSP• V(i,j) (j ≥ i) sei die maximale Anzahl an Stacking
Pairs, die von si...sj ohne Pseudoknots gebildet werden kann, wenn si und sj ein Watson-Crick-Paar bilden
• W(i,j) (j ≥i) sei die maximale Anzahl an Stacking Pairs, die von si...sj ohne Pseudoknots gebildet werden kann.
• => W(1,n) ist die maximale Anzahl an Stacking Pairs die von S ohne Pseudoknots gebildet werden kann.
Martina Fröhlich - Aktuelle Themen der Bioinformatik 17
Algorithmus MaxSP• Basis
For j=i,i+1,i+2 oder i+3 (j ≤ n)
V(i,j)=0 si,sj sind Basenpaare
W(i,j)=0.
• Weiterführung
For j>i+3
),1(),(max
e, Basenpaarsind und :),(max),(
1-jki jkWkiW
jijiVjiW
Basenpaare sind und :)1,1(
,Basenpaare sind 1-j und 1:1)1,1(max),(
jijiW
ijiVjiV
Martina Fröhlich - Aktuelle Themen der Bioinformatik 18
MaxSP ist 1/2-approximativ
• Gegebene RNA-Sequenz S• N* die maximale Anzahl an Stacking Pairs
in einer planaren Sekundärstruktur, die von S geformt werden kann
• W die maximale Anzahl an Stacking Pairs in einer planaren Sekundärstruktur ohne Pseudoknots, die von S geformt werden kann
Martina Fröhlich - Aktuelle Themen der Bioinformatik 19
Beweis• P* sei die planare Sekundärstruktur von S mit N* Stacking Pairs
• P* ist planar => jede Stacking Pair-Einbettung von P* ist planar
• Sei E eine Stacking Pair-Einbettung von P*, in der sich keine Linien überkreuzen
• Seien n1 und n2 die Anzahl der Stacking Pairs ober- bzw. unterhalb von L
• O.B.d.A n1 ≥ n2
• Sekundärstruktur P sei P*, jedoch ohne die Stacking Pairs unterhalb von L
• Da n1 ≥ n2, n1 ≥ N*/2, W ≥ n1 => W ≥ N*/2
Martina Fröhlich - Aktuelle Themen der Bioinformatik 20
Komplexität und Speicherplatz
• Algorithmus MaxSP berechnet die maximale Anzahl an Stacking Pairs einer Sekundärstruktur S ohne Pseudoknots in Zeit O(n3) und mit Speicherplatz O(n²).
Martina Fröhlich - Aktuelle Themen der Bioinformatik 21
Beweis
• Es werden jeweils O(n²) Einträge V(i,j) und W(i,j) gefüllt.
• Das Füllen der W`s benötigt konstante Zeit, das der V`s höchstens O(n).
• => O(n²) Einträge in O(n3) Zeit
Martina Fröhlich - Aktuelle Themen der Bioinformatik 22
Predicting RNA Secondary Structures
• Einleitung
• Ein approximativer Algorithmus für planare Sekundärstrukturen
• Ein approximativer Algorithmus für allgemeine Sekundärstrukturen
• NP-Vollständigkeit
Martina Fröhlich - Aktuelle Themen der Bioinformatik 23
Algorithmus GreedySP()• Sei S=s1s2...sn die Eingabesequenz und E die Menge der Basenpaare,
die der Algorithmus ausgibt. Zu Beginn sind alle sj unmarkiert und E= Ø
• GreedySP(S,i) //i ≥ 31. Finde die am weitesten links liegenden aufeinanderfolgenden i Stacking Pairs SP, die von unmarkierten Basen gebildet werden. Nimm SP zu E hinzu und markiere diese Basen. Wiederhole bis Sequenz einmal durchlaufen.
2.For k=i-1 downto 2,Finde die am weitesten links liegenden aufeinanderfolgenden i Stacking Pairs SP, die von unmarkierten Basen gebildet werden. Nimm SP zu E hinzu und markiere diese Basen. Wiederhole bis Sequenz einmal durchlaufen..
3.Finde das am weitesten links liegende Stacking Pair SP, das von unmarkierten Basen gebildet wird. Nimm es zu E hinzu und markiere diese Basen. Wiederhole bis Sequenz einmal durchlaufen.
Martina Fröhlich - Aktuelle Themen der Bioinformatik 24
Beweis zur Approximation
• Zu beweisen:
GreedySP findet 1/3 der maximal möglichen Stacking Pairs
Martina Fröhlich - Aktuelle Themen der Bioinformatik 25
Definitionen• Die von GreedySP ermittelten SP`s werden nacheinender
mit SP1, SP2,...,SPh bezeichnet• Für jedes SPj = (sp,...sp+t;sq-t,...sq) werden die beiden
Intervalle Ij und Jj für die Indices [p...p+1] und [q-t...q] definiert
• Sei F die Menge der Stacking Pairs einer optimalen Sekundärstruktur S mit der maximalen Anzahl an Stacking Pairs.
Für jedes berechnete SPj sei
Xß = {(sk,sk+1;sw-1,sw) F|mindestens einer der Indices k, k+1, w-1, w liegt in ß} für ß = Ij oder Jj.
Martina Fröhlich - Aktuelle Themen der Bioinformatik 26
Definitionen
• Für jedes j sei
und
• Es sei |SPj| die Anzahl der von SPj repräsentierten Stacking Pairs.
• Es seien |Ij| und |Jj| die Anzahlen der Indices im Intervall Ij und Jj
}X {X - X X´ kJkIjkjIjI
jIkJkIjkjJjJ X-}X {X - X X´
Martina Fröhlich - Aktuelle Themen der Bioinformatik 27
2 Teilschritte• Sei N die von GreedySP(S,i) berechnete und N*
die maximal mögliche Anzahl an Stacking Pairs in S.
• Folgend 2 Schritte müssen bewiesen werden:• Wenn |SPj| ≥ 1/r * |(X´Ij X´Jj)| für alle j
=> N ≥ 1/r * N*• Für jedes von GreedySP(S,i) berechnete SPj gilt
|SPj| ≥ 1/3 * |(X´Ij X´Jj)|
Martina Fröhlich - Aktuelle Themen der Bioinformatik 28
1.Schritt
• Lemma 1≤j≤h{ XIj XJj} = F
• Beweis durch Widerspruch
Stacking Pair(sk,sk+1;sw-1,sw) in F, aber in keinem der XIj, XJj
=> keiner der Indices in einem XIj, XJj
=>Widerspruch zu Schritt 3 des Algo`s
Martina Fröhlich - Aktuelle Themen der Bioinformatik 29
1.Schritt
• Aus der Definition der X´Ij und X´Jj folgt
{XIk XJk} = {X´Ik X´Jk}
• Da N = Σj |SPj| folgt
• Wenn |SPj| ≥ 1/r * |(X´Ij X´Jj)| für alle j
• N ≥ 1/r * | {XIk XJk}|
• Und somit N ≥ 1/r * N*
k k
k
Martina Fröhlich - Aktuelle Themen der Bioinformatik 30
2.Schritt
• Zu beweisen war:• Für jedes von GreedySP(S,i) berechnete SPj gilt
|SPj| ≥ 1/3 * |(X´Ij X´Jj)|
• Fallunterscheidung für die 3 Schritte des Algorithmus
Martina Fröhlich - Aktuelle Themen der Bioinformatik 31
Fall 1• SPj generiert von GreedySP(S,i) in Schritt 1• Per Definition |X´Ij|, |X´Jj| ≤ i+2• Behauptung: |X´Ij| ≤ i+1• Beweis durch Widerspruch:
-für eine Zahl t hat F i+2 aufeinanderfolgende Stacking Pairs (sp-1,...,sp+i+1;st-i-1,...,st+1)
-alle Basen vor der Wahl von SPj unmarkiert
-in SPj wären nicht die i linkesten Stacking Pairs Widerspruch
• Somit: |SPj|/|X´Ij X´Jj| ≥ i/((i+1)+(i+2)) ≥ 1/3 (wenn i ≥ 3)
Martina Fröhlich - Aktuelle Themen der Bioinformatik 32
Fall 2• SPj generiert von GreedySP(S,i) in Schritt 2.
• |SPj| =k ≥ 2; SPj = (sp,...,sp+k;sq-k,...,sq)
• Per Definition |X´Ij|, |X´Jj| ≤ i+2
• Behauptung: |X´Ij|, |X´Jj|, ≤ k+1
• Beweis:
Wie in Fall 1 Widerspruch bei sp-1,...,sp+k+1;st-k-1,...,st+1
Kann für X´Ij und X´Jj bewiesen werden..
Somit:
• |SPj|/|X´Ij X´Jj| ≥ k/((k+1)+(k+1)) ≥ 1/3 (wenn k ≥ 2)
Martina Fröhlich - Aktuelle Themen der Bioinformatik 33
Fall 3• SPj generiert von GreedySP(S,i) in Schritt 3.• Sei SPj = (sp,sp+1;sq-1,sq)• Wie in Fall 2 kann bewiesen werden, dass |X´Ij|, |X´Jj| ≤ k+1• Behauptung |X´Ij| ≤1• Beweis: Einziger möglicher Fall mit |X´Ij| =2, wenn
(sp-1,sp;sr-1,sr) und (sp,sp+1;st-1,st) beide zu X´Ij gehören würden.
SPj nicht linkestes Stacking Pair Widerspruch• Somit: |SPj|/|X´Ij X´Jj| ≥ 1/(1+2) ≥ 1/3
Martina Fröhlich - Aktuelle Themen der Bioinformatik 34
Zeit und Komplexität
• Bei gegebener RNA Sequenz S von Länge n und einer Konstante k benötigt GreedySP(S,k) Zeit und Speicherplatz O(n).
Martina Fröhlich - Aktuelle Themen der Bioinformatik 35
Zeit und Komplexität
• Für jedes j mit 1 ≤j ≤k gibt nur 4j verschiedene
Muster aus {A,G,C,U}• Darstellbar durch k verkettete Listen mit je 4j
Indices• O(n) Einträge pro Liste => O(kn)Einträge in allen
Listen• k-maliges Scannen der Sequenz, jeder Eintrag der
Liste wird höchstens einmal besucht => O(kn) Zeit
Martina Fröhlich - Aktuelle Themen der Bioinformatik 36
Fazit
• Algorithmus GreedySP ist 1/3-approximativ
• Berücksichtigt Pseudoknots
• Zeit O(n)
• Platz O(n)
Martina Fröhlich - Aktuelle Themen der Bioinformatik 37
Alternativen• Nussinov et al (1978) – Freie Energie-Funktion, die
minimiert wird, wenn die Sekundärstruktur die maximale Anzahl an komplementären Basenpaaren enthält. Ohne Pseudoknots.
(Zeit O(n3))• Mfold :
– Berechnung über stabile Strukturen(z. B. Helices)
– (Zeit O(n3))– ohne Pseudoknots
Martina Fröhlich - Aktuelle Themen der Bioinformatik 38
Alternativen• Rivas, Eddy (1998) Algorithmus mit dynamischer
Programmierung, handelt bestimmte Pseudoknots in O(n6)Zeit und O(n4) Speicherplatz
• Stochastische kontextfreie Grammatiken• Genetische Algorithmen.
Fitnessfunktion: Selektion nach Länge der Helix oder nach freier
Energie.
Martina Fröhlich - Aktuelle Themen der Bioinformatik 39
Predicting RNA Secondary Structures
• Einleitung
• Ein approximativer Algorithmus für planare Sekundärstrukturen
• Ein approximativer Algorithmus für allgemeine Sekundärstrukturen
• NP-Vollständigkeit
Martina Fröhlich - Aktuelle Themen der Bioinformatik 40
NP-Vollständigkeit• Das Ermitteln einer planaren RNA-Sekundärstruktur mit der
maximalen Anzahl an Stacking Pairs ist NP-Vollständig.• Beweis durch Reduktion des Tripartite Matching Problems
auf unser Problem• Gegeben: 3 Knotenmengen mit Kardinalität n
Kantenmenge E als Teilmenge von X × Y × Z von Grösse m
• Konstruktion einer RNA-Sequenz SE und eines Integers h in polynomieller Zeit.
• E enthält perfektes Matching sp(SE) ≥ h• E enthält kein perfektes Matching sp(SE) < h
Martina Fröhlich - Aktuelle Themen der Bioinformatik 41
Konstruktion der RNA-Sequenz SE
• X ={x1,...,xn}, Y={y1,...,yn}, Z={z1,...,zn}
• E=e1,...,em; ej = xpj, yqj, zrj
• RNA-Sequenz aufgebaut aus A, U, G, C
• Sei d = max {6n, 4(m+1)}+1
• Für k<d sei
δ(k) = UdAkGUdAd-k δ(k) =Ud-kAdGUkAd
π(k)=C2d+2kAGC4d-2k π (k)=G4d-2kAG2d+2k
Martina Fröhlich - Aktuelle Themen der Bioinformatik 42
Kodierung der Knoten
• Für 1≤i≤n ‹xi›= δ(i) ‹yi›= δ(n+i) ‹zi›= δ(2n+i)
• Wobei ‹xi› ist die Kodierung für Knoten xi
• ‹xi› = δ(i) ‹yi› = δ(n+i) ‹zi› = δ(2n+i)
• Knotenmenge X =‹x1›G‹x2›G...G‹xn›
• X = ‹xn›G‹xn-1›G...G‹x1›
• X-xi = ‹x1›G...G‹xi-1›G‹xi+1›G...G‹xn›
• X-xi=‹xn›G...G‹xi+1›G‹xi-1›G...G‹x1›
Martina Fröhlich - Aktuelle Themen der Bioinformatik 43
Kodierung der Kanten• Für jede Kante ej (1≤j≤m) sei
• Vj= π(j) Wj= π(m+1+j)
• Vj= π(j) Wj= π(m+1+j)
• ej=(xpj,yqj,zrj) = Sj =
AG Vj AG Wj AG X G Y G Z G (Z-zrj) G (Y-yqj) G (X-xpj) Vj A Wj
• Zusätzliche Sequenz Sm+1 =
AG Vm+1 AG Wm+1 AG Z G Y G X Vm+1 A Wm+1
• SE = Sm+1 Sm ... S1
• h = mσ + n(6d-4) + 12d-5 mit σ =3n(3d-2) + 6d - 1
Martina Fröhlich - Aktuelle Themen der Bioinformatik 44
Komplexität
• SE besteht aus O((n+m)3) Basen und kann in Zeit O(SE) konstruiert werden
• Zu beweisen:
Genau dann, wenn E ein perfektes Matching enthält, ist sp(SE) ≥ h
Martina Fröhlich - Aktuelle Themen der Bioinformatik 45
Definitionen
• Jedes Sj wird als Region bezeichnet
• Die Substrings U+A+ der δ(i), C+ der π und G+ der π werden als Fragmente bezeichnet
Martina Fröhlich - Aktuelle Themen der Bioinformatik 46
Korrektheit des “Wenn”-Falles
• Wenn E ein perfektes Matching enthält, dann ist sp(SE) ≥ h
Martina Fröhlich - Aktuelle Themen der Bioinformatik 47
Bildung von Stacking Pairs
• δ(i) oder δ(i) d-1
• δ(i) mit δ(i) 3d-2
• π(i) mit π(i) 6d-2
• Für jedes i ≠ j, π(i) mit π(i) 6d-3
Martina Fröhlich - Aktuelle Themen der Bioinformatik 48
Definitionen
• Sei M ={ej1,ej2,...,ejn} ein perfektes Matching
• Definiert jn+1=m+1
Martina Fröhlich - Aktuelle Themen der Bioinformatik 49
Vorgehen
• Durchlaufe Region für Region
• 3 Fälle zu Unterscheiden:
1. Fall: Sj, so dass ej M
2. Fall: Sj, so dass ej M
3. Fall: Sm+1
Martina Fröhlich - Aktuelle Themen der Bioinformatik 50
Fall1
• ej = (xpj, yqj, zrj)
• 6d-2 Stacking Pairs zwischen Vj und Vj und Wj und Wj
• 3d-2 Stacking Pairs zwischen ‹xi› und ‹xi› für i ≠ pj, ‹yi› und ‹yi› für i ≠ qj, ‹zi› und ‹zi› für i ≠ rj,
• ‹xpj›, ‹yqj›, ‹zrj› jeweils d-1 Stacking Pairs
Martina Fröhlich - Aktuelle Themen der Bioinformatik 51
Fall 1
• Stacking Pairs in Sj
2(6d-2) + 3(n-1)(3d-2) + 3(d-1) =
3n(3d-2) + 6d-1 = σ
• Es existieren (m-n) solcher Ecken
Martina Fröhlich - Aktuelle Themen der Bioinformatik 52
Fall 2
• 6d-3 Stacking Pairs zwischen Wjk in Sjk und Wjk+1 in Sjk+1
• 6d-2 Stacking Pairs zwischen Vjk in Sjk und Vjk in Sjk
• 3d-2 Stacking Pairs zwischen ‹xi› in Sjk und ‹xi› in Sjk für alle i ≠ pj1,…, pjk (analog bei ‹yi› und ‹zi›)
• 3d-2 Stacking Pairs zwischen ‹xi› in Sjk und ‹xi› in Sjk+1 für alle i = pj1,…, pjk (analog bei ‹yi› und ‹zi›)
Martina Fröhlich - Aktuelle Themen der Bioinformatik 53
Fall 2
• Stacking Pairs in Sj
6d-3 + 6d-2 + 3n(3d-2) = σ + 6d-4
• Es existieren n solcher Ecken
Martina Fröhlich - Aktuelle Themen der Bioinformatik 54
Fall 3
• 6d-2 Stacking Pairs zwischen Vm+1 und Vm+1
• 6d-3 Stacking Pairs zwischen Wm+1 und Wm+1
• Anzahl solcher Stacking Pairs in Sm+1
12d-5
Martina Fröhlich - Aktuelle Themen der Bioinformatik 55
Resultat
• E enthält perfektes Matching
Stacking Pairs in SE =
(m-n) σ + n(σ + 6d-4) + 12d – 5 = h
sp(SE) ≥ h
Martina Fröhlich - Aktuelle Themen der Bioinformatik 56
Korrektheit des “Nur dann, wenn”-Falles
• Wenn E kein perfektes Matching enthält, dann ist sp(SE)<h
Martina Fröhlich - Aktuelle Themen der Bioinformatik 57
Definitionen
• OPT : Sekundärstruktur von SE mit der maximalen Anzahl an Stacking Pairs
• #OPT = sp(SE)
• Konjugat: Für Substring H = s1,s2,...,sk ist das Konjugat Ĥ = ŝ1, ŝ2,..., ŝk mit
Â=U, Û=A, Ĉ=G, Ĝ=C
• 2-Substring: zwei adjazente Basen
Martina Fröhlich - Aktuelle Themen der Bioinformatik 58
Vorkommen der verschiedenen 2-Substrings
Martina Fröhlich - Aktuelle Themen der Bioinformatik 59
Fakten
• #OPT ≤ min {# AA, # UU} + min {# GG, # CC} + #UA/2 + #GC/2 = h + n +1 + (2m+2)
• Anzahl nichtgepaarter Substrings sei ◊
• #OPT ≤ min {# AA- ◊AA, # UU- ◊UU} +
min {# GG- ◊GG, # CC- ◊CC} +
(#UA- ◊UA)/2 + (#GC- ◊GC)/2
Martina Fröhlich - Aktuelle Themen der Bioinformatik 60
Grundlage des Beweises
• SE enthält kein perfektes Matching
untere Schranke für die ◊-Werte ist so
hoch, daß sp(SE) < h
Martina Fröhlich - Aktuelle Themen der Bioinformatik 61
Definitionen
• Offene Region: UU-,AA-, oder UA-Substrings innerhalb Sj sind mit Regionen außerhalb von Sj
verbunden ist. Sonst: Sj ist geschlossene Region
• Konjugierte Fragmente: F sei Fragment in SE
F´ ist kunjugiertes Fragment von F, wenn F´das Konjugat von F ist
• Begrenzungsfragmente:Vj oder Wj (für 1 ≤ j ≤ m+1)
Martina Fröhlich - Aktuelle Themen der Bioinformatik 62
Weiteres Vorgehen
• Fallunterscheidungen: – Sm+1 ist geschlossene Region
– Sm+1 ist offene Region
• Anzahl offener Regionen < n+1
• Anzahl offener Regionen > n+1
• Anzahl offener Regionen = n+1
Martina Fröhlich - Aktuelle Themen der Bioinformatik 63
Sm+1 ist geschlossene Region
• Sm+1 ist geschlossene Region#OPT < h
• Beweis: Sm+1 hat 3nd mehr AA- als UU-Substrings
◊AA ≥ 3nd #OPT < h + (n+1) + (2m+2) - 3nd < h
Martina Fröhlich - Aktuelle Themen der Bioinformatik 64
Nichtgebundene CC`s und GG`s
• Sei α die Anzahl an Begrenzungsfragmenten , die nicht mit ihren konjugierenden Fragmenten verbunden sind
• ◊CC+ ◊GG ≥ α + (#GC – GC)
Martina Fröhlich - Aktuelle Themen der Bioinformatik 65
◊CC+ ◊GG ≥ α + (#GC – GC)
• GC nur in Begrenzungsfragment F• GC gepaart linkestes CC nicht gepaart• (#GC- ◊GC) Begrenzungsfragmente, deren GC gepaart ist
Linkestes CC nicht gepaart+weiteres CC oder GG nicht gepaart
Anzahl ungepaarter CC und GG ≥ 2(#GC – GC)• α - (#GC- ◊GC) Begrenzungsfragmente, deren GC nicht
gepaart ist entweder ungepaartes CC oder GG Anzahl ungepaarter CC und GG ≥ α-(#GC – GC)
Martina Fröhlich - Aktuelle Themen der Bioinformatik 66
Vj und Wj in offener Region
• Sj ist offene Region
es dürfen nicht beide Fragmente Vj und Wj mit ihren konjugierenden Fragmenten verbunden sein
• Grund: Interleaving Block unpolar
Martina Fröhlich - Aktuelle Themen der Bioinformatik 67
Untere Grenze der ◊ -Werte
• Sei l ≥1 die Anzahl der offenen Regionen in OPT
1)Sm+1 ist offene Region ◊UU ≥ 3(m+1-l)d
2)max {◊CC, ◊GG} ≥ l + (#GC- ◊GC)/2
3)l=n+1, Sm+1 ist offene Region, E hat kein perfektes Matching entweder
a) ◊UU ≥3(m-n)d+1 b) ◊AA ≥1 oder c) ◊ UA≥2
Martina Fröhlich - Aktuelle Themen der Bioinformatik 68
Beweis von 1)
• Sj geschlossen (j ≠ m+1)
3d ungepaarte UU-Substrings• Da m+1-l geschlossene Regionen
3(m+1-l)d ungepaarte UU-Substrings
Sm+1 ist offene Region UU ≥ 3(m+1-l)d
Martina Fröhlich - Aktuelle Themen der Bioinformatik 69
Beweis von 2)
• 2l Fragmente in Vj und Wj in l, die nicht mit ihren konjugierten Fragmenten verbunden sind
◊CC + ◊GG ≥ 2l + (#GC- ◊GC)
max {◊CC, ◊GG} ≥ l + (#GC- ◊GC)/2
Martina Fröhlich - Aktuelle Themen der Bioinformatik 70
Beweis von 3)
• m+1-l = m-n geschlossene Regionen
3(m-n)d ungepaarte UU-Substrings
Martina Fröhlich - Aktuelle Themen der Bioinformatik 71
Beweis von 3)• n+1 offene Regionen bestehen aus Sm+1 und Sj1...Sjn
• In n Ecken kein perfektes Match in den n+1 Regionen von mind. einem xk mehr ‹xk› als ‹xk› mind. 2 Fragmente F in allen ‹xi› nicht gepaart
• Fall1: ungepaarter UU-Substring in F• Fall2: ungepaarter AA-Substring in F• Fall3: alle UU-und AA-Substrings gepaart UA-Substrings
der entsprechenden Fragmente ungepaart
a) ◊UU ≥3(m-n)d+1 b) ◊AA ≥1 oder c) ◊ UA≥2
Martina Fröhlich - Aktuelle Themen der Bioinformatik 72
Wenn E kein perfektes Matching enthält #OPT < h
1)l< n+1 ◊UU ≥ 3(m+1-l)d
#OPT = h + n + 1 + (2m+2) - 3(n+1-l)d
≤ h + n + 1+(2m+2) - 3d < h
2)l> n+1 max{◊CC, ◊GG} ≥ l + (#GC- ◊GC)/2
#OPT ≤ h + n + 1 – l < h, da l ≥ n+1
3)l=n+1 entweder a) ◊UU ≥3(m-n)d+1 b) ◊AA ≥1 oder
c) ◊UA ≥2
#OPT ≤ h + n – max{CC,GG}+(GC-GC)/2 < h, da l ≥ n+1
Martina Fröhlich - Aktuelle Themen der Bioinformatik 73
Ergebnis
• E enthält perfektes Matching sp(SE) ≥ h
• E enthält kein perfektes Matching sp(SE) < h
• Wenn planare RNA-Sekundärstruktur über Stacking Pairs in polynomieller Zeit berechnet werden könnte, könnte man auch das Tripartite Matching Problem in polynomieller Zeit lösen Widerspruch
Martina Fröhlich - Aktuelle Themen der Bioinformatik 74
Quellen- Predicting RNA Secondary Structures with Arbitrary Pseudoknots by
Maximizing the Number of Stacking Pairs, Samuel Ieong, Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung and Siu-Ming Yiu, published in Journal of Computational Biology, vol. 10. Number 6, 2003, pp. 981–995
- RNA Pseudoknot Prediction in Energy Based Models, Rune B. Lyngsø and Christian N. S. Pedersen, published in Journal of Computational Biology, vol. 7(3/4), pp. 409–428,
- www.bpc.mh-hannover.de/lehre/ skript/pdf/bioinformatik_2003_007.pdf