Lesender: Dr. Konstantin KlemmLehrstuhl fur Bioinformatik

Institut fur InformatikUniversitat Leipzig

Statistische Physik fur Bioinformatiker- WS 06 -

gesetzt in LATEX von Stefan Wirth1

19. Juni 2007

1wirth.s@gmx.net

Dieses Skript wurde begleitend zur Vorlesung erstellt und vom Lesenden selbst nocheinmal durchgesehen. Der Autor gibt keine Garantie auf die Richtigkeit der dargelegtenFakten!Eine kostenlose Weiterverbreitung und Verfielfaltigung ist gestattet, auch dieVerwendung als Grundlage fur Vorlesungen. Alle Anderungen des Dokuments mussenmit dem Autor abgesprochen sein!

Inhaltsverzeichnis

Abbildungsverzeichnis iii

1 Extrema unter Nebenbedingungen 1

2 Grundlagen der statistischen Mechanik 32.1 Physikalische Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Energie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2.1 Energieerhaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3 Entropie (=Information) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.4 Prinzip maximaler Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.5 Entropie-Maximierung bei gegebener mittlerer Energie . . . . . . . . . . . . . . . . . . . . 4

3 Informationen in der Zustandssumme 73.1 freie Energie (Helmholtz) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.2 mittlere Energie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.3 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.4 Warmekapazitat (spezifische Warme) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.5 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.5.1 Spin im Magnetfeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.5.2 N Spins im Magnetfeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.5.3 Spinkette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.5.4 N Spins im eigenen Magnetfeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.5.5 Phasenubergang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Monte-Carlo 154.1 Monte-Carlo Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.1.1 praktische Falle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.1.2 Metropolis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.1.3 2D-Ising-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.2 Multi-Kanonisches Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5 RNA-Faltung 195.1 Kinfold . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

i

Inhaltsverzeichnis

ii

Abbildungsverzeichnis

3.1 Die Energiekurve wird zunehmend scharfer (Varianz kleiner) . . . . . . . . . . . . . . . . . 123.2 grafische Losung der Mean-Field Approximation . . . . . . . . . . . . . . . . . . . . . . . 133.3 unterhalb der kritischen Temeperatur geht das System zufallig in einen der beiden Zustande

uber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4.1 Beispiel eines Systems, das kein detailliertes Gleichgewicht aufweist . . . . . . . . . . . . . 164.2 Histogramm vor dem Glatten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.3 Histogramm nach dem Glatten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

iii

Abbildungsverzeichnis

iv

1 Extrema unter Nebenbedingungen

(Lagrange-Multiplikatoren)gegeben: f : R→ R, differenzierbarf hat kritische Stelle (Extrema) in x gdw. f(x) = 0x ist Maximum von f → f ′(x) = 0f : Rn → Rn, diff.bar; Die Ableitung ist hier der Gradient:f hat Maximum in x, so ∇f(x) = ~0 ∈ Rn

∇f = ( ∂f∂x1

, ∂f∂x2

, . . . , ∂f∂xn

) = (∂1f, ∂2f, ..)

Problemstellung: gegeben: f : Rn → R, g : Rn → R, diff.bargesucht: Maximum x ∈ Rn von f unter der Bedingung g(x) = c

Beispiel: n = 2 f(x, y) = −x2 − y2, g(x, y) = x ∗ y = 1 also sind Linien gesucht, die erfullen: y = 1x ,

dies sind genau Hyperbeln. f erzeugt als Ergebnisse ein Kreisfeld um den Koordinatenursprung. Manlauft auf der g-Kurve lang und sucht das Maximum von f , dies ist genau am Umkehrpunkt in demKreis der Fall.

Lagrange-Multiplikatoren Sei x′ ∈ Rn lokales Maximum von f unter der Bedingung g(x, y) = c. Dannist:

∇L(x′) = 0, furL(x) = f(x) + λ(g(x)) und geeignetes λ ∈ R

soll also heißen, dass L(x) der Punkt auf der Tangente und Normale ist. Entlang der Tangente kann mitlinearer Ordnung verschoben werden, ohne den Wert von f signifikant zu andern. In Richtung derNormalen hingegen sind die Anderungen am großten.

∇(f(x) + λg(x)) = 0∇f(x′) = −λ∇g(x′)

Man kann damit Maxima unter allen erdenklichen Nebenbedingungen finden.

Beispiel: f(x, y) = −x2 − y2, g(x, y) = x ∗ y und Einsetzen:

