An Introduction to Bioinformatics Algorithms

by Jones, Neil C.; Pevzner, Pavel A.

• ISBN13: 9780262101066
• ISBN10: 0262101068
• Format: Hardcover
• Copyright: 2004-08-06
• Publisher: The MIT Press

Summary

This introductory text offers a clear exposition of the algorithmic principles driving advances in bioinformatics. Accessible to students in both biology and computer science, it strikes a unique balance between rigorous mathematics and practical techniques, emphasizing the ideas underlying algorithms rather than offering a collection of apparently unrelated problems. The book introduces biological and algorithmic ideas together, linking issues in computer science to biology and thus capturing the interest of students in both subjects. It demonstrates that relatively few design techniques can be used to solve a large number of practical problems in biology, and presents this material intuitively. An Introduction to Bioinformatics Algorithmsis one of the first books on bioinformatics that can be used by students at an undergraduate level. It includes a dual table of contents, organized by algorithmic idea and biological idea; discussions of biologically relevant problems, including a detailed problem formulation and one or more solutions for each; and brief biographical sketches of leading figures in the field. These interesting vignettes offer students a glimpse of the inspirations and motivations for real work in bioinformatics, making the concepts presented in the text more concrete and the techniques more approachable. PowerPoint presentations, practical bioinformatics problems, sample code, diagrams, demonstrations, and other materials can be found at the Author's website.

Author Biography

Neil C. Jones received his PhD from UCSD and is now a Staff Software Engineer at Google.

Pavel Pevzner is Ronald R. Taylor Professor of Computer Science at the University of California, San Diego. He is the author of Computational Molecular Biology: An Algorithmic Approach (MIT Press, 2000).

Table of Contents

