Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 11
1 Introduction......Page 15
1.2 Overview of the book......Page 16
1.3 Probabilities and probabilistic models......Page 18
Maximum likelihood estimation......Page 19
Bayes’ theorem and model comparison......Page 20
Bayesian parameter estimation......Page 22
1.4 Further reading......Page 24
2.1 Introduction......Page 26
2.2 The scoring model......Page 27
Substitution matrices......Page 28
Gap penalties......Page 30
2.3 Alignment algorithms......Page 32
Global alignment: Needleman–Wunsch algorithm......Page 33
Local alignment: Smith–Waterman algorithm......Page 36
Repeated matches......Page 39
Hybrid match conditions......Page 41
Alignment with affine gap scores......Page 43
More complex FSA models......Page 46
BLAST......Page 47
FASTA......Page 48
2.6 Linear space alignments......Page 49
The Bayesian approach: model comparison......Page 50
The classical approach: the extreme value distribution......Page 53
Correcting for length......Page 54
Why use the alignment score as the test statistic?......Page 55
Dayhoff PAM matrices......Page 56
BLOSUM matrices......Page 58
2.9 Further reading......Page 59
3 Markov chains and hidden Markov models......Page 61
3.1 Markov chains......Page 62
Modelling the beginning and end of sequences......Page 64
Using Markov chains for discrimination......Page 65
3.2 Hidden Markov models......Page 66
Formal definition of an HMM......Page 68
Most probable state path: the Viterbi algorithm......Page 70
The forward algorithm......Page 72
The backward algorithm and posterior state probabilities......Page 73
Posterior decoding......Page 74
3.3 Parameter estimation for HMMs......Page 76
Estimation when the state sequence is known......Page 77
Estimation when paths are unknown: Baum–Welch and Viterbi training......Page 78
Modelling of labelled sequences......Page 81
Discriminative estimation......Page 82
Duration modelling......Page 83
Silent states......Page 85
High order Markov chains......Page 87
Finding prokaryotic genes......Page 88
Inhomogeneous Markov chains......Page 90
The log transformation......Page 92
Scaling of probabilities......Page 93
3.7 Further reading......Page 94
4 Pairwise alignment using HMMs......Page 95
4.1 Pair HMMs......Page 96
The most probable path is the optimal FSA alignment......Page 97
A pair HMM for local alignment......Page 100
4.2 The full probability of x and y, summing over all paths......Page 102
Probabilistic sampling of alignments......Page 104
4.4 The posterior probability that xi is aligned to yj......Page 106
The expected accuracy of an alignment......Page 108
4.5 Pair HMMs versus FSAs for searching......Page 110
4.6 Further reading......Page 113
5 Profile HMMs for sequence families......Page 115
5.2 Adding insert and delete states to obtain profile HMMs......Page 117
Non-probabilistic profiles......Page 120
Basic profile HMM parameterisation......Page 122
5.4 Searching with profile HMMs......Page 123
Viterbi equations......Page 124
Alternatives to log-odds scoring......Page 125
Alignment......Page 127
5.5 Profile HMM variants for non-global alignments......Page 128
Simple pseudocounts......Page 130
Dirichlet mixtures......Page 131
Substitution matrix mixtures......Page 132
Deriving P(b|a) from an arbitrary matrix......Page 133
Estimation based on an ancestor......Page 134
Testing the pseudocount methods......Page 135
MAP match–insert assignment......Page 137
5.8 Weighting training sequences......Page 139
Simple weighting schemes derived from a tree......Page 140
Root weights from Gaussian parameters......Page 141
Voronoi weights......Page 143
Maximum discrimination weights......Page 144
Maximum entropy weights......Page 145
5.9 Further reading......Page 147
6 Multiple sequence alignment methods......Page 149
6.1 What a multiple alignment means......Page 150
6.2 Scoring a multiple alignment......Page 152
Minimum entropy......Page 153
Sum of pairs: SP scores......Page 154
6.3 Multidimensional dynamic programming......Page 155
Feng–Doolittle progressive multiple alignment......Page 159
Profile alignment......Page 161
CLUSTALW......Page 162
Iterative refinement methods......Page 163
Multiple alignment with a known profile HMM......Page 164
Overview of profile HMM training from unaligned sequences......Page 166
Baum–Welch expectation maximisation......Page 167
Avoiding local maxima......Page 168
Theoretical basis of simulated annealing......Page 169
Simulated annealing Viterbi estimation of HMMs......Page 170
Adaptively modifying model architecture; model surgery......Page 172
6.6 Further reading......Page 173
7.1 The tree of life......Page 175
7.2 Background on trees......Page 177
Counting and labelling trees......Page 178
7.3 Making a tree from pairwise distances......Page 180
Clustering methods: UPGMA......Page 181
Molecular clocks and the ultrametric property of distances......Page 183
Additivity and neighbour-joining......Page 184
Rooting trees......Page 187
7.4 Parsimony......Page 188
Selecting labelled branching patterns by branch and bound......Page 192
7.5 Assessing the trees: the bootstrap......Page 194
Sankoff & Cedergren’s gap-substitution algorithm......Page 195
Hein’s affine cost algorithm......Page 196
7.7 Further reading......Page 203
7.8 Appendix: proof of neighbour-joining theorem......Page 204
Overview of the probabilistic approach to phylogeny......Page 207
8.2 Probabilistic models of evolution......Page 208
The case of two sequences......Page 212
The likelihood for an arbitrary number of sequences......Page 214
Reversibility and independence of root position......Page 217
Maximising the likelihood......Page 220
Sampling from the posterior distribution......Page 221
A proposal distribution for phylogenetic trees......Page 222
Other phylogenetic uses of sampling......Page 225
The bootstrap revisited......Page 227
8.5 Towards more realistic evolutionary models......Page 229
Allowing different rates at different sites......Page 230
Evolutionary models with gaps......Page 231
Evaluating different probabilistic models......Page 235
A probabilistic interpretation of parsimony......Page 238
Maximum likelihood and pairwise distance methods......Page 242
A probabilistic interpretation of Sankoff & Cedergren......Page 245
8.7 Further reading......Page 246
9 Transformational grammars......Page 248
Definition of a transformational grammar......Page 249
Automata......Page 251
9.2 Regular grammars......Page 252
Finite state automata......Page 253
Moore vs. Mealy machines......Page 254
PROSITE patterns......Page 255
9.3 Context-free grammars......Page 257
Parse trees......Page 259
Push-down automata......Page 260
9.4 Context-sensitive grammars......Page 262
Unrestricted grammars and Turing machines......Page 263
9.5 Stochastic grammars......Page 264
Stochastic context-sensitive or unrestricted grammars......Page 265
Hidden Markov models are stochastic regular grammars......Page 266
Normal forms for stochastic context-free grammars......Page 267
The inside algorithm......Page 268
The outside algorithm......Page 269
The CYK alignment algorithm......Page 271
9.7 Further reading......Page 273
10 RNA structure analysis......Page 275
Terminology of RNA secondary structure......Page 276
RNA sequence evolution is constrained by structure......Page 279
Inferring structure by comparative sequence analysis......Page 280
10.2 RNA secondary structure prediction......Page 282
Base pair maximisation and the Nussinov folding algorithm......Page 284
An SCFG version of the Nussinov algorithm......Page 287
Energy minimisation and the Zuker folding algorithm......Page 289
Base pair confidence estimates......Page 291
SCFG models of ungapped RNA alignments......Page 292
Design of covariance models......Page 296
Construction of a CM from an RNA alignment......Page 298
Notation......Page 299
Scoring: inside algorithm......Page 301
Inside–outside expectation maximisation for CM parameters......Page 302
Database searching: the CYK algorithm......Page 304
Structural alignment: CYK algorithm with traceback......Page 308
‘Automated’ comparative sequence analysis using CMs......Page 309
An example of a practical application of CM algorithms......Page 311
10.4 Further reading......Page 313
The binomial distribution......Page 314
The multinomial distribution......Page 315
The Dirichlet distribution......Page 317
The extreme value distribution......Page 319
11.2 Entropy......Page 320
Relative entropy and mutual information......Page 323
Maximum likelihood......Page 326
The posterior probability distribution......Page 327
Change of variables......Page 328
Sampling by transformation from a uniform distribution......Page 329
Sampling from a Dirichlet by rejection......Page 330
Sampling with the Metropolis algorithm......Page 332
Gibbs sampling......Page 333
11.5 Estimation of probabilities from counts......Page 334
Mixtures of Dirichlets......Page 336
Estimating the prior......Page 337
11.6 The EM algorithm......Page 338
EM explanation of the Baum–Welch algorithm......Page 339
Bibliography......Page 341
Author index......Page 360
Subject index......Page 365