1/67 Johann-Wolfgang-Goethe Universität Frankfurt am Main Aktuelle Themen der Bioinformatik RNA-Sekundärstruktur- vorhersage mit Pseudoknots Johann-Wolfgang-Goethe

Johann-Wolfgang-Goethe Universität Frankfurt am Main

1/67

Aktuelle Themen der Bioinformatik

RNA-Sekundärstruktur-vorhersage mit

Pseudoknots


Vortragender:Timo Drick

Thema:


2/67

1. Einleitung1.1. Biologische Aspekte1.2. Überblick

2. Algorithmen2.1. Ohne Pseudoknots2.2. Mit Pseudoknots2.3. Vorstellung anderer Ansätze

3. Komplexität4. Zusammenfassung


3/67

Einführung - Biologische Aspekte

• RNA, was ist das?


4/67



5/67


Warum RNA?• RNA ist eine universell einsetzbare Struktur in der

Biologie. Sie erfüllt sehr viele verschiedenen Aufgaben:– mRNA (Vorlage der Proteinsynthese)– tRNA (Bereitstellung von Aminosäuren für

Proteinsynthese)– rRNA (Synthese von Proteinen)– snRNA (Splicing es gibt auch Selbstsplicende RNA)– Allgemein wird angenommen das Ursprünglich das

Leben mit RNA-Strukturen begonnen hat und daraus alles weitere Entstanden ist.


6/67

Einführung - Überblick

Warum Sekundärstrukturvorhersage?• Struktur ist wichtig um auf Funktionen zu

schließen.• 3D-Struktur ist zu komplex um

Basenpaarungen vorherzusagen.• Die Sekundärstuktur ist im Prinzip eine

Menge von Basenpaarungen in der 3D-Struktur.

• Die Sekundärstruktur kann als Grundlage für die 3D Vorhersage benutzt werden.


7/67



8/67



9/67



10/67

1. Einleitung2. Algorithmen

2.1. Ohne Pseudoknots2.2. Mit Pseudoknots2.3. Vorstellung anderer Ansätze



11/67

Algorithmen

• Prozess der Rechnergestützten Sekundärstrukturvorhersage ist sehr Komplex. Es müssen Kompromisse eingegangen werden.

• Um Methoden zu entwickeln müssen Modelle der Realität herangezogen werden.– Üblicherweise werden Gesetze aus der

Thermodynamik verwendet. Es wird die Energie für eine Struktur berechnet.

– Wenn Energie niedrig bzw. minimal dann ist die Struktur stabil.


12/67

Algorithmen - ohne Pseudoknots

Energiefunktion:• Maximierung der Anzahl von „stacking

pairs“ minimiert Energie.Stacking Pair:


13/67


• P ist eine Sekundärstruktur der RNA-Sequenz

• P ist als Menge von Basenpaaren definiert.

• Stacking Pairs werden so abgekürzt:

