Bioinformatics : sequence alignment and Markov models

GET FULLY UP-TO-DATE ON BIOINFORMATICS-THE TECHNOLOGY OF THE 21ST CENTURY Bioinformatics showcases the latest developments in the field along with all the foundational information you'll need. It provides in-depth coverage of a wide range of autoimmune disorders and detailed analyses of suffix trees, plus late-breaking advances regarding biochips and genomes. Featuring helpful gene-finding algorithms, Bioinformatics offers key information on sequence alignment, HMMs, HMM applications, protein secondary structure, microarray techniques, and drug discovery and development. Helpful diagrams accompany mathematical equations throughout, and exercises appear at the end of each chapter to facilitate self-evaluation. This thorough, up-to-date resource features: Worked-out problems illustrating concepts and models End-of-chapter exercises for self-evaluation Material based on student feedback Illustrations that clarify difficult math problems A list of bioinformatics-related websites Bioinformatics covers: Sequence representation and alignment Hidden Markov models Applications of HMMs Gene finding Protein secondary structure prediction Microarray techniques Drug discovery and development Internet resources and public domain databases Contents......Page 7 Preface......Page 13 Acknowledgments......Page 17 1 Preliminaries......Page 19 1.1.1 Amino Acids and Proteins......Page 20 1.1.2 Structures of Proteins......Page 21 1.1.3 Sequence Distribution of Insulin......Page 24 1.1.4 Bioseparation Techniques......Page 27 1.1.5 Nucleic Acids and Genetic Code......Page 30 1.1.6 Genomes—Diversity, Size, and Structure......Page 38 1.2 Probability and Statistics......Page 41 1.2.1 Three Definitions of Probability......Page 42 1.2.3 Independent Events and Bernoulli’s Theorem......Page 43 1.2.4 Discrete Probability Distributions......Page 44 1.2.5 Continuous Probability Distributions......Page 46 1.2.6 Statistical Inference and Hypothesis Testing......Page 48 1.3 Which Is Larger, 2[sup(n)] or n[sup(2)]?......Page 49 1.4 Big O Notation and Asymptotic Order of Functions......Page 50 Summary......Page 51 References and Sources......Page 52 Exercises......Page 53 Part 1 Sequence Alignment and Representation......Page 57 2.1 Introduction to Pairwise Sequence Alignment......Page 59 2.2 Why Study Sequence Alignment......Page 61 2.3 Alignment Grading Function......Page 65 2.4 Optimal Global Alignment of a Pair of Sequences......Page 69 2.5 Dynamic Programming......Page 73 2.7 Dynamic Arrays and O(N) Space......Page 74 2.8 Subquadratic Algorithms for Longest Common Subsequence Problems......Page 75 2.9 Optimal Local Alignment of a Pair of Sequences......Page 77 2.10 Affine Gap Model......Page 78 2.11 Greedy Algorithms for Pairwise Alignment......Page 81 2.12 Other Alignment Methods......Page 83 2.13 Pam and Blosum Matrices......Page 84 Summary......Page 87 References......Page 88 Exercises......Page 89 3.1 Suffix Trees......Page 103 3.2 Algorithm for Suffix Tree Representation of a Sequence......Page 106 3.3 Streaming a Sequence Against a Suffix Tree......Page 107 3.4 String Algorithms......Page 109 3.5 Suffix Trees in String Algorithms......Page 115 3.6 Look-up Tables......Page 117 Summary......Page 118 References......Page 119 Exercises......Page 120 4.1 What Is Multiple-Sequence Alignment?......Page 133 4.3 Optimal MSA by Dynamic Programming......Page 135 4.5 What Are NP Complete Problems?......Page 136 4.6 Center-Star-Alignment Algorithm [4]......Page 137 4.7 Progressive Alignment Methods......Page 139 4.8 The Consensus Sequence......Page 140 4.10 Geometry of Multiple Sequences......Page 141 References......Page 143 Exercises......Page 144 Part 2 Probability Models......Page 149 5.1 Introduction......Page 151 5.2 kth-order Markov Chain......Page 152 5.3 DNA Sequence and Geometric Distribution [2–4]......Page 153 5.4 Three Questions in the HMM......Page 161 5.6 Decoding Problem and Viterbi Algorithm......Page 164 5.7 Relative Entropy......Page 165 5.8 Probabilistic Approach to Phylogeny......Page 167 5.9 Sequence Alignment Using HMMs......Page 170 5.10 Protein Families......Page 171 5.11 Wheel HMMs to Model Periodicity in DNA......Page 174 5.12 Generalized HMM (GHMM)......Page 175 5.14 Multiple Alignments......Page 178 5.15 Classification Using HMMs......Page 179 5.16 Signal Peptide and Signal Anchor Prediction by HMMs......Page 180 5.17 Markov Model and Chargaff's Parity Rules......Page 181 Summary......Page 182 References......Page 183 Exercises......Page 184 6.1 Introduction......Page 197 6.2 Relative Entropy Site-Selection Problem......Page 198 6.3 Maximum-Subsequence Problem......Page 200 6.4 Interpolated Markov Model (IMM)......Page 202 6.5 Shine Dalgarno SD Sites Finding......Page 203 6.6 Gene Annotation Methods......Page 205 6.7 Secondary Structures of Proteins......Page 209 Summary......Page 221 References......Page 222 Exercises......Page 224 Part 3 Measurement Techniques......Page 229 7.1 Introduction......Page 231 7.2 Microarray Detection......Page 241 7.3 Microarray Surfaces......Page 245 7.4 Phosphoramadite Synthesis......Page 249 7.5 Microarray Manufacture......Page 251 7.6 Normalization for cDNA Microarray Data......Page 254 Summary......Page 258 References......Page 259 Exercises......Page 260 8.1 Role of Electrophoresis in the Measurement of Sequence Distribution......Page 263 8.2 Fick’s Laws of Molecular Diffusion......Page 264 8.3 Generalized Fick’s Law of Diffusion......Page 267 8.4 Electrophoresis Apparatus......Page 287 8.5 Electrophoretic Term, Ballistic Term, and Fick Term in the Governing Equation......Page 288 Summary......Page 292 References......Page 293 Exercises......Page 294 A: Internet Hotlinks to Public-Domain Databases......Page 305 B: PERL for Bioinformaticists......Page 317 A......Page 321 B......Page 322 C......Page 323 D......Page 324 F......Page 325 G......Page 326 H......Page 327 J......Page 328 L......Page 329 M......Page 330 N......Page 331 P......Page 332 R......Page 334 S......Page 335 T......Page 337 Z......Page 338 Contents 7 Preface 13 Acknowledgments 17 1 Preliminaries 19 1.1 Molecular Biology 20 1.1.1 Amino Acids and Proteins 20 1.1.2 Structures of Proteins 21 1.1.3 Sequence Distribution of Insulin 24 1.1.4 Bioseparation Techniques 27 1.1.5 Nucleic Acids and Genetic Code 30 1.1.6 Genomes—Diversity, Size, and Structure 38 1.2 Probability and Statistics 41 1.2.1 Three Definitions of Probability 42 1.2.2 Bayes’ Theorem and Conditional Probability 43 1.2.3 Independent Events and Bernoulli’s Theorem 43 1.2.4 Discrete Probability Distributions 44 1.2.5 Continuous Probability Distributions 46 1.2.6 Statistical Inference and Hypothesis Testing 48 1.3 Which Is Larger, 2[sup(n)] or n[sup(2)]? 49 1.4 Big O Notation and Asymptotic Order of Functions 50 Summary 51 References and Sources 52 Exercises 53 Part 1 Sequence Alignment and Representation 57 2 Alignment of a Pair of Sequences 59 Objectives 59 2.1 Introduction to Pairwise Sequence Alignment 59 2.2 Why Study Sequence Alignment 61 2.3 Alignment Grading Function 65 2.4 Optimal Global Alignment of a Pair of Sequences 69 2.5 Dynamic Programming 73 2.6 Time Analysis and Space Efficiency 74 2.7 Dynamic Arrays and O(N) Space 74 2.8 Subquadratic Algorithms for Longest Common Subsequence Problems 75 2.9 Optimal Local Alignment of a Pair of Sequences 77 2.10 Affine Gap Model 78 2.11 Greedy Algorithms for Pairwise Alignment 81 2.12 Other Alignment Methods 83 2.13 Pam and Blosum Matrices 84 Summary 87 References 88 Further Reading 89 Exercises 89 3 Sequence Representation and String Algorithms 103 Objectives 103 3.1 Suffix Trees 103 3.2 Algorithm for Suffix Tree Representation of a Sequence 106 3.3 Streaming a Sequence Against a Suffix Tree 107 3.4 String Algorithms 109 3.5 Suffix Trees in String Algorithms 115 3.6 Look-up Tables 117 Summary 118 References 119 Exercises 120 4 Multiple-Sequence Alignment 133 Objectives 133 4.1 What Is Multiple-Sequence Alignment? 133 4.2 Defenitions of Multiple Global Alignment and Sum of Pairs 135 4.3 Optimal MSA by Dynamic Programming 135 4.4 Theorem of Wang and Jiang [2] 136 4.5 What Are NP Complete Problems? 136 4.6 Center-Star-Alignment Algorithm [4] 137 4.7 Progressive Alignment Methods 139 4.8 The Consensus Sequence 140 4.9 Greedy Method 141 4.10 Geometry of Multiple Sequences 141 Summary 143 References 143 Exercises 144 Part 2 Probability Models 149 5 Hidden Markov Models and Applications 151 Objectives 151 5.1 Introduction 151 5.2 kth-order Markov Chain 152 5.3 DNA Sequence and Geometric Distribution [2–4] 153 5.4 Three Questions in the HMM 161 5.5 Evaluation Problem and Forward Algorithm 164 5.6 Decoding Problem and Viterbi Algorithm 164 5.7 Relative Entropy 165 5.8 Probabilistic Approach to Phylogeny 167 5.9 Sequence Alignment Using HMMs 170 5.10 Protein Families 171 5.11 Wheel HMMs to Model Periodicity in DNA 174 5.12 Generalized HMM (GHMM) 175 5.13 Database Mining 178 5.14 Multiple Alignments 178 5.15 Classification Using HMMs 179 5.16 Signal Peptide and Signal Anchor Prediction by HMMs 180 5.17 Markov Model and Chargaff's Parity Rules 181 Summary 182 References 183 Exercises 184 6 Gene Finding, Protein Secondary Structure 197 Objectives 197 6.1 Introduction 197 6.2 Relative Entropy Site-Selection Problem 198 6.3 Maximum-Subsequence Problem 200 6.4 Interpolated Markov Model (IMM) 202 6.5 Shine Dalgarno SD Sites Finding 203 6.6 Gene Annotation Methods 205 6.7 Secondary Structures of Proteins 209 Summary 221 References 222 Exercises 224 Part 3 Measurement Techniques 229 7 Biochips 231 Objectives 231 7.1 Introduction 231 7.2 Microarray Detection 241 7.3 Microarray Surfaces 245 7.4 Phosphoramadite Synthesis 249 7.5 Microarray Manufacture 251 7.6 Normalization for cDNA Microarray Data 254 Summary 258 References 259 Exercises 260 8 Electrophoretic Techniques and Finite Speed of Diffusion 263 Objectives 263 8.1 Role of Electrophoresis in the Measurement of Sequence Distribution 263 8.2 Fick’s Laws of Molecular Diffusion 264 8.3 Generalized Fick’s Law of Diffusion 267 8.4 Electrophoresis Apparatus 287 8.5 Electrophoretic Term, Ballistic Term, and Fick Term in the Governing Equation 288 Summary 292 References 293 Exercises 294 A: Internet Hotlinks to Public-Domain Databases 305 B: PERL for Bioinformaticists 317 Index 321 A 321 B 322 C 323 D 324 E 325 F 325 G 326 H 327 I 328 J 328 K 329 L 329 M 330 N 331 O 332 P 332 Q 334 R 334 S 335 T 337 U 338 V 338 W 338 X 338 Y 338 Z 338 Publisher's Note: Products purchased from Third Party sellers are not guaranteed by the publisher for quality, authenticity, or access to any online entitlements included with the product. GET FULLY UP-TO-DATE ON BIOINFORMATICS-THE TECHNOLOGY OF THE 21ST CENTURY Bioinformatics showcases the latest developments in the field along with all the foundational information you'll need. It provides in-depth coverage of a wide range of autoimmune disorders and detailed analyses of suffix trees, plus late-breaking advances regarding biochips and genomes. Featuring helpful gene-finding algorithms, Bioinformatics offers key information on sequence alignment, HMMs, HMM applications, protein secondary structure, microarray techniques, and drug discovery and development. Helpful diagrams accompany mathematical equations throughout, and exercises appear at the end of each chapter to facilitate self-evaluation. This thorough, up-to-date resource features: Bioinformatics covers: "A state-of-the-art textbook on bioinformatics covering the latest 21st-century technology. An essential tool, this book explores the cutting-edge methods of bioinformatics, presenting a wide range of diagrams, mathematical equations, worked examples, and exercises to illustrate the concepts and models. Bioinformatics discusses auto-immune disorders and enumerates the motivation for sequence alignment. The text provides gene-finding algorithms and introduces binomial heap for the maximum increasing subsequence problem. There is also a wealth of information on suffix trees ... HMM ... HMM applications ... protein secondary structure ... microarray techniques ... drug discovery and development ... and advances in biochip and genome completions and sequence alignment. In addition, this valuable resource includes a listing of Internet sites in bioinformatics, which contain constantly updated information on this fast-changing field." "Bioinformatics offers in-depth coverage of a wide range of autoimmune disorders, detailed analyses of suffix trees, and the latest biochip and genome advances." "Featuring helpful gene-finding algorithms, Bioinformatics offers key information on sequence alignment, HMMs, HMM applications, protein secondary structure, microarray techniques, and drug discovery and development. Diagrams accompany mathematical equations throughout, and exercises appear at the end of each chapter to facilitate self-evaluation."--Jacket