 |
Algorithms in bioinformatics : a practical introduction / Wing-Kin Sung. — Boca Raton : Chapman & Hall/CRC, c2010. – (58.17115/S958) |
Contents
CONTENTS
Preface
Introduction to Molecular Biology
1.1 DNA， RNA， and Protein
1.2 Genome， Chromosome and Gene
1.3 Replication and Mutation of DNA
1.4 Central Dogma (from DNA to Protein)
1.5 Post-Translation Modification (PTM)
1.6 Population Genetics
1.7 Basic Biotechnological Tools
1.8 Brief History of Bioinformatics
1.9 Exercises
2 Sequence Similarity
2.1 Introduction
2.2 Global Alignment Problem
2.3 Local Alignment
2.4 Semi-Global Alignment
2.5 Gap Penalty
2.6 Scoring Function
2.7 Exercises
3 Suffix Tree
3.1 Introduction
3.2 Suffix Tree
3.3 Simple Applications of a Suffix Tree
3.4 Construction of a Suffix Tree
3.5 Suffix Array
3.6 FM-Index
3.7 Approximate Searching Problem
3.8 Exercises
4 Genome Alignment
4.1 Introduction
4.2 Maximum unique match(MUM)
4.3 MUMmer1: LCS
4.4 MUMmer2 and MUMmer3
4.5 Mutation Sensitive Alignment
4.6 Dot Plot for Visualizing the Alignment
4.7 Further Reading
4.8 Exercises
5 Database Search
5.1 Introduction
5.2 Smith-Waterman Algorithm
5.3 Fast A
5.4 BLAST
5.5 Variations of the BLAST Algorithm
5.6 Q-gram Alignment based on Suffix Arrays (QUASAR)
5.7 Locality-Sensitive Hashing
5.8 BWT-SW
5.9 Are Existing Database Searching Methods Sensitive Enough?
5.10 Exercises
6 Multiple Sequence Alignment
6.1 Introduction 139
6.2 Formal Definition of the Multiple Sequence Alignment Problem 139
6.3 Methods for Solving the MSA Problem 141
6.4 Dynamic Programming Method 142
6.5 Center Star Method 143
6.6 Progressive Alignment Method 146
6.7 Iterative Method 149
6.8 Purther Reading 151
6.9 Exercises 152
7 Phylogeny Reconstruction
7.1 Introduction
7.2 Character-Based Phylogeny Reconstruction Algorithm
7.3 Distance-Based Phylogeny Reconstruction Algorithm 178
7.4 Bootstrapping 191
7.5 Can Tree Reconstruction Methods Infer the Correct Tree? 192
7.6 Exercises 193
8 Phylogeny Comparison
8.1 Introduction
8.2 Similarity Measurement
8.3 Dissimilarity Measurements
8.4 Consensus Tree Problem
8.5 Further Reading
8.6 Exercises
9 Genome Rearrangement
9.1 Introduction
9.2 Types of Genome Rearrangements
9.3 Computational Problems
9.4 Sorting an Unsigned Permutation by Reversals
9.5 Sorting a Signed Permutation by Reversals
9.6 Further Reading
9.7 Exercises
10 Motif Finding
10.1 Introduction
10.2 Identifying Binding Regions of TFs
10.3 Motif Model
10.4 The Motif Finding Problem
10.5 Scanning for Known Motifs
10.6 Statistical Approaches
10.7 Combinatorial Approaches
10.8 Scoring Function
10.9 Motif Ensemble Methods
10.10 Can Motif Finders Discover the Correct Motifs? 271
10.11 Motif Finding Utilizing Additional Information 274
10.12 Exercises
11 RNA Secondary Structure Prediction 281
11.1 Introduction 281
11.2 Obtaining RNA Secondary Structure Experimentally 285
11.3 RNA Structure Prediction Based on Sequence Only 286
11.4 Structure Prediction with the Assumption That There is No Pseudoknot
11.5 Nussinov Folding Algorithm
11.6 ZUKER Algorithm
11.7 Structure Prediction with Pseudoknots
11.8 Exercises
12 Peptide Sequencing
12.1 Introduction
12.2 Obtaining the Mass Spectrum of a Peptide
12.3 Modeling the Mass Spectrum of a Fragmented Peptide
12.4 De Novo Peptide Sequencing Using Dynamic Programming
12.5 De Novo Sequencing Using Graph-Based Approach 317
12.6 Peptide Sequencing via Database Search 319
12.7 Further Reading
12.8 Exercises
13 Population Genetics
13.1 Introduction
13.2 Hardy-Weinberg Equilibrium
13.3 Linkage Disequilibrium
13.4 Genotype Phasing
13.5 Tag SNP Selection
13.6 Association Study
13.7 Exercises
References
Index
