Preface |
|
xv | |
|
|
1 | (6) |
|
Algorithms and Complexity |
|
|
7 | (50) |
|
|
7 | (7) |
|
Biological Algorithms versus Computer Algorithms |
|
|
14 | (3) |
|
|
17 | (3) |
|
Correct versus Incorrect Algorithms |
|
|
20 | (4) |
|
|
24 | (4) |
|
Iterative versus Recursive Algorithms |
|
|
28 | (5) |
|
Fast versus Slow Algorithms |
|
|
33 | (4) |
|
|
37 | (3) |
|
Algorithm Design Techniques |
|
|
40 | (9) |
|
|
41 | (1) |
|
Branch-and-Bound Algorithms |
|
|
42 | (1) |
|
|
43 | (1) |
|
|
43 | (5) |
|
Divide-and-Conquer Algorithms |
|
|
48 | (1) |
|
|
48 | (1) |
|
|
48 | (1) |
|
Tractable versus Intractable Problems |
|
|
49 | (2) |
|
|
51 | (3) |
|
|
52 | (2) |
|
|
54 | (3) |
|
|
57 | (26) |
|
|
57 | (2) |
|
What Is the Genetic Material? |
|
|
59 | (1) |
|
|
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) |
|
|
65 | (2) |
|
|
67 | (6) |
|
|
67 | (4) |
|
|
71 | (1) |
|
|
72 | (1) |
|
|
72 | (1) |
|
How Do Individuals of a Species Differ? |
|
|
73 | (1) |
|
How Do Different Species Differ? |
|
|
74 | (1) |
|
|
75 | (8) |
|
Biobox: Russell Doolittle |
|
|
79 | (4) |
|
|
83 | (42) |
|
|
83 | (4) |
|
Impractical Restriction Mapping Algorithms |
|
|
87 | (2) |
|
A Practical Restriction Mapping Algorithm |
|
|
89 | (2) |
|
Regulatory Motifs in DNA Sequences |
|
|
91 | (2) |
|
|
93 | (4) |
|
The Motif Finding Problem |
|
|
97 | (3) |
|
|
100 | (8) |
|
|
108 | (3) |
|
|
111 | (3) |
|
|
114 | (5) |
|
|
116 | (3) |
|
|
119 | (6) |
|
|
125 | (22) |
|
|
125 | (2) |
|
|
127 | (4) |
|
|
131 | (1) |
|
Breakpoints: A Different Face of Greed |
|
|
132 | (4) |
|
A Greedy Approach to Motif Finding |
|
|
136 | (1) |
|
|
137 | (6) |
|
|
139 | (4) |
|
|
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) |
|
|
178 | (2) |
|
|
180 | (4) |
|
Alignment with Gap Penalties |
|
|
184 | (1) |
|
|
185 | (8) |
|
|
193 | (4) |
|
Statistical Approaches to Gene Prediction |
|
|
197 | (3) |
|
Similarity-Based Approaches to Gene Prediction |
|
|
200 | (3) |
|
|
203 | (4) |
|
|
207 | (4) |
|
|
209 | (2) |
|
|
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) |
|
|
240 | (4) |
|
|
241 | (3) |
|
|
244 | (3) |
|
|
247 | (64) |
|
|
247 | (13) |
|
|
260 | (2) |
|
|
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) |
|
|
287 | (3) |
|
Protein Identification via Database Search |
|
|
290 | (2) |
|
|
292 | (1) |
|
|
293 | (6) |
|
|
299 | (3) |
|
|
302 | (9) |
|
Combinatorial Pattern Matching |
|
|
311 | (28) |
|
|
311 | (2) |
|
|
313 | (3) |
|
|
316 | (2) |
|
|
318 | (2) |
|
|
320 | (4) |
|
Heuristic Similarity Search Algorithms |
|
|
324 | (2) |
|
Approximate Pattern Matching |
|
|
326 | (4) |
|
BLAST: Comparing a Sequence against a Database |
|
|
330 | (1) |
|
|
331 | (6) |
|
|
333 | (4) |
|
|
337 | (2) |
|
|
339 | (48) |
|
|
339 | (4) |
|
|
343 | (3) |
|
|
346 | (2) |
|
Clustering and Corrupted Cliques |
|
|
348 | (6) |
|
|
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) |
|
|
370 | (4) |
|
|
374 | (5) |
|
|
379 | (5) |
|
|
380 | (4) |
|
|
384 | (3) |
|
|
387 | (22) |
|
CG-Islands and the ``Fair Bet Casino'' |
|
|
387 | (3) |
|
The Fair Bet Casino and Hidden Markov Models |
|
|
390 | (3) |
|
|
393 | (4) |
|
|
397 | (1) |
|
|
398 | (2) |
|
|
400 | (7) |
|
|
403 | (4) |
|
|
407 | (2) |
|
|
409 | (10) |
|
The Sorting Problem Revisited |
|
|
409 | (3) |
|
|
412 | (2) |
|
|
414 | (2) |
|
|
416 | (1) |
|
|
417 | (2) |
Using Bioinformatics Tools |
|
419 | (2) |
Bibliography |
|
421 | (8) |
Index |
|
429 | |