Computational Molecular Biology : An Algorithmic Approach

by Pavel A. Pevzner

• ISBN13: 9780262161978
• ISBN10: 0262161974
• Format: Hardcover
• Copyright: 2000-08-21
• Publisher: Bradford Books

Summary

In one of the first major texts in the emerging field of computational molecular biology, Pavel Pevzner covers a broad range of algorithmic and combinatorial topics and shows how they are connected to molecular biology and to biotechnology. The book has a substantial "computational biology without formulas" component that presents the biological and computational ideas in a relatively simple manner. This makes the material accessible to computer scientists without biological training, as well as to biologists with limited background in computer science. Computational Molecular Biology series Computer science and mathematics are transforming molecular biology from an informational to a computational science. Drawing on computational, statistical, experimental, and technological methods, the new discipline of computational molecular biology is dramatically increasing the discovery of new technologies and tools for molecular biology. The new MIT Press Computational Molecular Biology series provides a unique venue for the rapid publication of monographs, textbooks, edited collections, reference works, and lecture notes of the highest quality.

Table of Contents

Preface	xiii
Computational Gene Hunting	1	(18)
Introduction	1	(1)
Genetic Mapping	1	(4)
Physical Mapping	5	(3)
Sequencing	8	(2)
Similarity Search	10	(2)
Gene Prediction	12	(2)
Mutation Analysis	14	(1)
Comparative Genomics	14	(3)
Proteomics	17	(2)
Restriction Mapping	19	(22)
Introduction	19	(2)
Double Digest Problem	21	(2)
Multiple Solutions of the Double Digest Problem	23	(3)
Alternating Cycles in Colored Graphs	26	(1)
Transformations of Alternating Eulerian Cycles	27	(5)
Physical Maps and Alternating Eulerian Cycles	32	(2)
Partial Digest Problem	34	(1)
Homometric Sets	35	(3)
Some Other Problems and Approaches	38	(3)
Optical mapping	38	(1)
Probed Partial Digest mapping	38	(3)
Map Assembly	41	(18)
Introduction	41	(3)
Mapping with Non-Unique Probes	44	(4)
Mapping with Unique Probes	48	(2)
Interval Graphs	50	(3)
Mapping with Restriction Fragment Fingerprints	53	(1)
Some Other Problems and Approaches	54	(5)
Lander-Waterman statistics	54	(1)
Screening clone libraries	55	(1)
Radiation hybrid mapping	55	(4)
Sequencing	59	(6)
Introduction	59	(2)
Overlap, Layout, and Consensus	61	(1)
Double-Barreled Shotgun Sequencing	62	(1)
Some Other Problems and Approaches	63	(2)
Shortest Superstring Problem	63	(1)
Finishing phase of DNA sequencing	63	(2)
DNA Arrays	65	(28)
Introduction	65	(2)
Sequencing by Hybridization	67	(1)
SBH and the Shortest Superstring Problem	68	(2)
SBH and the Eulerian Path Problem	70	(4)
Probability of Unique Sequence Reconstruction	74	(1)
String Rearrangements	75	(3)
2-optimal Eulerian Cycles	78	(3)
Positional Sequencing by Hybridization	81	(1)
Design of DNA Arrays	82	(2)
Resolving Power of DNA Arrays	84	(1)
Multiprobe Arrays versus Uniform Arrays	85	(2)
Manufacture of DNA Arrays	87	(4)
Some Other Problems and Approaches	91	(2)
SBH with universal bases	91	(1)
Adaptive SBH	91	(1)
SBH-style shotgun sequencing	92	(1)
Fidelity probes for DNA arrays	92	(1)
Sequence Comparison	93	(30)
Introduction	93	(3)
Longest Common Subsequence Problem	96	(2)
Sequence Alignment	98	(1)
Local Sequence Alignment	98	(2)
Alignment with Gap Penalties	100	(1)
Space-Efficient Sequence Alignment	101	(1)
Young Tableaux	102	(4)
Average Length of Longest Common Subsequences	106	(3)
Generalized Sequence Alignment and Duality	109	(2)
Primal-Dual Approach to Sequence Comparison	111	(2)
Sequence Alignment and Integer Programming	113	(1)
Approximate String Matching	114	(1)
Comparing a Sequence Against a Database	115	(1)
Multiple Filtration	116	(2)
Some Other Problems and Approaches	118	(5)
Parametric sequence alignment	118	(1)
Alignment statistics and phase transition	119	(1)
Suboptimal sequence alignment	119	(1)
Alignment with tandem duplications	120	(1)
Winnowing database search results	120	(1)
Statistical distance between texts	120	(1)
RNA folding	121	(2)
Multiple Alignment	123	(10)
Introduction	123	(2)
Scoring a Multiple Alignment	125	(1)
Assembling Pairwise Alignments	126	(1)
Approximation Algorithm for Multiple Alignments	127	(1)
Assembling 1-way Alignments	128	(2)
Dot-Matrices and Image Reconstruction	130	(1)
Multiple Alignment via Dot-Matrix Multiplication	131	(1)
Some Other Problems and Approaches	132	(1)
Multiple alignment via evolutionary trees	132	(1)
Cutting corners in edit graphs	132	(1)
Finding Signals in DNA	133	(20)
Introduction	133	(1)
Edgar Allan Poe and DNA Linguistics	134	(2)
The Best Bet for Simpletons	136	(1)
The Conway Equation	137	(3)
Frequent Words in DNA	140	(3)
Consensus Word Analysis	143	(1)
CG-islands and the ``Fair Bet Casino''	144	(1)
Hidden Markov Models	145	(2)
The Elkhorn Casino and HMM Parameter Estimation	147	(1)
Profile HMM Alignment	148	(1)
Gibbs Sampling	149	(1)
Some Other Problems and Approaches	150	(3)
Finding gapped signals	150	(1)
Finding signals in samples with biased frequencies	150	(1)
Choice of alphabet in signal finding	151	(2)
Gene Prediction	153	(22)
Introduction	153	(2)
Statistical Approach to Gene Prediction	155	(1)
Similarity-Based Approach to Gene Prediction	156	(1)
Spliced Alignment	157	(10)
Reverse Gene Finding and Locating Exons in cDNA	167	(2)
The Twenty Questions Game with Genes	169	(1)
Alternative Splicing and Cancer	169	(2)
Some Other Problems and Approaches	171	(4)
Hidden Markov Models for gene prediction	171	(2)
Bacterial gene prediction	173	(2)
Genome Rearrangements	175	(54)
Introduction	175	(12)
The Breakpoint Graph	187	(1)
``Hard-to-Sort'' Permutations	188	(1)
Expected Reversal Distance	189	(3)
Signed Permutations	192	(1)
Interleaving Graphs and Hurdles	193	(3)
Equivalent Transformations of Permutations	196	(4)
Searching for Safe Reversals	200	(4)
Clearing the Hurdles	204	(5)
Duality Theorem for Reversal Distance	209	(4)
Algorithm for Sorting by Reversals	213	(1)
Transforming Men into Mice	214	(5)
Capping Chromosomes	219	(2)
Caps and Tails	221	(2)
Duality Theorem for Genomic Distance	223	(3)
Genome Duplications	226	(1)
Some Other Problems and Approaches	227	(2)
Genome rearrangements and phylogenetic studies	227	(1)
Fast algorithm for sorting by reversals	228	(1)
Computational Proteomics	229	(22)
Introduction	229	(2)
The Peptide Sequencing Problem	231	(1)
Spectrum Graphs	232	(4)
Learning Ion-Types	236	(1)
Scoring Paths in Spectrum Graphs	237	(2)
Peptide Sequencing and Anti-Symmetric Paths	239	(1)
The Peptide Identification Problem	240	(1)
Spectral Convolution	241	(2)
Spectral Alignment	243	(2)
Aligning Peptides Against Spectra	245	(3)
Some Other Problems and Approaches	248	(3)
From proteomics to genomics	248	(1)
Large-scale protein analysis	249	(2)
Problems	251	(20)
Introduction	251	(1)
Restriction Mapping	251	(3)
Map Assembly	254	(2)
Sequencing	256	(1)
DNA Arrays	257	(2)
Sequence Comparison	259	(5)
Multiple Alignment	264	(1)
Finding Signals in DNA	264	(1)
Gene Prediction	265	(1)
Genome Rearrangements	266	(3)
Computational Proteomics	269	(2)
All You Need to Know about Molecular Biology	271	(4)
Bibliography	275	(34)
Index	309