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