Multiple Biological Sequence Alignment

Ken Nguyen, PhD, is an associate professor at Clayton State University, GA, USA. He received his PhD, MSc and BSc degrees in computer science all from Georgia State University. His research interests are in databases, parallel and distribute computing and bioinformatics. He was a Molecular Basis of Disease fellow at Georgia State and is the recipient of the highest graduate honor at Georgia State, the William M. Suttles Graduate Fellowship.Xuan Guo, PhD, is a postdoctoral associate at Oak Ridge National Lab, USA. He received his PhD degree in computer science from Georgia State University in 2015. His research interests are in bioinformatics, machine leaning, and cloud computing. He is an editorial assistant of International Journal of Bioinformatics Research and Applications.Yi Pan, PhD, is a Regents' Professor of Computer Science and an Interim Associate Dean and Chair of Biology at Georgia State University. He received his BE and ME in computer engineering from Tsinghua University in China and his PhD in computer science from the University of Pittsburgh. Dr. Pan's research interests include parallel and distributed computing, optical networks, wireless networks and bioinformatics. He has published more than 180 journal papers with about 60 papers published in various IEEE/ACM journals. He is co-editor along with Albert Y. Zomaya of the Wiley Series in Bioinformatics.

"Covers the full spectrum of the field, from alignment algorithms to scoring methods, practical techniques, and alignment tools and their evaluations." (Zentralblatt MATH, 2016)