∇(f(x) + λg(x)) = 0∇(−x2 − y2 + λx ∗ y) = 0

−2x + λy = 0 und− 2y + λx = 0

x =λ

2y

y =λ

2x

x =λ2

4x

1

1 Extrema unter Nebenbedingungen

damit ist fur λ ∈ {−0.5, 0.5} x = y (Einsetzen in letzter Zeile) und damit:

g(x, y) = x

x ∗ y = c

x = y = ±√

(c)

2

2 Grundlagen der statistischen Mechanik

2.1 Physikalische Systeme

• n Zustande, die mit gegebener Wahrscheinlichkeit auftreten, damit ist |X| = n die Menge allerZustande und p : X → [0, 1], pi ist Wahrscheinlichkeit des i-ten Zustandes.Beispielsweise die Darstellung fur Spins (kleine magnetische Momente, zeigen entweder nach obenoder unten): X = Bn binare Zustande

2.2 Energie

E : X → R

Ei ist die Energie des i-ten ZustandesBetrachte 2 physikalische Systeme, die keine Wechselwirkung haben (nicht interagieren):X, Y diese konnen auch als ein System gesehen werden: X × Y GesamtsystemE1 : X → R, E2 : Y → R, damit wird definiert:Egesamt : X × Y → R, Egesamt

ij = E1i + E2

j

Dies besagt, dass Energie additiv ist.

2.2.1 Energieerhaltung

Energiewert ε gegeben (Das System hat Energie ε)Daraus weiß man, dass nur Zustande i mit Ei = ε angenommen werden.

Beispiel: X = Bn (die Spins von oben) Ex =∑n

i=1 xi mit ε gegeben:σ(ε) =

(nε

)Zustande mit der Energie ε (σ ist Zustandsdichte)

2.3 Entropie (=Information)

zentrale Frage: wieviel Information bekommt man?Beispiel:

p : X → [0, 1]

pi =

