Recently molecular biology has undergone unprecedented development generating vast quantities of data needing sophisticated computational methods for analysis, processing and archiving. This requirement has given birth to the truly interdisciplinary field of computational biology, or bioinformatics, a subject reliant on both theoretical and practical contributions from statistics, mathematics, computer science and biology. * Provides the background mathematics required to understand why certain algorithms work * Guides the reader through probability theory, entropy and combinatorial optimization * In-depth coverage of molecular biology and protein structure prediction * Includes several less familiar algorithms such as DNA segmentation, quartet puzzling and DNA strand separation prediction * Includes class tested exercises useful for self-study * Source code of programs available on a Web site Primarily aimed at advanced undergraduate and graduate students from bioinformatics, computer science, statistics, mathematics and the biological sciences, this text will also interest researchers from these fields.

Peter Clote is the author of Computational Molecular Biology: An Introduction, published by Wiley.

Rolf Backofen is the author of Computational Molecular Biology: An Introduction, published by Wiley.

Series Preface

xi

Preface

xiii

Molecular Biology

1

(22)

Some Organic Chemistry

3

(1)

Small Molecules

4

(2)

Sugars

6

(1)

Nucleic Acids

6

(8)

Nucleotides

6

(2)

DNA

8

(5)

RNA

13

(1)

Proteins

14

(3)

Amino Acids

14

(1)

Protein Structure

15

(2)

From DNA to Proteins

17

(4)

Amino Acids and Proteins

17

(2)

Transcription and Translation

19

(2)

Exercises

21

(2)

Acknowledgements and References

22

(1)

Math Primer

23

(58)

Probability

23

(30)

Random Variables

25

(2)

Some Important Probability Distributions

27

(11)

Markov Chains

38

(5)

Metropolis-Hastings Algorithm

43

(4)

Markov Random Fields and Gibbs Sampler

47

(5)

Maximum Likelihood

52

(1)

Combinatorial Optimization

53

(8)

Lagrange Multipliers

53

(1)

Gradient Descent

54

(1)

Heuristics Related to Simulated Annealing

54

(1)

Applications of Monte Carlo

55

(5)

Genetic Algorithms

60

(1)

Entropy and Applications to Molecular Biology

61

(11)

Information Theoretic Entropy

62

(1)

Shannon Implies Boltzmann

63

(3)

Simple Statistical Genomic Analysis

66

(3)

Genomic Segmentation Algorithm

69

(3)

Exercises

72

(5)

Appendix: Modification of Bezout's Lemma

77

(4)

Acknowledgements and References

79

(2)

Sequence Alignment

81

(54)

Motivating Example

83

(1)

Scoring Matrices

84

(4)

Global Pairwise Sequence Alignment

88

(23)

Distance Methods

88

(11)

Alignment with Tandem Duplication

99

(11)

Similarity Methods

110

(1)

Multiple Sequence Alignment

111

(7)

Dynamic Programming

112

(1)

Gibbs Sampler

112

(2)

Maximum-Weight Trace

114

(3)

Hidden Markov Models

117

(1)

Steiner Sequences

117

(1)

Genomic Rearrangements

118

(2)

Locating Cryptogenes and Guide RNA

120

(3)

Anchor and Periodicity Rules

122

(1)

Search for Cryptogenes

122

(1)

Expected Length of gRNA in Trypanosomes

123

(5)

Exercises

128

(4)

Appendix: Maximum-Likelihood Estimation for Pair Probabilities

132

(3)

Acknowledgements and References

133

(2)

All About Eve

135

(40)

Introduction

135

(2)

Rate of Evolutionary Change

137

(7)

Amino Acid Sequences

137

(2)

Nucleotide Sequences

139

(5)

Clustering Methods

144

(13)

Ultrametric Trees

147

(5)

Additive Metric

152

(4)

Estimating Branch Lengths

156

(1)

Maximum Likelihood

157

(9)

Likelihood of a Tree

159

(1)

Recursive Definition for the Likelihood

160

(2)

Optimal Branch Lengths for Fixed Topology

162

(4)

Determining the Topology

166

(1)

Quartet Puzzling

166

(5)

Quartet Puzzling Step

169

(1)

Majority Consensus Tree

170

(1)

Exercises

171

(4)

Acknowledgements and References

173

(2)

Hidden Markov Models

175

(26)

Likelihood and Scoring a Model

177

(3)

Re-estimation of Parameters

180

(13)

Baum--Welch Method

181

(3)

EM and Justification of the Baum-Welch Method

184

(3)

Baldi--Chauvin Gradient Descent

187

(4)

Mamitsuka's MA Algorithm

191

(2)

Applications

193

(4)

Multiple Sequence Alignment

193

(1)

Protein Motifs

194

(1)

Eukaryotic DNA Promotor Regions

195

(2)

Exercises

197

(4)

Acknowledgements and References

198

(3)

Structure Prediction

201

(62)

RNA Secondary Structure

202

(11)

DNA Strand Separation

213

(10)

Amino Acid Pair Potentials

223

(5)

Lattice Models of Proteins

228

(6)

Monte Carlo and the Heteropolymer Protein Model

231

(2)

Genetic Algorithm for Folding in the HP Model

233

(1)

Hart and Istrial's Approximation Algorithm

234

(9)

Performance

234

(2)

Lower Bound

236

(3)

Block Structure, Folding Point, and Balanced Cut

239

(4)

Constraint-Based Structure Prediction

243

(3)

Protein Threading

246

(13)

Definition

246

(3)

A Branch-and-Bound Algorithm

249

(9)

NP-hardness

258

(1)

Exercises

259

(4)

Acknowledgements and References

261

(2)

Appendix A Mathematical Background

263

(2)

A.1 Asymptotic complexity

263

(1)

A.2 Units of Measurement

263

(1)

A.3 Lagrange Multipliers

264

(1)

Appendix B Resources

265

(4)

B.1 Web Sites

265

(1)

B.2 The PDB Format

266

(3)

References

269

(12)

Index

281

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

Amazon no longer offers textbook rentals. We do!

Amazon no longer offers textbook rentals. We do!

We're the #1 textbook rental company. Let us show you why.

Computational Molecular Biology An Introduction

9780471872528

0471872520

Supplemental Materials

Summary

Author Biography

Table of Contents

Supplemental Materials

Rewards Program