Entropy functions and rare events in disordered systems by transfer matrix calculations and Monte Carlo sampling [Elektronische Ressource] / von Stefan Wolfsheimer

Sujets

• Physik

Informations

• Publié par: carl_von_ossietzky_universitat_oldenburg
• Publié le: 01 janvier 2009
• Nombre de lectures: 4
• Langue: English
• Poids de l'ouvrage: 5 Mo

Extrait

Entropy Functions
and
Rare Events
in Disordered Systems
by Transfer Matrix Calculations
and
Monte Carlo Sampling
Von der Fakulta¨t V (Mathematik und Naturwissenschaften) der Carl von Ossietzky
Universita¨t Oldenburg zur Erlangung des Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
angenommene Dissertation
von
Stefan Wolfsheimer
geboren am 20.09.1977 in Frankfurt am Main2
Gutachter: Prof. Dr. Alexander K. Hartmann
Zweitgutachter: Prof. Dr. Andreas Engel
Tag der Disputation: 27.02.2009
2Contents
Zusammenfassung / Abstract 1
1 Introduction 3
2 Monte Carlo methods 7
2.1 Simple sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 The Metropolis-Hastings algorithm . . . . . . . . . . . . . . . . . . . 8
2.3 The dynamics of the N-fold way . . . . . . . . . . . . . . . . . . . . 9
2.4 Parallel tempering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5.1 Equilibration . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.5.2 Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.6 Sampling of rare events I:Importance sampling and reweighting . . . 13
2.6.1 Estimation of relative normalization constants . . . . . . . . . 16
2.6.2 Illustration: Reweighting probability distributions . . . . . . . 17
2.7 Sampling of rare events II:Generalized ensemble methods . . . . . . . 18
2.7.1 Wang-Landau sampling . . . . . . . . . . . . . . . . . . . . 20
2.7.2 Optimized ensembles . . . . . . . . . . . . . . . . . . . . . . 21
2.8 Sampling of rare events III:Evaluation of the number of potential moves 24
2.8.1 The density of states by transition matrix estimates . . . . . . 24
2.8.2 The ParQ algorithm . . . . . . . . . . . . . . . . . . . . . . . 25
3 Sequence alignment 27
3.1 Notation of sequence alignment . . . . . . . . . . . . . . . . . . . . 29
3.2 Scoring models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.1 ThePAM family . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.2 TheBLOSUM family . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3 Position specific scoring for transmembrane proteins using theSLIM family 35
3.3 Optimal alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.1 Global alignment . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.2 Local alignment . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 Finite-temperature local alignment . . . . . . . . . . . . . . . . . . . 41
3.5 The linear-logarithmic phase transition . . . . . . . . . . . . . . . . . 42
3.6 Thermodynamics of local alignments by biological examples . . . . . 44
3.6.1 Strong homologs . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6.2 Weak homologs . . . . . . . . . . . . . . . . . . . . . . . . . 47
34 Contents
4 Statistics of local sequence alignment 53
4.1 Karlin-Altschul-Dembo theory and beyond . . . . . . . . . . . . . . 54
4.2 Sampling of rare events in the sequence space . . . . . . . . . . . . . 57
4.3 Statistics of two i.i.d. sequences . . . . . . . . . . . . . . . . . . . . 60
4.4 The biological example revisited . . . . . . . . . . . . . . . . . . . . 62
4.5 Statistics of position dependent alignment for transmembrane protein models 65
4.5.1 Fixed queries versus random subjects . . . . . . . . . . . . . 68
4.5.2 Random queries and position specific scoring . . . . . . . . . 71
4.6 Phase diagram and statistics of finite-temperature alignment . . . . . 76
4.7 Concluding discussion . . . . . . . . . . . . . . . . . . . . . . . . . 80
5 RNA secondary structure prediction 81
5.1 Notation of RNA secondary structures . . . . . . . . . . . . . . . . . 82
5.2 The pair-energy model . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.3 The free-energy model . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.4 The molten-glass transition . . . . . . . . . . . . . . . . . . . . . . . 91
6 Minimum-free-energy distribution of RNA secondary structures 93
6.1 Sequence models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.2 Simulation method . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.3 The minimum-free-energy distributions . . . . . . . . . . . . . . . . 96
6.3.1 Entropy and thermodynamics of large deviations . . . . . . . 98
6.3.2 Comparison between random and natural RNA sequences . . 102
6.4 Discussion and outlook . . . . . . . . . . . . . . . . . . . . . . . . . 104
7 Complex state spaces and glassy Monte Carlo dynamics 107
7.1 Markov chain Monte Carlo sampling of secondary structures . . . . . 108
7.1.1 The ParQ simulation . . . . . . . . . . . . . . . . . . . . . . 111
7.1.2 Flat-histogram and optimized ensembles . . . . . . . . . . . . 112
7.2 Convergence properties of the Monte Carlo algorithms . . . . . . . . 113
7.3 Correlation between algorithmic and structural complexity . . . . . . 116
7.3.1 Ratio of number of first excitations and ground states . . . . . 116
7.3.2 Ultrametricity of the phase space . . . . . . . . . . . . . . . . 117
7.3.3 Distribution of tunneling times of the flat histogram random walk120
7.3.4 Are all ground states visited with equal probability? . . . . . . 123
7.4 Rate of convergence in extended state spaces . . . . . . . . . . . . . 125
7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
A Additional algorithms 131
A.1 Stochastic backtracing for local alignment . . . . . . . . . . . . . . . 131
A.2 Pair probabilities of RNA secondary structures and hierarchical backtracing131
A.3 The clustering method . . . . . . . . . . . . . . . . . . . . . . . . . 133
A.4 Statistical significance of the Bhattacharyya distance measure . . . . . 134
B The +/- J spin glass: Algebraic tunneling times? 137
B.1 The Edwards-Anderson Hamiltonian . . . . . . . . . . . . . . . . . . 137
B.2 Extension of the state space . . . . . . . . . . . . . . . . . . . . . . . 139
B.3 Performance in the extended state space . . . . . . . . . . . . . . . . 141
C Fit parameters 147
4CONTENTS 5
D List of acronyms 153
Bibliography 154
Lebenslauf und Vero¨ffentlichungen 171
Stellungnahme 175
Danksagung 177
56 Contents
60. Zusammenfassung 1
Zusammenfassung
In der vorliegenden Arbeit wurden Fragestellungen der Bioinformatik mit Monte Carlo
Verfahren der statistischen Physik behandelt.
Beim Vergleich von molekularen Sequenzen (Sequenz Alignment) verwendet man
¨statistische Tests, um die Signifikanz beobachteter Ahnlichkeiten zu quantifizieren.
Verteilung der optimalen lokalen Alignment-Scores u¨ber Zufallssequenzen, insbeson-
dere seltene Ereignisse, sind ein wichtiger Bestandteil solcher Tests. Ich erweiterte eine
bereits bestehende Arbeit, in der große Abweichungen von der theoretisch vorherge-
sagten Gumbel-Verteilung gefunden wurde, auf weitere biologisch relevante Protein-
und Score-Modelle. In den meisten Fa¨llen konnten die Abweichungen durch eine
heuristisch modifizierte Gumbel-Verteilung beschrieben werden. Sie sind teilweise so
¨groß, dass einige signifikante Ahnlichkeiten in der bisherigen Praxis nicht als solche
klassifiziert werden. Dies kann eintreten, wenn man ein Suchergebnis weiter verfein-
ern mo¨chte. Zuerst betrachtete ich die Verteilung bezu¨glich des Standardmodells fu¨r
Proteinsequenzen fu¨r verschiedene Alignment-Parameter. In einem zweiten Schritt un-
tersuchte ich ein Modell, das Transmembran-Proteine beschreibt. Außerdem studierte
ich Verteilungen freier Energien kanonischer Alignment-Ensembles. Die temperat-
urabha¨ngige Form dieser Verteilungen deutete ich anhand des linear-logarithmischen
Phasenu¨bergangs, der in diesem Modell auftritt.
In einer a¨hnlichen Weise untersuchte ich RNA Sekunda¨rstrukturen. Hier wurde die
Verteilung der minimalen freien Energie ebenfalls u¨ber Zufallssequenzen bestimmt.
Mit diesen Verteilungen konnte ich biologische RNA Sequenzen gegen Zufallsmodelle
vergleichen. Dazu betrachtete ich mikrokanonische Sequenzensembles und verglich
deren statistische Eigenschaften mit biologischen RNA Sequenzen aus einer Daten-
bank.
Auch fu¨r eine Studie der Monte Carlo Dynamik in komplexen Energielandschaften
betrachtete ich RNA Sekunda¨rstrukturen. Diese stellen fu¨r solche Fragestellungen ein
ideales Modell dar, da es, im Gegensatz zu vielen anderen Modellen, exakt behan-
delt werden kann und gleichzeit komplexe glassartige Eigenschaften besitzt. Ich ver-
glich dynamische Eigenschaften verschiedener Monte Carlo Algorithmen mit statis-
chen Eigenschaften, die durch Transfermatrix-Berechnungen zuga¨nglich sind.
Abstract
This thesis treats problems from bioinformatics with Monte Carlo methods from sta-
tistical physics.
Methods to compare molecular sequences (sequence alignment) make use of sta-
tistical tests to assess the significance of observed similarities. Distributions of optimal
alignment scores over random sequences, particularly rare events, are integral parts of
such tests. I extended an existing work where large deviations from the asymptoti-
cally predicted Gumbel distribution were found to further biologically relevant scoring
and protein models. In most cases, deviations could be described by an heuristically
modified Gumbel distribution.