{1 i = 10 sonst

damit ist die Entropie hierbei gleich 0

3

2 Grundlagen der statistischen Mechanik

Entropie S Die mittlere Zahl der Ja / Nein Fragen, die notig sind, um die Messung eindeutig zubeschreiben.Beispiel: pi = 1

n , Wenn man n Zustande hat, dann sind das wohl S ≈ log2 n (aufgerundet)Beispiel: p1 = 0.5, p2 = 0.25, p3 = 0.25, damit ist S = 1 + 0.5 ∗ 1 = 1.5

also: S = −∑

i pi log2 pi =∑

i pi log21pi

ist die Entropie des Wahrscheinlichkeitsvektors (p1, .., pn)

Zwei unabangige Systeme:

p : X → [0, 1]q : Y → [0, 1]

man will, dass die Systeme sich additiv verhalten was die Entropie angeht (man erhalt ja dieInformation aus beiden Systemen, die nicht uberlappen, da sie unabhangig sind)

S = −n∑

i=1

m∑j=1

pi ∗ qj ∗ log2 piqj

= −n∑

i=1

m∑j=1

piqj(log2 pi + log2 qj)

= −n∑

i=1

m∑j=1

piqj log2 pi −n∑

i=1

m∑j=1

piqj log2 qj

=

(m∑

i=1

qj

)︸ ︷︷ ︸

=1

(−

n∑i=1

pi log2 pi

)︸ ︷︷ ︸

Sx

+

(n∑

i=1

pi

)︸ ︷︷ ︸

=1

− m∑j=1

qj log2 qj

︸ ︷︷ ︸

Sy

= Sx + Sy

2.4 Prinzip maximaler Entropie

Fur Systeme im Gleichgewicht hat die Wahrscheinlichkeitsverteilung maximale Entropie unter dengegebenen Nebenbedingungen.

< E >=n∑

i=1

piEi

ist der Mittelwert der Energie.Betrachte System Y = Xr ein komplexes System (bestehend aus mehreren gleichen Systemen X)

< E >x=1r

< E >y=1rε

wobei das ε die Energie des Systems X ist.

2.5 Entropie-Maximierung bei gegebener mittlerer Energie

vergleiche Kapitel 1 und setze:

”S → f “, ”< E >= g “

4

2.5 Entropie-Maximierung bei gegebener mittlerer Energie

Wende Methode mit Lagrange-Multiplikatoren an: man will die Entropie maximieren (deshalb auchL(p)) und den Mittelwert der Energie beibehalten.1

L(p) = s(p) + λ < E > (p) + µ∑

pi︸ ︷︷ ︸=1

L(p) = s(p) + λ

n∑i=1

pi − β < E >

= −n∑

i=1

pi ln pi + λ

n∑i=1

pi − β

n∑i=1

piEi

∇L(p) = 0⇔ ∀i ∈ n′ :∂L

∂pi= 0

wobei n′ = {1, 2, .., n}

0 =∂L

∂pi= − ln pi − 1 + λ− βEi

ln pi = −1 + λ− βEi

pi = exp(−1 + λ− βEi) ∝ exp(−βEi)

Die letzte Zeile ist damit die Boltzmann-Gibbs-Verteilung2 und exp(−βEi) der Boltzmann-Faktor.damit:

pi =exp(−βEi)

Z(β)

Z =n∑

j=1

exp(−βEj)

Z(β) ist die Zustandsumme, wobei β = 1T die inverse Temperatur ist.

Wird ein System immer weiter abgekuhlt, dann kommt man dem Grundzustand mit Wahrscheinlichkeit1 sehr nahe, also alle anderne Zustande erhalten die Wahrscheinlichkeit 0. (β →∞, E = 0, exp(0) = 1)Das Gleichgewicht der Boltzmann-Gewichte ist die Maximale Entropie.

Betrachtung pi = 1Z exp(−βEi)

• β = 0, T = +∞: pi = pj fur alle i, j ∈ X (Zustandsraum), pi = 1|X|

• β →∞, T → 0: siehe Beispiel

Beispiel: X = {1, 2}, E1 = 0, E2 = 1

p1 =1Z

exp(−β ∗ 0) =1Z

=1

1 + exp(−β)β→∞→ 1

p2 =1Z

exp(−β ∗ 1) =exp(−β)

Z=

exp(−β)1 + exp(−β)

β→∞→ 0

Z = 1 + exp(−β)

1hier wird einfach mal mit ln gerechnet, denn: log2 x = ln xln 2

2∝ heisst:”proportional zu“

5

2 Grundlagen der statistischen Mechanik

6

3 Informationen in der Zustandssumme

3.1 freie Energie (Helmholtz)

Die freie Energie F kann aus der Zustandssumme gewonnen werden:

F =− lnZ

β

Mit der Partitionierung des Zustandsraums X = X1 ∪X2, X1 ∩X2 = ∅:

F1 =− lnZ1

β, Z1 =

∑i∈X1

exp(−βEi) (3.1)

F2 =− lnZ2

β, Z2 =

∑i∈X2

exp(−βEi) (3.2)

Z = Z1 + Z2 = exp(−βF1) + exp(−βF2) (3.3)

= exp(−β(−lnZ1

β)) + exp(−β(

−lnZ2

β)) (3.4)

= Z1 + Z2 = Z (3.5)

Die Idee der Vereinigung ist, dass die Rechnung geteilt werden kann.

3.2 mittlere Energie

U =< E > =∑

i

piEi (3.6)

=∑

i

exp(−βEi)Z

Ei (3.7)

Nebenbetrachtung1:

Z =∑

i

exp(−βEi) (3.8)

∂Z

∂β= −

∑i

exp(−βEi)Ei (3.9)

1Z hangt von β ab

7

3 Informationen in der Zustandssumme

Einsetzen und Probe:

U = − 1Z

∂Z

∂β= −∂ lnZ

∂β(3.10)

=1Z

∂ lnZ

∂β(3.11)

=1Z

∑i

exp(−βEi)Ei (3.12)

=∑

i

pi ∗ Ei (3.13)

3.3 Entropie

S = −∑

i

pi ln pi (3.14)

= −∑

i

exp(−βEi)Z

ln(

exp(−βEi)Z

)(3.15)

= −∑

i

exp(−βEi)Z

[ln exp(−βEi)− lnZ)] (3.16)

= −∑

i

exp(−βEi)Z

(−βEi)−exp(−βEi)

ZlnZ (3.17)

= β∑

i

exp(−βEi)Z︸ ︷︷ ︸pi

Ei +(∑

i

exp(−βEi)︸ ︷︷ ︸Z

) lnZ

Z(3.18)

= βU + lnZ (3.19)

Von Zeile 3.17 nach 3.18 wurde die Summe auseinander genommen und aus der ersten Summe das −βherausgezogen.Herleitung fur die freie Energie F :

F = U − TS (3.20)

= −∂ lnZ

∂β− T (βU + lnZ) (3.21)

= −∂ lnZ

