Algorithms in bioinformatics: a practical introduction

Preface

1. Introduction to Molecular Biology

1.1. DNA, RNA, and Protein

1.1.1. Proteins

1.1.2. DNA

1.1.3. RNA

1.2. Genome, Chromosome, and Gene

1.2.1. Genome

1.2.2. Chromosome

1.2.3. Gene

1.2.4. Complexity of the Organism versus Genome Size

1.2.5. Number of Genes versus Genome Size

1.3. Replication and Mutation of DNA

1.4. Central Dogma (from DNA to Protein)

1.4.1. Transcription (Prokaryotes)

1.4.3. Transcription (Eukaryote)

1.4.3. Translation

1.5. Post-Translation Modification (PTM)

1.6. Population Genetics

1.7. Basic Biotechnological Tools

1.7.1. Restriction Enzymes

1.7.2. Sonication

1.7.3. Cloning

1.7.4. PCR

1.7.5. Gel Electrophoresis

1.7.6. Hybridization

1.7.7. Next Generation DNA Sequencing

1.8. Brief History of Bioinformatics

1.9. Exercises

2. Sequence Similarity

2.2. Introduction

2.2. Global Alignment Problem

2.2.1. Needleman-Wunsch Algorithm

2.2.2. Running Time Issue

2.2.3. Space Efficiency Issue

2.2.4. More on Global Alignment

2.3. Local Alignment

2.4. Semi-Global Alignment

2.5. Gap Penalty

2.5.1. General Gap Penalty Model

2.5.2. Affine Gap Penalty Model

2.5.3. Convex Gap Model

2.6. Scoring Function

2.6.1. Scoring Function for DNA

2.6.2. Scoring Function for Protein

2.7. Exercises

3. Suffix Tree

3.1. Introduction

3.2. Suffix Tree

3.3. Simple Applications of a Suffix Tree

3.3.1. Exact String Matching Problem

3.3.2. Longest Repeated Substring Problem

3.3.3. Longest Common Substring Problem

3.3.4. Longest Common Prefix (LCP)

3.3.5. Finding a Palindrome

3.3.6. Extracting the Embedded Suffix Tree of a String from the Generalized Suffix Tree

3.3.7. Common Substring of 2 or More Strings

3.4. Construction of a Suffix Tree

3.4.1. Step 1: Construct the Odd Suffix Tree

3.4.2. Step 2: Construct the Even Suffix Tree

3.4.3. Step 3: Merge the Odd and the Even Suffix Trees

3.5. Suffix Array

3.5.1. Construction of a Suffix Array

3.5.2. Exact String Matching Using a Suffix Array

3.6. FM-Index

3.6.1. Definition

3.6.2. The occ Data Structure

3.6.3. Exact String Matching Using the FM-Index

3.7. Approximate Searching Problem

3.8. Exercises

4. Genome Alignment

4.1. Introduction

4.2. Maximum Unique Match (MUM)

4.2.1. How to Find MUMs

4.3. MUMmer1: LCS

4.3.1. Dynamic Programming Algorithm in 0(n 2 ) Time

4.3.2. An O (n log n)-Time Algorithm

4.4. MUMmer2 and MUMmer3

4.4.1. Reducing Memory Usage

4.4.2. Employing a New Alternative Algorithm for Finding MUMs

4.4.3. Clustering Matches

4.4.4. Extension of the Definition of MUM

4.5. Mutation Sensitive Alignment

4.5.1. Concepts and Definitions

4.5.2. The Idea of the Heuristic Algorithm

4.5.3. Experimental Results

4.6. Dot Plot for Visualizing the Alignment

4.7. Further Reading

4.8. Exercises

5. Database Search

5.1. Introduction

5.1.1. Biological Database

5.1.2. Database Searching

5.1.3. Types of Algorithms

5.2. Smith-Waterman Algorithm

5.3. FastA

5.3.1. FastP Algorithm

5.3.2. FastA Algorithm

5.4. Blast

5.4.1. Blast1

5.4.2. Blast2

5.4.3. Blast1 versus Blast2

5.4.4. Blast versus FastA

5.4.5. Statistics for Local Alignment

5.5. Variations of the Blast Algorithm

5.5.1. MegaBlast

5.5.2. Blat

5.5.3. PatternHunter

5.5.4. PSI-Blast (Position-Specific Iterated Blast)

5.6. Q-gram Alignment based on Suffix A Rrays (QUASAR)

5.6.1. Algorithm

5.6.2. Speeding Up and Reducing the Space for QUASAR

5.6.3. Time Analysis

5.7. Locality-Sensitive Hashing

5.8. BWT-SW

5.8.1. Aligning Query Sequence to Suffix Tree

5.8.2. Meaningful Alignment

5.9. Are Existing Database Searching Methods Sensitive Enough?

5.10. Exercises

6. Multiple Sequence Alignment

6.1. Introduction

6.2. Formal Definition of the Multiple Sequence Alignment Problem

6.3. Methods for Solving the MSA Problem

6.4. Dynamic Programming Method

6.5. Center Star Method

6.6. Progressive Alignment Method

6.6.1. ClustalW

6.6.2. Profile-Profile Alignment

6.6.3. Limitation of Progressive Alignment Construction

6.7. Iterative Method

6.7.1. Muscle