nsUGCAs ||}*,,,,{

jiPjijijjiiPjiji

undnjiji

4:)11(),('':'',

1:

j)1,-jq,...,-j ; qi1,...,i(i,q)-jq(i1),..,-j1(ij),(i


14/67


Erstellen eines Graphen:• Der ungerichtete Graph G(P) besteht aus n

Knoten die den Basen in S entsprechen.• Basen (i,j) bilden Kanten in G(P) falls:

j=i+1 oder (i·j) є P• Eine Sekundärstruktur ist planar wenn ihr

Graph planar ist.


15/67


Pseudoknot:• Wenn P zwei Basenpaare (i·j) und (i‘·j’)

enthält, verursachen sie einen Pseudoknot falls gilt: i<i’<j<j’


16/67


• P enthält einen „Interleaving Block“ wenn P drei SPs(i,i+1;j-1,j),(i',i'+1;j'-1,j'),(i'',i''+1;j''-1,j'') enthält für die gilt: i<i'<i''<j<j'<j''‚

Wenn P einen Interleaving Block enthält ist P nicht planar.


17/67


Stacking Pair Embedding (SPE)• SPE von S auf ein Gitter:

– Die Basen S werden als n aufeinander folgende Gitterpunkte auf einer horizontalen Gitterlinie L gezeichnet.

– i und i+1 sind verbunden.– Wenn (i,i+1;j-1,j) ein SP ist dann sind i und i+1 mit j-1

und j verbunden. Beide Kanten müssen über oder unter L liegen.


18/67


• Eine SPE ist planar wenn sie ohne Kantenüberschneidungen gezeichnet werden kann.

• Annahme: P ist eine Sekundärstruktur von S.E ist eine SPE von P. Wenn P planar ist dann muss auch E planar sein.


19/67


Beweis:• Wenn P keine planare SPE hat nehmen wir

an das P einen „Interleaving Block“ enthält und das E SPs hat die sich über L kreuzen.

• Wenn sich kein weiteres SP unter L befindet können wir eins der SPs nach unten klappen.


20/67


• Folgerung: Es muss sich mindestens noch ein SP unter L befinden.

• Probieren aller möglichen Anordnungen zeigt das E nur dann nicht ohne Überschneidungen gezeichnet werden kann wenn es sich um einen „Interleaving Block“ handelt.


21/67



22/67


MaxSP• MaxSP berechnet max # von SPs ohne

Pseudoknots.• Zwei Arrays V und W:

– V(i,j):(j>=i) enthält die max # SPs ohne Pseudoknots die mit i,...,j gebildet werden können, wenn gilt i und j bilden Watson-Crick paar.

– W(i,j):(j>=i) enthält die max # SPs ohne Pseudoknots die mit i,...,j gebildet werden können.

– W(1,n) ist die max # SP die S bilden kann.


23/67


MaxSP• Basis:

Wenn j=i, j=i+1, j=i+2, j=i+3 für die gilt (j<=n)– V(i,j)=0|i und j sind ein WC paar.– W(i,j)=0

• Rekursion:Wenn j>i+3

),1(),(maxe, Basenpaarsind und :),(

max),(1-jki jkWkiW

jijiVjiW

e Basenpaarsind und :)1,1(

e, Basenpaarsind 1-j und 1:1)1,1(max),(

jijiWijiV

jiV


24/67


• Der Algorithmus zählt SPs nur dann:– Wenn nach einem Basenpaar ein weiteres folgt.– D.h. viele SPs hintereinander zählen mehr als

einzelne SPs.• Beispiel an Tafel:


25/67


Annahme:• Gegeben ist eine RNA-Sequenz S. • N* ist die max # SPs die mit einer planaren

Sekondärstruktur von S gebildet werden kann.

• W ist die max # an SPs die mit S ohne Pseudoknots gebildet werden können.

• Dann gilt W>=N* / 2


26/67


Beweis:• P* ist eine planare Sekundärstruktur von S

mit N* SPs.• Solange P* planar ist sind alle SPEs von P*

auch planar Lemma 3.1.• E ist ein SPE von P* so dass keine Linien

im Gitter sich überschneidet. • n1 und n2 sind die # SPs über und unter L.

2und 2und

1

121

N*/ WnWN*/ n nn


27/67


• Der Algorithmus MaxSP findet mindestens ½ der möglichen SPs einer Sekondärstruktur für eine RNA-Sequenz S.

• Resourcen:– Laufzeit O(n3)– Platz O(n2)

• Es gibt O(n2) Einträge in V(i,j) und W(i,j) zu füllen.

• Pro Eintrag brauchen wir bei W(i,j) O(n) zeit und bei V(i,j) O(1) zeit.


28/67


MaxSP• Basis:

Wenn j=i, j=i+1, j=i+2, j=i+3 für die gilt (j<=n)– V(i,j)=0|i und j sind ein WC paar.– W(i,j)=0

• Rekursion:Wenn j>i+3

},j)}W(kW(i,k)

jV(i,j)|i{W(i,j)

j-ki 1maxpaar WC ein sind und

max1

}j) |i,j-W(i

j-|i),j-V(i{V(i,j)

paar WC ein sind und 11paar WC ein sind 1 und 1111

max


29/67


mfold• Berechnet minimale Energie ohne Pseudoknots.• Drei Arrays V, WM und W:

– V(i,j) enthält die minimale Energie eine Sekundärsturktur die mit i,...,j gebildet werden kann, wenn gilt i und j bilden Watson-Crick paar.

– WM(i,j) enthält die minimale Energie eine Sekundärsturktur die mit i,...,j gebildet werden kann, wenn sie Teil eines multibranched loop ist.

– W(i,j) enthält die minimale Energie der Struktur i...j


30/67


Hairpin loopStacking

BasepairsInternal loops

bulges


31/67


mfold• Resourcen:

– Laufzeit O(n3) evtl. O(cn3)– Platz O(n2)


32/67





33/67

Algorithmen - mit Pseudoknots

GreedySP(S,i) : i>=31. Finde die linkesten SPs mit i aufeinander

folgenden Basenpaaren die nicht markiert sind.Füge die Bassenpaare zu E hinzu und markiere sie.Wiederhole 1. bis keine mehr gefunden werden.

2. Für k=i-1 bis 2, Finde alle SPs mit k aufeinander folgenden Basenpaaren.Füge sie E hinzu und markiere sie.

3. Finde das linkeste SP.Füge es E hinzu und markiere es.Wiederhole bis keine weiteren vorhanden.


34/67


• Algorithmus erzeugt eine Sekundärstruktur die mindestens 1/3 der maximal möglichen SPs enthält.

• Es werden Strukturen mit vielen aufeinander folgenden Basenpaaren bevorzugt.

• Ressourcen:– Laufzeit O(ni)– Platz O(n)


35/67





36/67


Andere Herangehensweisen für Sekundärstruktur Vorhersage:

• Verwendung von Stochastischen Kontextfreien Grammatiken.

• Genetische Algorithmen• Anregung: Ansätze mit anderen

Bioinformatischen methoden (Neuronale Netze, Schwarmalgorithmen, ...)


37/67

KurzePAUSE


38/67

1. Einleitung2. Algorithmen3. Komplexität

3.1. Energiefunktion3.2. Idee3.3. Alphabet3.4. RNA-Konstuktion3.5. Beweis

4. Zusammenfassung


39/67

Komplexität

• Problem:Berechnung einer RNA-Sekondärstruktur mit minimaler Energie.

• NP-Vollständigkeit ist bewiesen.• Einfache Energiefunktion als grundlage.


40/67

Komplexität - Energiefunktion

Nearest Neighbour Pseudoknot Model S ist eine Sekundärstruktur der Sequenz s. S

ist eine Menge von Basenpaaren.Es gilt:

SjijijiEsE )1,1,()(

nsUGCAs ||}*,,,,{

'':'',1:

jjiiSjijiundnjiji


41/67

Komplexität - Energiefunktion

• Folgerungen:– Die Energie hängt ab von der Basenpaarung

selbst und von den beiden Nachbarbasen bzw. dessen Paarungen.

– Dieses Modell erlaubt alle Arten von Pseudoknots. (Es gibt keinerlei Restriktionen im bezug auf die Sekondärstruktur).


42/67



4. Zusammenfassung


43/67

Komplexität – Idee

NP-Vollständig• Klasse P:

– Efizient entscheidbare Sprachen. (Entscheidbar in Polynomialzeit)

• Klasse NP:– Sprachen die in polynomieller Laufzeit von

einer Nichtdeterministischen Turingmaschine entschieden werden können.

– Sprachen die in polynomieller Laufzeit verifiziert werden können


44/67


• Klasse NP-hart– Eine Sprache L ist NP-hart wenn alle

Sprachen in NP auf sie Reduziert werden können.

– Reduktion muss in polynomieller Laufzeit möglich sein.

• Gilt P=NP ?


45/67


Annahme 1Entscheidung ob eine optimale

Sekundärstruktur in dem NNPM eine geringere Energie als E hat, ist NP-Vollständig.

Beweis:NP: Trivial – Verifizierer kann in p-Zeit

Energie berechnen.NP-hart : Folgt.


46/67


Wie wird NP-hart Komplexität bewiesen?Reduktion auf 3SAT3SAT:

• Literal: Variable x oder x negiert.• Klausel: Disjunktion von Literalen.• Variante: Jedes Literal darf maximal 2x

auftauchen.

...)()( fedcba


47/67


• Für den Beweis sind nur Watson-Crick Basenpaarungen erlaubt.(Technische Einschränkung um die Komplexität des Beweises zu reduzieren.)

• Es wird ein Unendliches Alphabet aus Basen konstruiert. Dieses Konstrukt wird dann als Symbol betrachtet.


48/67


3.1. Energiefunktion3.2. Idee3.3. Alphabet3.4. RNA-Konstruktion3.5. Beweis

4. Zusammenfassung


49/67

Komplexität – Alphabet

Konstruktion eines unendlichen Alphabets mit Basen:

• Ein Symbol entspricht der d stelligen binären Darstellung von k

• wobei gilt: 0<=k<=2d-1 über das Alphabet {A,U} ist.

• Der String b{A,U}(k,d) der Länge d wird als binär Zahl interpretiert. A = 0 und U = 1. Das gleiche für C,G


50/67


• Das k'te eindeutige {A,U} Muster das d Binärstellen benutzt ist der String:

• A...AUb{A,U}(k,d)AUAb{A,U}(k,d)UA...A.• wobei A...A=d+2 stellen.• Gleiche gilt für GC Muster.• BSP:• k=2; d=2• A(UA)AU AUA UA(UA)A


51/67


• Spezielle Konstruktion nötig damit keine unbeabsichtigten Symbole zwischen zwei Symbolen entstehen können.

• Symbole können negiert werden und bilden dann ihr Komplement.

• Ein Symbol wird negiert indem alle As mit Us, und alle Gs mit Cs und umgekehrt vertauscht werden.

• Nur Paarungen mit komplementären Symbolen werden energetisch bevorzugt.


52/67


Symbolische-Energiefunktion:

Basenpaare zwischen Komplementären Symbolen werden energetisch bevorzugt wenn sie keine Pseudoknots mit ihren direkten Nachbarn bilden.

sandernfall0.,,,gilt

}1,...,1{'für und sindSymboleärekomplementundwenn

1,,(1''1''1'1

11 SWZVZZWZVjij

YX

WVYXEjjijjjji

jiji


53/67



4. Zusammenfassung


54/67

Komplexität – RNA-Konstuktion

• Übeführung einer Formel Ф in eine Sequenz sФ wobei gilt:– Ф liegt in der Speziellen 3SAT form vor.– sФ wird so konstruiert das die Sekundärstruktur

genau dann energetisch Minimal ist, wenn Ф erfüllbar ist.=> Wenn wir das entscheiden können, dann können wir auch 3SAT entscheiden.


55/67


Alphabet:• Für jedes Literal in Ф werden ein oder zwei

Komplementäre Symbole erzeugt.

• Für die i’te Klausel in Ф existieren zwei paare von Komplementären Symbolen

• Für die i’te Variable existiert ein Paar von komplementären Symbolen

2211 )(,)( und )(,)( llll

2211 und i,i,i,i, c, cc, c

11 i,i, v, v


56/67


Herstellen von substrings aus Klauseln.• • Der Klausel Substring SCi passend zu Ci ist der

String:

• Wenn das literal ij zum ersten Mal in Ci auftaucht dann ist ij=1 ansonsten ij=2

• Benachbarte Literale können keine Basenpaarung bilden ohne einen Pseudoknot zu verursachen.

von Klauselte' dieist 321 illlCi

2,32,1,22,1,11, 321)()()( iiiiiiiii clcclcclc


57/67


Herstellen von substrings aus Variablen• Xi ist eine Variable die 2x positiv und 2x negativ

in Ф auftaucht.• Der Substring sieht dann so aus:

• vi sind Kontrollsymbole die, die Komplementären Variablen voneinander abschirmen.

• Bei fehlen eines + bzw. - Vorkommens von Xi wird die Variable einfach weggelassen.

iiiiiii vxxvxxv 1212 )()()()(


58/67


• Ф ist eine Boolesche Formel in CNF.• Alle Klauseln enthalten max 3 Literale.• Jedes Literal taucht max 2x auf.• Angenommen Ф besteht aus c Klauseln und

benutzt v Variablen, dann ist:

• Wobei gilt das Ci ist die i’te Klausel des Substrings der zu der i’ten Klausel in Ф gehört.

vc VVVCCCs ...... 2121


59/67


Beispiel:


60/67



4. Zusammenfassung


61/67

Komplexität – Beweis

Behauptung:• Eine optimale Sekundärstruktur für sФ mit

der speziellen Energiefunktion hat genau die Energie -(3c+v) wenn und nur wenn Ф erfüllbar ist.


62/67


Wann ist eine 3SAT-Formel erfüllbar?• In jeder Klausel muss mindestens ein

Literal wahr sein.• Nur möglich wenn ein Literal in dieser

Klausel existiert das nicht in einer anderen Klausel in negierter Form gebraucht wird.

• Hier problem vereinfacht da jedes Literal maximal 2x auftaucht.


63/67


• Paarungen zwischen Literalen zeigen das das Litral wahr sein kann.

• Paarungen zwischen kontroll Symbolen in Variablesubstrings verhindern das eine Variable und ihre negation wahr sind.


64/67


3c+v• v – In jedem Variablen Block kann eine

Paarung der Kontrollsymbole stattfinden.• 2c – In jedem Klauseln Block können zwei

Paarungen zwischen Kontrollsymbolen stattfinden.

• c – ein Literal aus dem Klauseln Block kann eine Paarung mit einem Literal im Variablen Block eingehen.


65/67

Komplexität – Zusammenfassung

Zusammenfassung des Beweises:• Energiefunktion: einfache Funktion gewählt

– D.h. Komplexere Energiefunktionen können meistens darauf reduziert werden.

• Idee: Reduktion auf 3SAT– Wobei jedes Literal maximal 2x vorkommt.

• Alphabet: Binäre Kodierung von Symbolen in RNA-Basen.

– Erzeugung eines Unendlichen Alphabets.• RNA-Konstuktion: Aus 3SAT-Formel RNA-

Sequenz erstellen die genau dann minimale Energie besitzt wenn die 3SAT-Formel erfüllbar ist.


66/67

1. Einleitung1.1. Biologische Aspekte1.2. Überblick

2. Algorithmen2.1. Ohne Pseudoknots2.2. Mit Pseudoknots2.3. Vorstellung anderer Ansätze



67/67

Vielen dank für eure Aufmerksamkeit.

Schönen Feierabend

Documents

1/67 Johann-Wolfgang-Goethe Universität Frankfurt am Main Aktuelle Themen der Bioinformatik RNA-Sekundärstruktur- vorhersage mit Pseudoknots Johann-Wolfgang-Goethe