∂β− TβU − T lnZ (3.22)

= −∂ lnZ

∂β︸ ︷︷ ︸U

−U −T lnZ︸ ︷︷ ︸F

(3.23)

= −T lnZ = − lnZ

β= F (3.24)

8

3.4 Warmekapazitat (spezifische Warme)

3.4 Warmekapazitat (spezifische Warme)

C =∂U

∂T=

∂

∂T(−∂ lnZ

∂β) (3.25)

=∂

∂β(−∂ lnZ

∂β)∂β

∂T(3.26)

=∂

∂β(−∂ lnZ

∂β)(−β2) (3.27)

= β2 ∂2 lnZ

∂β(3.28)

C = −β2 ∂

∂βi

∑i

exp(−βEi)Z

Ei (3.29)

= −β2[∑

i

exp(−βEi)Z

(−E2i ) +

∑i

exp(−βEi)Ei∂

∂β

1Z︸ ︷︷ ︸

=− 1Z2

∂Z∂β

] (3.30)

= −β2[−∑

i

exp(−βEi)Z

E2i − U

1Z

∂Z

∂β] (3.31)

= −β2[− < E2 > + < E >2] (3.32)= β2 (< E2 > − < E >2)︸ ︷︷ ︸

Schwankungsquadrat der Energie

(3.33)

(< E2 > − < E >2) = −∂U

∂β=

1β2

C (3.34)

C = −β2 ∂U

∂β(3.35)

β(T ) = 1T , β′(T ) = − 1

T 2 = −β2.

3.5 Beispiele

3.5.1 Spin im Magnetfeld

X = {−1, 1} ein 1-Spin-System mit σ ∈ {−1, 1} als Spin-Variable. σ beschreibt die Rotation einesTeilchens (die Ausrichtung). Die Teilchen liegen in einem Magnetfeld, das eine bestimmte Richtung Bunabhangig von den Teilchen hat. Somit ist die Energie des Teilchens davon abhangig, wie es zu demFeld steht:

E−1 = −B (3.36)E1 = B (3.37)E = σ ∗B (3.38)

9

3 Informationen in der Zustandssumme

und damit:

Z =∑σ∈X

exp(−βEσ) = exp(βB) + exp(−βB) = 2 cosh(βB) (3.39)

U = −∂ lnZ

∂β= − 1

Z

∂Z

∂β= −B sinh(βB)

cosh(βB)= −B tanh(βB) (3.40)

C = B2 β2

cosh2 βB(3.41)

(< E2 > − < E >2) = B2 1cosh2 βB

(3.42)

Nebenrechnungen:

12(exp(x) + exp(−x)) = cosh(x)

(cosh(x))′ =12(exp(x)− exp(−x)) = sinh(x)

(sinh(x))′ =12(exp(x) + exp(−x)) = cosh(x)

sinhx

coshx= tanhx

tanh x ∈ (−1,+1)

10

3.5 Beispiele

3.5.2 N Spins im Magnetfeld

X = {−1,+1}N und damit ergeben sich ganze Spin-Strings (wie Binarstrings, aber auf -1,+1),σ ∈ X, (σ1, σ2, .., σN )

Eσ =N∑

j=1

σjB

Z =∑σ∈X

exp(−βEσ) =∑σ∈X

exp(−β

N∑j=1

σjB)

=∑σ∈X

N∏j=1

exp(−βσjB) =∑σ∈X

exp(−βσ1B) ∗ exp(−βσ2B) ∗ . . . ∗ exp(−βσNB)

=

∑σ1∈{−1,+1}

exp(−βσ1B)

∗ ∑

σ2∈{−1,+1}

exp(−βσ2B)

∗ . . . ∗

∑σN∈{−1,+1}

exp(−βσNB)

=

∑σ∈{−1,+1}

exp(−βσB)

N

= (2 coshβB)N

U = −∂ lnZ

∂β= − ∂

∂βln[(2 coshβB)N ]

= − ∂

∂β[N ln(2 coshβB)]

= −NB tanh βB

(< E2 > − < E >2) = NB2 1cosh2 βB

< σ > = − tanh βB

erstes Ergebnis: relative Schwankung:√

< E2 > − < E >2

< E >=

√NB( 1

cosh βB )

−NB tanh βB= − 1√

N︸ ︷︷ ︸Energie wird scharf, s. Abb. 3.1

1sinhβB

N→∞→ 0

3.5.3 Spinkette

N Spins, jeder sieht das Feld seines Vorgangers und seines Nachfolgers.

