Algorithmic aspects of bioinformatics

Advances in bioinformatics and systems biology require improved computational methods for analyzing data, while progress in molecular biology is in turn influencing the development of computer science methods. This book introduces some key problems in bioinformatics, discusses the models used to formally describe these problems, and analyzes the algorithmic approaches used to solve them.

After introducing the basics of molecular biology and algorithmics, Part I explains string algorithms and alignments; Part II details the field of physical mapping and DNA sequencing; and Part III examines the application of algorithmics to the analysis of biological data. Exciting application examples include predicting the spatial structure of proteins, and computing haplotypes from genotype data.

This book describes topics in detail and presents formal models in a mathematically precise, yet intuitive manner, with many figures and chapter summaries, detailed derivations, and examples. It is well suited as an introduction into the field of bioinformatics, and will benefit students and lecturers in bioinformatics and algorithmics, while also offering practitioners an update on current research topics.

1 Introduction	p. 1
Part I Introduction and Basic Algorithms
2 Basics of Molecular Biology	p. 7
2.1 Proteins	p. 7
2.2 Nucleic Acids	p. 9
2.3 Hereditary Information and Protein Biosynthesis	p. 12
2.4 Experimental Techniques	p. 15
2.4.1 Basic Terms and Methods	p. 15
2.4.2 Duplication of DNA	p. 15
2.4.3 Gel Electrophoresis and Direct Sequencing	p. 16
2.4.4 DNA Chips	p. 19
2.5 Bibliographic Notes	p. 20
3 Basic Concepts: Strings, Graphs, and Algorithms	p. 23
3.1 Strings	p. 23
3.2 Graphs	p. 25
3.3 Algorithms and Complexity	p. 28
3.4 Bibliographic Notes	p. 35
4 String Algorithms	p. 37
4.1 The String Matching Problem	p. 37
4.2 String Matching Automata	p. 39
4.3 The Boyer-Moore Algorithm	p. 44
4.4 Suffix Trees	p. 50
4.5 Further Applications of Suffix Trees	p. 58
4.5.1 Generalized Suffix Trees and the Substring Problem	p. 58
4.5.2 Longest Common Substrings	p. 61
4.5.3 Efficient Computation of Overlaps	p. 63
4.5.4 Repeats in Strings	p. 66
4.6 Suffix Arrays	p. 68
4.7 Summary	p. 77
4.8 Bibliographic Notes	p. 78
5 Alignment Methods	p. 81
5.1 Alignment of Two Strings	p. 82
5.1.1 Basic Definitions	p. 82
5.1.2 Global Alignment	p. 84
5.1.3 Local and Semiglobal Alignment	p. 89
5.1.4 Generalized Scoring Functions	p. 94
5.2 Heuristic Methods for Database Search	p. 97
5.2.1 The FASTA Heuristic	p. 98
5.2.2 The BLAST Heuristic	p. 99
5.3 Multiple Alignments	p. 101
5.3.1 Definition and Scoring of Multiple Alignments	p. 101
5.3.2 Exact Computation of Multiple Alignments	p. 104
5.3.3 Combining Pairwise Alignments	p. 109
5.4 Summary	p. 114
5.5 Bibliographic Notes	p. 114
Part II DNA Sequencing
6 Introduction and Overview	p. 119
7 Physical Mapping	p. 123
7.1 Restriction Site Mapping	p. 123
7.1.1 The Double Digest Approach	p. 124
7.1.2 The Partial Digest Approach	p. 131
7.1.3 Comparison of Methods for Restriction Site Mapping	p. 141
7.2 Hybridization Mapping	p. 143
7.2.1 Mapping with Unique Probes	p. 146
7.2.2 Mapping with Unique Probes and Errors	p. 157
7.2.3 Mapping with Non-unique Probes	p. 165
7.3 Summary	p. 166
7.4 Bibliographic Notes	p. 168
8 DNA Sequencing	p. 171
8.1 Shotgun Sequencing	p. 171
8.1.1 Crucial Points to Be Considered in a Suitable Model	p. 174
8.1.2 The Shortest Common Superstring Problem	p. 176
8.1.3 Refined Models for Fragment Assembly	p. 196
8.2 Sequencing by Hybridization	p. 201
8.3 Summary	p. 207
8.4 Bibliographic Notes	p. 208
Part III Analyzing Biological Data
9 Finding Signals in DNA Sequences	p. 213
9.1 Identical and Similar Substrings	p. 213
9.2 Tandem Repeats	p. 217
9.3 Frequent and Infrequent Substrings	p. 223
9.4 Hidden Markov Models	p. 228
9.5 Summary	p. 235
9.6 Bibliographic Notes	p. 235
10 Genome Rearrangements	p. 237
10.1 Modeling	p. 237
10.2 Sorting Undirected Permutations	p. 239
10.3 Sorting Directed Permutations	p. 247
10.4 Computing the Syntenic Distance	p. 249
10.5 Summary	p. 255
10.6 Bibliographic Notes	p. 255
11 Phylogenetic Trees	p. 257
11.1 Ultrametric Distances	p. 258
11.2 Additive Trees	p. 265
11.3 Characters with Binary States	p. 268
11.4 The Parsimony Principle and the Quartet Method	p. 275
11.5 Summary	p. 283
11.6 Bibliographic Notes	p. 285
12 Haplotyping	p. 287
12.1 Inferring Haplotypes from a Population	p. 288
12.2 Haplotyping a Single Individual	p. 305
12.3 Summary	p. 316
12.4 Bibliographic Notes	p. 316
13 Molecular Structures	p. 319
13.1 RNA Secondary Structure Prediction	p. 320
13.1.1 Minimizing the Free Energy	p. 322
13.1.2 Stochastic Context-Free Grammars	p. 329
13.2 Structure-Based Comparison of Biomolecules	p. 337
13.3 Protein Structure Prediction	p. 349
13.3.1 De Novo Structure Prediction - The HP Model	p. 352
13.3.2 Protein Threading	p. 363
13.4 Summary	p. 369
13.4.1 RNA Secondary Structure Prediction	p. 369
13.4.2 Structure-Based Comparison of Biomolecules	p. 371
13.4.3 Protein Structure Prediction	p. 371
13.5 Bibliographic Notes	p. 372
13.5.1 RNA Secondary Structure Prediction	p. 372
13.5.2 Structure-Based Comparison of Biomolecules	p. 373
13.5.3 Protein Structure Prediction	p. 374
References	p. 377
Index	p. 389

Available:*

On Order

Summary

Summary

Table of Contents