Upload
kioshi
View
37
Download
0
Embed Size (px)
DESCRIPTION
Predicting RNA Secondary Structures. with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs. Predicting RNA Secondary Structures. Einleitung Ein approximativer Algorithmus für planare Sekundärstrukturen Ein approximativer Algorithmus für allgemeine Sekundärstrukturen - PowerPoint PPT Presentation
Citation preview
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