Eσ = J

N∑i=1

σiσi+1, J < 0 reellwertiger Parameter

σ′i = σiσi+1

Eσ′ = J

N∑i=1

σi

11

3 Informationen in der Zustandssumme

Abbildung 3.1: Die Energiekurve wird zunehmend scharfer (Varianz kleiner)

2 aufeinanderfolgende σ gleich: σ′ ist positiv. Dies lasst sich nun abbilden auf (N-1) Spins imMagnetfeld:

Z = (2 coshβJ)N−1

3.5.4 N Spins im eigenen Magnetfeld

Bisher zerfiel das System in N unabhangige Systeme, ohne Interaktionen. Dies ist hier jetzt nicht mehrso, sondern betrachtet wird nun auch das Magnetfeld, welches die Spins selbst erzeugen.X = {−1,+1}N

Eσ = B(σ)N∑

i=1

σi

B(σ) = − 1N

N∑i=1

σi = − < σ >

”Mean-Field“ Approximation (Molekularfeldnaherung):

< σ > = −B (selbst erzeugtes Magnetfeld)< σ > = − tanh βB (außeres Magnetfeld)

Selbstkonsistentrechnung sagt, dass diese gleich sein mussen:

B = tanhβB

− < σ > = tanhβ(− < σ >)< σ > = tanhβ(< σ >)

Diese Gleichung kann nicht vollstandig gelost werden (man kann tanh nicht vernunftig auflosen),grafisch siehe Abbildung 3.2.

Von den 3 Losungen existiert nur die 0 immer, denn der tanh konnte ja so gestreckt werden, dass dieanderen Schnittpunkte nicht existieren. Anstieg:(

d

d < σ >tanh β < σ >

)(0) =

(β

1cosh2 β < σ >

)(0) = β

Von Null verschiedene Losungen ⇔ β > 1; βc ist kritische (inverse) Temperatur. Curie-Temperatur

12

3.5 Beispiele

Abbildung 3.2: grafische Losung der Mean-Field Approximation

Abbildung 3.3: unterhalb der kritischen Temeperatur geht das System zufallig in einen der beiden Zustande uber

3.5.5 Phasenubergang

• Magnetische Systeme, Ordnung ↔ Unordnung

• Flussig ↔ Fest

• Schwer ↔ Leicht (Optimierungsprobleme)

13

3 Informationen in der Zustandssumme

14

4 Monte-Carlo

Um Systeme zu beschreiben sind teilweise sehr viele Informationen notig bzw. wird das Problemhinreichend groß, sodass man andere Methoden (stochastische) nehmen muss, um Berechnungendurchzufuhren.Beispiel: < E >=

∑i piEi

1. Problem: |X| ist im Allgemeinen zu groß, um Summe ausfuhren zu konnen (numerisch)Losung: Sampling.S ⊂ X zufallig erzeugen, < E >≈

Pi∈S piEiP

i∈S pi

2. Problem: Wenn Wahrscheinlichkeit auf wenige Zustande konzentriert ist, wird dieses Samplingbeliebig ungenau.Losung: Important Sampling.i ∈ S mit Wahrscheinlichkeit pi. Dann < E >≈

Pi∈S Ei

|S|

4.1 Monte-Carlo Importance Sampling

(Markov-Ketten-Monte Carlo) Gegeben sind die Wahrscheinlichkeiten p(x), x ∈ X.1

Dies ist dann ein Markov-Prozess mit:

Ubergangswahrscheinlichkeiten (wie vorher: x→ y):

h(y|x)

Kette: ... x, y︸︷︷︸h(y|x)

Detailliertes Gleichgewicht:

h(y|x)p(x) = h(x|y)p(y)h(y|x)h(x|y)

=p(y)p(x)

Es ist also Gleichwahrscheinlich, dass xy und yx auftritt. Bedingung: h(y|x) = 0⇔ h(x|y) = 0(Gegenbeispiel: 3 Punkte, gleiche Wahrscheinlichkeit, Ubergange gerichtet im Kreis, Abbildung 4.1)

Nachbarschaftsstruktur auf X:M(x) = Menge der Nachbarn von xSymmetrie: x ∈M(y)⇔ y ∈M(x)h(y|x) 6= 0⇔ y ∈M(x)

1Erzeuge eine Kette von Zustanden

15

4 Monte-Carlo

Abbildung 4.1: Beispiel eines Systems, das kein detailliertes Gleichgewicht aufweist