Preface	xv
Introduction	1	(6)
Algorithms and Complexity	7	(50)
What Is an Algorithm?	7	(7)
Biological Algorithms versus Computer Algorithms	14	(3)
The Change Problem	17	(3)
Correct versus Incorrect Algorithms	20	(4)
Recursive Algorithms	24	(4)
Iterative versus Recursive Algorithms	28	(5)
Fast versus Slow Algorithms	33	(4)
Big-O Notation	37	(3)
Algorithm Design Techniques	40	(9)
Exhaustive Search	41	(1)
Branch-and-Bound Algorithms	42	(1)
Greedy Algorithms	43	(1)
Dynamic Programming	43	(5)
Divide-and-Conquer Algorithms	48	(1)
Machine Learning	48	(1)
Randomized Algorithms	48	(1)
Tractable versus Intractable Problems	49	(2)
Notes	51	(3)
Biobox: Richard Karp	52	(2)
Problems	54	(3)
Molecular Biology Primer	57	(26)
What Is Life Made Of?	57	(2)
What Is the Genetic Material?	59	(1)
What Do Genes Do?	60	(1)
What Molecule Codes for Genes?	61	(1)
What Is the Structure of DNA?	61	(2)
What Carries Information between DNA and Proteins?	63	(2)
How Are Proteins Made?	65	(2)
How Can We Analyze DNA?	67	(6)
Copying DNA	67	(4)
Cutting and Pasting DNA	71	(1)
Measuring DNA Length	72	(1)
Probing DNA	72	(1)
How Do Individuals of a Species Differ?	73	(1)
How Do Different Species Differ?	74	(1)
Why Bioinformatics?	75	(8)
Biobox: Russell Doolittle	79	(4)
Exhaustive Search	83	(42)
Restriction Mapping	83	(4)
Impractical Restriction Mapping Algorithms	87	(2)
A Practical Restriction Mapping Algorithm	89	(2)
Regulatory Motifs in DNA Sequences	91	(2)
Profiles	93	(4)
The Motif Finding Problem	97	(3)
Search Trees	100	(8)
Finding Motifs	108	(3)
Finding a Median String	111	(3)
Notes	114	(5)
Biobox: Gary Stormo	116	(3)
Problems	119	(6)
Greedy Algorithms	125	(22)
Genome Rearrangements	125	(2)
Sorting by Reversals	127	(4)
Approximation Algorithms	131	(1)
Breakpoints: A Different Face of Greed	132	(4)
A Greedy Approach to Motif Finding	136	(1)
Notes	137	(6)
Biobox: David Sankoff	139	(4)
Problems	143	(4)
Dynamic Programming Algorithms	147	(80)
The Power of DNA Sequence Comparison	147	(1)
The Change Problem Revisited	148	(5)
The Manhattan Tourist Problem	153	(14)
Edit Distance and Alignments	167	(5)
Longest Common Subsequences	172	(5)
Global Sequence Alignment	177	(1)
Scoring Alignments	178	(2)
Local Sequence Alignment	180	(4)
Alignment with Gap Penalties	184	(1)
Multiple Alignment	185	(8)
Gene Prediction	193	(4)
Statistical Approaches to Gene Prediction	197	(3)
Similarity-Based Approaches to Gene Prediction	200	(3)
Spliced Alignment	203	(4)
Notes	207	(4)
Biobox: Michael Waterman	209	(2)
Problems	211	(16)
Divide-and-Conquer Algorithms	227	(20)
Divide-and-Conquer Approach to Sorting	227	(3)
Space-Efficient Sequence Alignment	230	(4)
Block Alignment and the Four-Russians Speedup	234	(4)
Constructing Alignments in Subquadratic Time	238	(2)
Notes	240	(4)
Biobox: Webb Miller	241	(3)
Problems	244	(3)
Graph Algorithms	247	(64)
Graphs	247	(13)
Graphs and Genetics	260	(2)
DNA Sequencing	262	(2)
Shortest Superstring Problem	264	(1)
DNA Arrays as an Alternative Sequencing Technique	265	(3)
Sequencing by Hybridization	268	(3)
SBH as a Hamiltonian Path Problem	271	(1)
SBH as an Eulerian Path Problem	272	(3)
Fragment Assembly in DNA Sequencing	275	(5)
Protein Sequencing and Identification	280	(4)
The Peptide Sequencing Problem	284	(3)
Spectrum Graphs	287	(3)
Protein Identification via Database Search	290	(2)
Spectral Convolution	292	(1)
Spectral Alignment	293	(6)
Notes	299	(3)
Problems	302	(9)
Combinatorial Pattern Matching	311	(28)
Repeat Finding	311	(2)
Hash Tables	313	(3)
Exact Pattern Matching	316	(2)
Keyword Trees	318	(2)
Suffix Trees	320	(4)
Heuristic Similarity Search Algorithms	324	(2)
Approximate Pattern Matching	326	(4)
BLAST: Comparing a Sequence against a Database	330	(1)
Notes	331	(6)
Biobox: Gene Myers	333	(4)
Problems	337	(2)
Clustering and Trees	339	(48)
Gene Expression Analysis	339	(4)
Hierarchical Clustering	343	(3)
k-Means Clustering	346	(2)
Clustering and Corrupted Cliques	348	(6)
Evolutionary Trees	354	(4)
Distance-Based Tree Reconstruction	358	(3)
Reconstructing Trees from Additive Matrices	361	(5)
Evolutionary Trees and Hierarchical Clustering	366	(2)
Character-Based Tree Reconstruction	368	(2)
Small Parsimony Problem	370	(4)
Large Parsimony Problem	374	(5)
Notes	379	(5)
Biobox: Ron Shamir	380	(4)
Problems	384	(3)
Hidden Markov Models	387	(22)
CG-Islands and the ``Fair Bet Casino''	387	(3)
The Fair Bet Casino and Hidden Markov Models	390	(3)
Decoding Algorithm	393	(4)
HMM Parameter Estimation	397	(1)
Profile HMM Alignment	398	(2)
Notes	400	(7)
Biobox: David Haussler	403	(4)
Problems	407	(2)
Randomized Algorithms	409	(10)
The Sorting Problem Revisited	409	(3)
Gibbs Sampling	412	(2)
Random Projections	414	(2)
Notes	416	(1)
Problems	417	(2)
Using Bioinformatics Tools	419	(2)
Bibliography	421	(8)
Index	429