• Preface xi1 Introduction 11.1 Motivation 21.2 The Organization of this Book 21.3 Sequence Fundamentals 31.3.1 Protein 51.3.2 DNA/RNA 61.3.3 Sequence Formats 61.3.4 Motifs 71.3.5 Sequence Databases 92 Protein/DNA/RNA Pairwise Sequence Alignment 112.1 Sequence Alignment Fundamentals 122.2 Dot-Plot Matrix 122.3 Dynamic Programming 142.3.1 Needleman–Wunsch’s Algorithm 152.3.2 Example 162.3.3 Smith–Waterman’s Algorithm 172.3.4 Affine Gap Penalty 192.4 Word Method 192.4.1 Example 202.5 Searching Sequence Databases 212.5.1 FASTA 212.5.2 BLAST 213 Quantifying Sequence Alignments 253.1 Evolution and Measuring Evolution 253.1.1 Jukes and Cantor’s Model 263.1.2 Measuring Relatedness 283.2 Substitution Matrices and Scoring Matrices 283.2.1 Identity Scores 283.2.2 Substitution/Mutation Scores 293.3 GAPS 323.3.1 Sequence Distances 353.3.2 Example 353.4 Scoring Multiple Sequence Alignments 363.4.1 Sum-of-Pair Score 363.5 Circular Sum Score 383.6 Conservation Score Schemes 393.6.1 Wu and Kabat’s Method 393.6.2 Jores’s Method 393.6.3 Lockless and Ranganathan’s Method 403.7 Diversity Scoring Schemes 403.7.1 Background 413.7.2 Methods 413.8 Stereochemical Property Methods 423.8.1 Valdar’s Method 433.9 Hierarchical Expected Matching Probability Scoring Metric (HEP) 443.9.1 Building an AACCH Scoring Tree 443.9.2 The Scoring Metric 463.9.3 Proof of Scoring Metric Correctness 473.9.4 Examples 483.9.5 Scoring Metric and Sequence Weighting Factor 493.9.6 Evaluation Data Sets 503.9.7 Evaluation Results 524 Sequence Clustering 594.1 Unweighted Pair Group Method with Arithmetic Mean – UPGMA 604.2 Neighborhood-Joining Method – NJ 614.3 Overlapping Sequence Clustering 655 Multiple Sequences Alignment Algorithms 695.1 Dynamic Programming 705.1.1 DCA 705.2 Progressive Alignment 715.2.1 Clustal Family 735.2.2 PIMA: Pattern-Induced Multisequence Alignment 735.2.3 PRIME: Profile-Based Randomized Iteration Method 745.2.4 DIAlign 755.3 Consistency and Probabilistic MSA 765.3.1 POA: Partial Order Graph Alignment 765.3.2 PSAlign 775.3.3 ProbCons: Probabilistic Consistency-Based Multiple Sequence Alignment 785.3.4 T-Coffee: Tree-Based Consistency Objective Function for Alignment Evaluation 795.3.5 MAFFT: MSA Based on Fast Fourier Transform 805.3.6 AVID 815.3.7 Eulerian Path MSA 815.4 Genetic Algorithms 825.4.1 SAGA: Sequence Alignment by Genetic Algorithm 835.4.2 GA and Self-Organizing Neural Networks 845.4.3 FAlign 855.5 New Development in Multiple Sequence Alignment Algorithms 855.5.1 KB-MSA: Knowledge-Based Multiple Sequence Alignment 855.5.2 PADT: Progressive Multiple Sequence Alignment Based on Dynamic Weighted Tree 945.6 Test Data and Alignment Methods 975.7 Results 985.7.1 Measuring Alignment Quality 985.7.2 RT-OSM Results 986 Phylogeny in Multiple Sequence Alignments 1036.1 The Tree of Life 1036.2 Phylogeny Construction 1056.2.1 Distance Methods 1066.2.2 Character-Based Methods 1076.2.3 Maximum Likelihood Methods 1096.2.4 Bootstrapping 1106.2.5 Subtree Pruning and Re-grafting 1116.3 Inferring Phylogeny from Multiple Sequence Alignments 1127 Multiple Sequence Alignment on High-Performance Computing Models 1137.1 Parallel Systems 1137.1.1 Multiprocessor 1137.1.2 Vector 1147.1.3 GPU 1147.1.4 FPGA 1147.1.5 Reconfigurable Mesh 1147.2 Exiting Parallel Multiple Sequence Alignment 1147.3 Reconfigurable-Mesh Computing Models – (R-Mesh) 1167.4 Pairwise Dynamic Programming Algorithms 1187.4.1 R-Mesh Max Switches 1187.4.2 R-Mesh Adder/Subtractor 1187.4.3 Constant-Time Dynamic Programming on R-Mesh 1207.4.4 Affine Gap Cost 1237.4.5 R-Mesh On/Off Switches 1247.4.6 Dynamic Programming Backtracking on R-Mesh 1257.5 Progressive Multiple Sequence Alignment ON R-Mesh 1267.5.1 Hierarchical Clustering on R-Mesh 1277.5.2 Constant Run-Time Sum-of-Pair Scoring Method 1287.5.3 Parallel Progressive MSA Algorithm and Its Complexity Analysis 1298 Sequence Analysis Services 1338.1 EMBL-EBI: European Bioinformatics Institute 1338.2 NCBI: National Center for Biotechnology Information 1358.3 GenomeNet and Data Bank of Japan 1368.4 Other Sequence Analysis and Alignment Web Servers 1378.5 SeqAna: Multiple Sequence Alignment with Quality Ranking 1388.6 Pairwise Sequence Alignment and Other Analysis Tools 1408.7 Tool Evaluation 1429 Multiple Sequence for Next-Generation Sequences 1459.1 Introduction 1459.2 Overview of Next Generation Sequence Alignment Algorithms 1479.2.1 Alignment Algorithms Based on Seeding and Hash Tables 1479.2.2 Alignment Algorithms Based on Suffix Tries 1519.3 Next-Generation Sequencing Tools 15410 Multiple Sequence Alignment for Variations Detection 16110.1 Introduction 16110.2 Genetic Variants 16310.3 Variation Detection Methods Based on MSA 16510.4 Evaluation Methodology 17210.4.1 Performance Metrics 17210.4.2 Simulated Sequence Data 17410.4.3 Real Sequence Data 17510.5 Conclusion and Future Work 17611 Multiple Sequence Alignment for Structure Detection 17911.1 Introduction 17911.2 RNA Secondary Structure Prediction Based on MSA 18011.2.1 Common Information in Multiple Aligned RNA Sequences 18211.2.2 Review of RNA SS Prediction Methods 18311.2.3 Measures of Quality of RNA SS Prediction 18711.3 Protein Secondary Structure Prediction Based on MSA 18911.3.1 Review of Protein Secondary Structure Prediction Methods 19011.3.2 Measures of Quality of Protein SS Prediction 19511.4 Conclusion and Future Work 196References 199Index 219