6.7.2. Log-Expectation (LE) Score

6.8. Further Reading

6.9. Exercises

7. Phylogeny Reconstruction

7.1. Introduction

7.1.1. Mitochondrial DNA and Inheritance

7.1.2. The Constant Molecular Clock

7.1.3. Phylogeny

7.1.4. Applications of Phylogeny

7.1.5. Phylogenetic Tree Reconstruction

7.2. Character-Based Phylogeny Reconstruction Algorithm

7.2.1. Maximum Parsimony

7.2.2. Compatibility

7.2.3. Maximum Likelihood Problem

7.3. Distance-Based Phylogeny Reconstruction Algorithm

7.3.1. Additive Metric and Ultrametric

7.3.2. Unweighted Pan Group Method with Arithmetic Mean (UPGMA)

7.3.3. Additive Tree Reconstruction

7.3.4. Nearly Additive Tree Reconstruction

7.3.5. Can We Apply Distance-Based Methods Given a Character-State Matrix?

7.4. Bootstrapping

7.5. Can Tree Reconstruction Methods Infer the Correct Tree?

7.6. Exercises

8. Phylogeny Comparison

8.1. Introduction

8.2. Similarity Measurement

8.2.1. Computing MAST by Dynamic Programming

8.2.2. MAST for Unrooted Trees

8.3. Dissimilarity Measurements

8.3.1. Robinson-Foulds Distance

8.3.2. Nearest Neighbor Interchange Distance (NNI)

8.3.3. Subtree Transfer Distance (STT)

8.3.4. Quartet Distance

8.4. Consensus Tree Problem

8.4.1. Strict Consensus Tree

8.4.2. Majority Rule Consensus Tree

8.4.3. Median Consensus Tree

8.4.4. Greedy Consensus Tree

8.4.5. R* Tree

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.4.1. Upper and Lower Bound on an Unsigned Reversal Distance

9.4.2. 4-Approximation Algorithm for Sorting an Unsigned Permutation

9.4.3. 2-Approximation Algorithm for Sorting an Unsigned Permutation

9.5. Sorting a Signed Permutation by Reversals

9.5.1. Upper Bound on Signed Reversal Distance

9.5.2. Elementary Intervals, Cycles, and Components

9.5.3. The Hannenhalli-Pevzner Theorem

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.6.1. Gibbs Motif Sampler

10.6.2. MEME

10.7. Combinatorial Approaches

10.7.1. Exhaustive Pattern-Driven Algorithm

10.7.2. Sample-Driven Approach

10.7.3. Suffix Tree-Based Algorithm

10.7.4. Graph-Based Method

10.8. Scoring Function

10.9. Motif Ensemble Methods

10.9.1. Approach of MotifVoter

10.9.2. Motif Filtering by the Discriminative and Consensus Criteria

10.9.3. Sites Extraction and Motif Generation

10.10. Can Motif Finders Discover the Correct Motifs?

10.11. Motif Finding Utilizing Additional Information

10.11.1. Regulatory Element Detection Using Correlation with Expression

10.11.2. Discovery of Regulatory Elements by Phylogenetic Footprinting

10.12. Exercises

11. RNA Secondary Structure Prediction

11.1. Introduction

11.1.1. Base Interactions in RNA

11.1.2. RNA Structures

11.2. Obtaining RNA Secondary Structure Experimentally

11.3. RNA Structure Prediction Based on Sequence Only

11.4. Structure Prediction with the Assumption That There is No Pseudoknot

11.5. Nussinov Folding Algorithm

11.6. ZUKER Algorithm

11.6.1. Time Analysis

11.6.2. Speeding up Multi-Loops

11.6.3. Speeding up Internal Loops

11.7. Structure Prediction with Pseudoknots

11.7.1. Definition of a Simple Pseudoknot

11.7.2. Akutsu's Algorithm for Predicting an RNA Secondary Structure with Simple 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.3.1. Amino Acid Residue Mass

12.3.2. Fragment Ion Mass

12.4. De Novo Peptide Sequencing Using Dynamic Programming

12.4.1. Scoring by Considering y-Ions

12.4.2. Scoring by Considering y-Ions and b-Ions

12.5. De Novo Sequencing Using Graph-Based Approach

12.6. Peptide Sequencing via Database Search

12.7. Further Reading

12.8. Exercises

13. Population Genetics

13.1. Introduction

13.1.1. Locus, Genotype, Allele, and SNP

13.1.2. Genotype Frequency and Allele Frequency

13.1.3. Haplotype and Phenotype

13.1.4. Technologies for Studying the Human Population .

13.1.5. Bioinformatics Problems

13.2. Hardy-Weinberg Equilibrium

13.3. Linkage Disequilibrium

13.3.1. D and D'

13.3.2. r 2

13.4. Genotype Phasing

13.4.1. Clark's Algorithm

13.4.2. Perfect Phylogeny Haplotyping Problem

13.4.3. Maximum Likelihood Approach

13.4.4. Phase Algorithm

13.5. Tag SNP Selection

13.5.1. Zhang et al's Algorithm

13.5.2. IdSelect

13.6. Association Study

13.6.1. Categorical Data Analysis

13.6.2. Relative Risk and Odds Ratio

13.6.3. Linear Regression

13.6.4. Logistic Regression

13.7. Exercises

References

Index