1 Introduction

1.1 Sequence similarity, homology, and alignment

1.2 Overview of the book

1.3 Probabilities and probabilistic models

1.4 Further reading

2 Pairwise alignment

2.1 Introduction

2.2 The scoring model

2.3 Alignment algorithms

2.4 Dynamic programming with more complex models

2.5 Heuristic alignment algorithms

2.6 Linear space alignments

2.7 Significance of scores

2.8 Deriving score parameters from alignment data

2.9 Further reading

3 Markov chains and hidden Markov models

3.1 Markov chains

3.2 Hidden Markov models

3.3 Parameter estimation for HMMs

3.4 HMM model structure

3.5 More complex Markov chains

3.6 Numerical stability of HMM algorithms

3.7 Further reading

4 Pairwise alignment using HMMs

4.1 Pair HMMs

4.2 The full probability of x and y, summing over all paths

4.3 Suboptimal alignment

4.4 The posterior probability that xi is aligned to yj

4.5 Pair HMMs versus FSAs for searching

4.6 Further reading

5 Profile HMMs for sequence families

5.1 Ungapped score matrices

5.2 Adding insert and delete states to obtain profile HMMs

5.3 Deriving profile HMMs from multiple alignments

5.4 Searching with profile HMMs

5.5 Profile HMM variants for non-global alignments

5.6 More on estimation of probabilities

5.7 Optimal model construction

5.8 Weighting training sequences

5.9 Further reading

6 Multiple sequence alignment methods

6.1 What a multiple alignment means

6.2 Scoring a multiple alignment

6.3 Multidimensional dynamic programming

6.4 Progressive alignment methods

6.5 Multiple alignment by profile HMM training

6.6 Further reading

7 Building phylogenetic trees

7.1 The tree of life

7.2 Background on trees

7.3 Making a tree from pairwise distances

7.4 Parsimony

7.5 Assessing the trees: the bootstrap

7.6 Simultaneous alignment and phylogeny

7.7 Further reading

7.8 Appendix: proof of neighbour-joining theorem

8 Probabilistic approaches to phylogeny

8.1 Introduction

8.2 Probabilistic models of evolution

8.3 Calculating the likelihood for ungapped alignments

8.4 Using the likelihood for inference

8.5 Towards more realistic evolutionary models

8.6 Comparison of probabilistic and non-probabilistic methods

8.7 Further reading

9 Transformational grammars

9.1 Transformational grammars

9.2 Regular grammars

9.3 Context-free grammars

9.4 Context-sensitive grammars

9.5 Stochastic grammars

9.6 Stochastic context-free grammars for sequence modelling

9.7 Further reading

10 RNA structure analysis

10.1 RNA

10.2 RNA secondary structure prediction

10.3 Covariance models: SCFG-based RNA profiles

10.4 Further reading

11 Background on probability

11.1 Probability distributions

11.2 Entropy

11.3 Inference

11.4 Sampling

11.5 Estimation of probabilities from counts

11.6 The EM algorithm

Bibliography

Author index

Subject index