Bioinformatics by Sharma, Kal Renganathan -- Read -- Imperial Library of Trantor

Index

Cover Page Bioinformatics Copyright page Contents Preface Acknowledgments 1 Preliminaries

1.1 Molecular Biology 1.1.1 Amino Acids and Proteins 1.1.2 Structures of Proteins 1.1.3 Sequence Distribution of Insulin 1.1.4 Bioseparation Techniques 1.1.5 Nucleic Acids and Genetic Code 1.1.6 Genomes—Diversity, Size, and Structure 1.2 Probability and Statistics 1.2.1 Three Definitions of Probability 1.2.2 Bayes' Theorem and Conditional Probability 1.2.3 Independent Events and Bernoulli's Theorem 1.2.4 Discrete Probability Distributions 1.2.5 Continuous Probability Distributions 1.2.6 Statistical Inference and Hypothesis Testing 1.3 Which Is Larger, 2n or n2? 1.4 Big O Notation and Asymptotic Order of Functions Summary References and Sources Exercises

Part 1 Sequence Alignment and Representation

2 Alignment of a Pair of Sequences

Objectives 2.1 Introduction to Pairwise Sequence Alignment 2.2 Why Study Sequence Alignment 2.3 Alignment Grading Function 2.4 Optimal Global Alignment of a Pair of Sequences 2.4.1 Needleman and Wunsch Algorithm 2.5 Dynamic Programming 2.6 Time Analysis and Space Efficiency 2.7 Dynamic Arrays and O(N) Space 2.8 Subquadratic Algorithms for Longest Common Subsequence Problems 2.9 Optimal Local Alignment of a Pair of Sequences 2.9.1 Smith and Waterman Algorithm 2.10 Affine Gap Model 2.11 Greedy Algorithms for Pairwise Alignment 2.12 Other Alignment Methods 2.13 Pam and Blosum Matrices Summary References Further Reading Exercises

3 Sequence Representation and String Algorithms

Objectives 3.1 Suffix Trees 3.1.1 Overview of Suffix Trees in Sequence Analysis 3.2 Algorithm for Suffix Tree Representation of a Sequence 3.3 Streaming a Sequence Against a Suffix Tree 3.4 String Algorithms 3.4.1 Rabin-Karp Algorithm 3.4.2 Knuth-Morris-Pratt (KMP) Algorithm 3.4.3 Boyer-Moore Algorithm 3.4.4 Finite Automaton 3.5 Suffix Trees in String Algorithms 3.6 Look-up Tables Summary References Exercises

4 Multiple-Sequence Alignment

Objectives 4.1 What Is Multiple-Sequence Alignment? 4.2 Defenitions of Multiple Global Alignment and Sum of Pairs 4.2.1 Multiple Global Alignment 4.2.2 Sum of Pairs 4.3 Optimal MSA by Dynamic Programming 4.4 Theorem of Wang and Jiang [2] 4.5 What Are NP Complete Problems? 4.6 Center-Star-Alignment Algorithm [4] 4.6.1 Time Analysis 4.7 Progressive Alignment Methods 4.8 The Consensus Sequence 4.9 Greedy Method 4.10 Geometry of Multiple Sequences Summary References Exercises

Part 2 Probability Models

5 Hidden Markov Models and Applications

Objectives 5.1 Introduction 5.2 kth-order Markov Chain 5.3 DNA Sequence and Geometric Distribution [2–4] 5.4 Three Questions in the HMM 5.5 Evaluation Problem and Forward Algorithm 5.6 Decoding Problem and Viterbi Algorithm 5.7 Relative Entropy 5.8 Probabilistic Approach to Phylogeny 5.9 Sequence Alignment Using HMMs 5.10 Protein Families 5.11 Wheel HMMs to Model Periodicity in DNA 5.12 Generalized HMM (GHMM) 5.13 Database Mining 5.14 Multiple Alignments 5.15 Classification Using HMMs 5.16 Signal Peptide and Signal Anchor Prediction by HMMs 5.17 Markov Model and Chargaff's Parity Rules Summary References Exercises

6 Gene Finding, Protein Secondary Structure

Objectives 6.1 Introduction 6.2 Relative Entropy Site-Selection Problem 6.2.1 Greedy Approach 6.2.2 Gibbs Sampler 6.3 Maximum-Subsequence Problem 6.3.1 Bates and Constable Algorithm 6.3.2 Binomial Heap [4–7] 6.4 Interpolated Markov Model (IMM) 6.5 Shine Dalgarno SD Sites Finding 6.6 Gene Annotation Methods 6.7 Secondary Structures of Proteins 6.7.1 Neural Networks 6.7.2 PHD Architecture of Rost and Sander 6.7.3 Ensemble Method of Riis and Krogh [23] 6.7.4 Protein Secondary Structure Using HMMs 6.7.5 DAG RNNs: Directed Acyclic Graphs and Recursive NN Architecture and 3D Protein Structure Prediction 6.7.6 Annotate Subcellular Localization for Protein Structure Summary References Exercises

Part 3 Measurement Techniques

7 Biochips

Objectives 7.1 Introduction 7.1.1 Microarrays, Biochips, and Disease 7.1.2 Five Steps and Ten Tips 7.1.3 Applications of Microarrays 7.2 Microarray Detection 7.2.1 Fluorescence Detection and Optical Requirements 7.2.2 Confocal Scanning Microscope 7.3 Microarray Surfaces 7.4 Phosphoramadite Synthesis 7.5 Microarray Manufacture 7.6 Normalization for cDNA Microarray Data Summary References Exercises

8 Electrophoretic Techniques and Finite Speed of Diffusion

Objectives 8.1 Role of Electrophoresis in the Measurement of Sequence Distribution 8.2 Fick's Laws of Molecular Diffusion 8.3 Generalized Fick's Law of Diffusion 8.3.1 Derivation of a Generalized Fick's Law of Diffusion 8.3.2 Taitel Paradox and Final Time Condition 8.3.3 Relativistic Transformation of Coordinates 8.3.4 Periodic Boundary Condition 8.4 Electrophoresis Apparatus 8.5 Electrophoretic Term, Ballistic Term, and Fick Term in the Governing Equation Summary References Exercises

A Internet Hotlinks to Public-Domain Databases B PERL for Bioinformaticists Index