《an introduction to bioinformatics algorithms P435》求取 ⇩

1Introduction1

2Algorithms and Complexity7

2.1 What Is an Algorithm?7

2.2 Biological Algorithms versus Computer Algorithms14

2.3 The Change Problem17

2.4 Correct versus Incorrect Algorithms20

2.5 Recursive Algorithms24

2.6 Iterative versus Recursive Algorithms28

2.7 Fast versus Slow Algorithms33

2.8 Big-O Notation37

2.9Algorithm Design Techniques40

2.9.1 Exhaustive Search41

2.9.2 Branch-and-Bound Algorithms42

2.9.3 Greedy Algorithms43

2.9.4 Dynamic Programming43

2.9.5 Divide-and-Conquer Algorithms48

2.9.6 Machine Learning48

2.9.7 Randomized Algorithms48

2.10 Tractable versus Intractable Problems49

2.11Notes51

Biobox: Richard Karp52

2.12 Problems54

3Molecular Biology Primer57

3.1 What Is Life Made Of?57

3.2 What Is the Genetic Material?59

3.3 What Do Genes Do?60

3.4 What Molecule Codes for Genes?61

3.5 What Is the Structure of DNA?61

3.6 What Carries Information between DNA and Proteins?63

3.7 How Are Proteins Made?65

3.8How Can We Analyze DNA?67

3.8.1 Copying DNA67

3.8.2 Cutting and Pasting DNA71

3.8.3 Measuring DNA Length72

3.8.4 Probing DNA72

3.9 How Do Individuals of a Species Differ?73

3.10 How Do Different Species Differ?74

3.11Why Bioinformatics?75

Biobox: Russell Doolittle79

4Exhaustive Search83

4.1 Restriction Mapping83

4.2 Impractical Restriction Mapping Algorithms87

4.3 A Practical Restriction Mapping Algorithm89

4.4 Regulatory Motifs in DNA Sequences91

4.5 Profiles93

4.6 The Motif Finding Problem97

4.7 Search Trees100

4.8 Finding Motifs108

4.9 Finding a Median String111

4.10Notes114

Biobox: Gary Stormo116

4.11 Problems119

5Greedy Algorithms125

5.1 Genome Rearrangements125

5.2 Sorting by Reversals127

5.3 Approximation Algorithms131

5.4 Breakpoints: A Different Face of Greed132

5.5 A Greedy Approach to Motif Finding136

5.6Notes137

Biobox: David Sankoff139

5.7 Problems143

6Dynamic Programming Algorithms147

6.1 The Power of DNA Sequence Comparison147

6.2 The Change Problem Revisited148

6.3 The Manhattan Tourist Problem153

6.4 Edit Distance and Alignments167

6.5 Longest Common Subsequences172

6.6 Global Sequence Alignment177

6.7 Scoring Alignments178

6.8 Local Sequence Alignment180

6.9 Alignment with Gap Penalties184

6.10 Multiple Alignment185

6.11 Gene Prediction193

6.12 Statistical Approaches to Gene Prediction197

6.13 Similarity-Based Approaches to Gene Prediction200

6.14 Spliced Alignment203

6.15 Notes207

Biobox: Michael Waterman209

6.16Problems211

7Divide-and-Conquer Algorithms227

7.1 Divide-and-Conquer Approach to Sorting227

7.2 Space-Efficient Sequence Alignment230

7.3 Block Alignment and the Four-Russians Speedup234

7.4 Constructing Alignments in Subquadratic Time238

7.5Notes240

Biobox: Webb Miller241

7.6 Problems244

8Graph Algorithms247

8.1 Graphs247

8.2 Graphs and Genetics260

8.3 DNA Sequencing262

8.4 Shortest Superstring Problem264

8.5 DNA Arrays as an Alternative Sequencing Technique265

8.6 Sequencing by Hybridization268

8.7 SBH as a Hamiltonian Path Problem271

8.8 SBH as an Eulerian Path Problem272

8.9 Fragment Assembly in DNA Sequencing275

8.10 Protein Sequencing and Identification280

8.11 The Peptide Sequencing Problem284

8.12 Spectrum Graphs287

8.13 Protein Identification via Database Search290

8.14 Spectral Convolution292

8.15 Spectral Alignment293

8.16 Notes299

8.17 Problems302

9Combinatorial Pattern Matching311

9.1 Repeat Finding311

9.2 Hash Tables313

9.3 Exact Pattern Matching316

9.4 Keyword Trees318

9.5 Suffix Trees320

9.6 Heuristic Similarity Search Algorithms324

9.7 Approximate Pattern Matching326

9.8 BLAST: Comparing a Sequence against a Database330

9.9Notes331

Biobox: Gene Myers333

9.10 Problems337

10 Clustering and Trees339

10.1Gene Expression Analysis339

10.2 Hierarchical Clustering343

10.3 k-Means Clustering346

10.4 Clustering and Corrupted Cliques348

10.5 Evolutionary Trees354

10.6 Distance-Based Tree Reconstruction358

10.7 Reconstructing Trees from Additive Matrices361

10.8 Evolutionary Trees and Hierarchical Clustering366

10.9 Character-Based Tree Reconstruction368

10.10 Small Parsimony Problem370

10.11 Large Parsimony Problem374

10.12 Notes379

Biobox: Ron Shamir380

10.13 Problems384

11 Hidden Markov Models387

11.1CC-Islands and the “Fair Bet Casino”387

11.2 The Fair Bet Casino and Hidden Markov Models390

11.3 Decoding Algorithm393

11.4 HMM Parameter Estimation397

11.5 Profile HMM Alignment398

11.6Notes400

Biobox: David Haussler403

11.7 Problems407

12 Randomized Algorithms409

12.1The Sorting Problem Revisited409

12.2 Gibbs Sampling412

12.3 Random Projections414

12.4 Notes416

12.5 Problems417

Using Bioinformatics Tools419

Bibliography421

Index428