Damit kann man einen Monte Carlo Schritt definieren:

h(y|x) = f(y|x)︸ ︷︷ ︸Vorschlagswahrscheinlichkeit

∗ g(y|x)︸ ︷︷ ︸Akzeptanzwahrscheinlichkeit

f(y|x) .. Wahrscheinlichkeit y vorzuschlagen, wenn aktuell bei xg(y|x) .. Wahrscheinlichkeit zu akzeptieren, gegeben aktueller Zustand x und Vorschlagy = Pr{Akzeptanz|y, x}

4.1.1 praktische Falle

Mx .. Nachbarn von x

f(y|x) =

{1

|M(x)| y ∈ m(x)

0 sonst

4.1.2 Metropolis

g(y|x) = min

{1,

p(y)f(x|y)p(x)f(y|x)

}g(y|x) = min

{1,

p(x)f(y|x)p(y)f(x|y)

}mit dieser Wahl kann man den gesamten Zustandsraum durchschreiten und bleibt nicht hangen.

p(x) =1Z

exp(−βEx)

g(y|x) = min

{1,

exp(−βEy)f(x|y)exp(−βEx)f(y|x)

}= min

{1, exp(−β(Ey − Ex))

f(x|y)f(y|x)

}

Zeige: h(y|x)h(x|y) = p(y)

p(x) (also dass das definierte Gleichgewicht von Metropolis erfullt wird)

g(y|x)g(x|y)

= min

f(x|y)p(y)f(y|x)p(x)

1,

1p(x)f(y|x)p(y)f(x|y)

=p(y)f(x|y)p(x)f(y|x)

h(y|x)h(x|y)

=g(y|x)f(y|x)g(x|y)f(x|y)

=p(y)p(x)

Detailliertes Gleichgewicht gilt also.

16

4.2 Multi-Kanonisches Monte Carlo

Boltzmann-Gibbs auf regularem Graph

g(y|x) = min{1, exp(−β∆E)}

∆E = Ey − Ex, also die Differenz der Energien. Ist in der Praxis oft eine ganze Zahl (Z) auf einembekannten Intervall und lasst sich somit sehr schnell berechnen. (Beispiel:∆E ∈ {−4,−3,−2,−1, 0, 1, 2, 3, 4}, einmal berechnen, dann nachschlagen)

4.1.3 2D-Ising-Modell

Spins auf einem quadratischen Gitter2. (an jedem Knoten eine Spinvariable σi ∈ {−1,+1}). Hierhangen die Energiebeitrage vom Vergleich der Spins mit den Nachbarn im Gitter ab.E(σ) = −

∑{i,j}∈GITTER σiσj

4.2 Multi-Kanonisches Monte Carlo

Wenn die Energielandschaft viele niedrigen Egiezustande besitzt, aber immer getrennt durch sehr hoheBerge, so findet man die vielen Moglichkeiten nicht, wenn man nicht uber die Berge druberkommt.

Ziel Sampling, so dass alle Energiewerte mit derselben Wahrscheinlichkeit auftreten. (Energiewertesind diskret, am besten aquidistant)

p(x) ∝ exp(−βEi)Metropolis→ Energie-Histogramm (Abb. 4.2) H(E) → p(x)← p(x)

H(Ex) (bis auf

Normierung)Metropolis Sampling→ flacheres Histogramm (Abb 4.3, in jedem Schritt flacher).

Abbildung 4.2: Histogramm vor dem Glatten

Abbildung 4.3: Histogramm nach dem Glatten

Somit werden die Wahrscheinlichkeiten fur die Werte am Anstieg des Berges erhoht, da sie viel seltenerauftreten. Dies erleichtert dann im nachsten Schritt den Aufstieg auf den Berg und irgendwann kommt

2in den 30-ern aufgestelltes Modell und Losung in den 60-ern

17

4 Monte-Carlo

man in ein neues Tal. Man muss sich nur Die Anderungen der p(x) merken, um dies am Ende wiederruckgangig zu machen.mit Energiedichte σ(E): p(E)→ 1

σ(E) (bis auf Normierung)

18

5 RNA-Faltung

5.1 Kinfold

Nimmt als Input RNA-Sequenzen und simuliert die Faltung an diesen. Ausgabe: freie Energie und dieZeitpunkte.Ist mit einer Variante des Metropolis implementiert, die niemals ablehnt; dies ergibt die stetigenZeitpunkte (bei normalem Metropolis ware sie diskret).

19

5 RNA-Faltung

20