1st Edition
Introduction to Computational Biology Maps, Sequences and Genomes
Biology is in the midst of a era yielding many significant discoveries and promising many more. Unique to this era is the exponential growth in the size of information-packed databases. Inspired by a pressing need to analyze that data, Introduction to Computational Biology explores a new area of expertise that emerged from this fertile field- the combination of biological and information sciences.
This introduction describes the mathematical structure of biological data, especially from sequences and chromosomes. After a brief survey of molecular biology, it studies restriction maps of DNA, rough landmark maps of the underlying sequences, and clones and clone maps. It examines problems associated with reading DNA sequences and comparing sequences to finding common patterns. The author then considers that statistics of pattern counts in sequences, RNA secondary structure, and the inference of evolutionary history of related sequences.
Introduction to Computational Biology exposes the reader to the fascinating structure of biological data and explains how to treat related combinatorial and statistical problems. Written to describe mathematical formulation and development, this book helps set the stage for even more, truly interdisciplinary work in biology.
Introduction
Molecular Biology
Mathematics, Statistics, and Computer Science
Some Molecular Biology
DNA and Proteins
The Central Dogma
The Genetic Code
Transfer RNA and Protein Sequences
Genes Are Not Simple
Biological Chemistry
Restriction Maps
Introduction
Graphs
Interval Graphs
Measuring Fragment Sizes
Multiple Maps
Double Digest Problem
Classifying Multiple Solutions
Algorithms for DDP
Algorithms and Complexity
DDP is N P-Complete
Approaches to DDP
Simulated Annealing: TSP and DDP
Mapping with Real Data
Cloning and Clone Libraries
A Finite Number of Random Clones
Libraries by Complete Digestion
Libraries by Partial Digestion
Genomes per Microgram
Physical Genome Maps: Oceans, Islands, and Anchors
Mapping by Fingerprinting
Mapping by Anchoring
An Overview of Clone Overlap
Putting It Together
Sequence Assembly
Shotgun Sequencing
Sequencing by Hybridization
Shotgun Sequencing Revisited
Databases and Rapid Sequence Analysis
DNA and Protein Sequence Databases
A Tree Representation of a Sequence
Hashing a Sequence
Repeats in a Sequence
Sequence Comparison by Hashing
Sequence Comparison with at most l
Mismatches
Sequence Comparison by Statistical Content
Dynamic Programming Alignment of Two Sequences
The Number of Alignments
Shortest and Longest Paths in a Network
Global Distance Alignment
Global Similarity Alignment
Fitting One Sequence into Another
Local Alignment and Clumps
Linear Space Algorithms
Tracebacks
Inversions
Map Alignment
Parametric Sequence Comparisons
Multiple Sequence Alignment
The Cystic Fibrosis Gene
Dynamic Programming in r-Dimensions
Weighted-Average Sequences
Profile Analysis
Alignment by Hidden Markov Models
Consensus Word Analysis
Probability and Statistics for Sequence Alignment
Global Alignment
Local Alignment
Extreme Value Distributions
The Chein-Stein Method
Poisson Approximation and Long Matches
Sequence Alignment with Scores
Probability and Statistics for Sequence Patterns
A Central Limit Theorem
Nonoverlapping Pattern Counts
Poisson Approximation
Site Distributions
RNA Secondary Structure
Combinatorics
Minimum Free-energy Structures
Consensus folding
Trees and Sequences
Trees
Distance
Parsimony
Maximum Likelihood Trees
Sources and Perspectives
Molecular Biology
Physical Maps and Clone Libraries
Sequence Assembly
Sequence Comparisons
Probability and Statistics
RNA Secondary Structure
Trees and Sequences
References
Problem Solutions and Hints
Mathematical Notation
Algorithm Index
Author Index
Subject Index
Biography
Waterman, Michael S.
"I very much enjoyed the book, and was delighted to recommend it…the use of molecular biology to introduce and illustrate application of sophisticated mathematical theory was excellent…as an illustration of the challenges and rewards of collaborative work, it is ideal."
-Statistics: Monash University