Covers the fundamentals and techniques of multiple biological sequence alignment and analysis, and shows readers how to choose the appropriate sequence analysis tools for their tasks This book describes the traditional and modern approaches in biological sequence alignment and homology search. This book contains 11 chapters, with Chapter 1 providing basic information on biological sequences. Next, Chapter 2 contains fundamentals in pair-wise sequence alignment, while Chapters 3 and 4 examine popular existing quantitative models and practical clustering techniques that have been used in multiple sequence alignment. Chapter 5 describes, characterizes and relates many multiple sequence alignment models. Chapter 6 describes how traditionally phylogenetic trees have been constructed, and available sequence knowledge bases can be used to improve the accuracy of reconstructing phylogeny trees. Chapter 7 covers the latest methods developed to improve the run-time efficiency of multiple sequence alignment. Next, Chapter 8 covers several popular existing multiple sequence alignment server and services, and Chapter 9 examines several multiple sequence alignment techniques that have been developed to handle short sequences (reads) produced by the Next Generation Sequencing technique (NSG). Chapter 10 describes a Bioinformatics application using multiple sequence alignment of short reads or whole genomes as input. Lastly, Chapter 11 provides a review of RNA and protein secondary structure prediction using the evolution information inferred from multiple sequence alignments. * Covers the full spectrum of the field, from alignment algorithms to scoring methods, practical techniques, and alignment tools and their evaluations * Describes theories and developments of scoring functions and scoring matrices *Examines phylogeny estimation and large-scale homology search Multiple Biological Sequence Alignment: Scoring Functions, Algorithms and Applications is a reference for researchers, engineers, graduate and post-graduate students in bioinformatics, and system biology and molecular biologists. 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.
Autorentext
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.
Inhalt
Preface xi
1 Introduction 1
1.1 Motivation 2
1.2 The Organization of this Book 2
1.3 Sequence Fundamentals 3
1.3.1 Protein 5
1.3.2 DNA/RNA 6
1.3.3 Sequence Formats 6
1.3.4 Motifs 7
1.3.5 Sequence Databases 9
2 Protein/DNA/RNA Pairwise Sequence Alignment 11
2.1 Sequence Alignment Fundamentals 12
2.2 Dot-Plot Matrix 12
2.3 Dynamic Programming 14
2.3.1 NeedlemanWunsch's Algorithm 15
2.3.2 Example 16
2.3.3 SmithWaterman's Algorithm 17
2.3.4 Affine Gap Penalty 19
2.4 Word Method 19
2.4.1 Example 20
2.5 Searching Sequence Databases 21
2.5.1 FASTA 21
2.5.2 BLAST 21
3 Quantifying Sequence Alignments 25
3.1 Evolution and Measuring Evolution 25
3.1.1 Jukes and Cantor's Model 26
3.1.2 Measuring Relatedness 28
3.2 Substitution Matrices and Scoring Matrices 28
3.2.1 Identity Scores 28
3.2.2 Substitution/Mutation Scores 29
3.3 GAPS 32
3.3.1 Sequence Distances 35
3.3.2 Example 35
3.4 Scoring Multiple Sequence Alignments 36
3.4.1 Sum-of-Pair Score 36
3.5 Circular Sum Score 38
3.6 Conservation Score Schemes 39
3.6.1 Wu and Kabat's Method 39
3.6.2 Jores's Method 39
3.6.3 Lockless and Ranganathan's Method 40
3.7 Diversity Scoring Schemes 40
3.7.1 Background 41
3.7.2 Methods 41
3.8 Stereochemical Property Methods 42
3.8.1 Valdar's Method 43
3.9 Hierarchical Expected Matching Probability Scoring Metric (HEP) 44
3.9.1 Building an AACCH Scoring Tree 44
3.9.2 The Scoring Metric 46
3.9.3 Proof of Scoring Metric Correctness 47
3.9.4 Examples 48
3.9.5 Scoring Metric and Sequence Weighting Factor 49
3.9.6 Evaluation Data Sets 50
3.9.7 Evaluation Results 52
4 Sequence Clustering 59
4.1 Unweighted Pair Group Method with Arithmetic Mean UPGMA 60
4.2 Neighborhood-Joining Method NJ 61
4.3 Overlapping Sequence Clustering 65
5 Multiple Sequences Alignment Algorithms 69
5.1 Dynamic Programming 70
5.1.1 DCA 70
5.2 Progressive Alignment 71
5.2.1 Clustal Family 73
5.2.2 PIMA: Pattern-Induced Multisequence Alignment 73
5.2.3 PRIME: Profile-Based Randomized Iteration Method 74
5.2.4 DIAlign 75
5.3 Consistency and Probabilistic MSA 76
5.3.1 POA: Partial Order Graph Alignment 76
5.3.2 PSAlign 77
5.3.3 ProbCons: Probabilistic Consistency-Based Multiple Sequence Alignment 78
5.3.4 T-Coffee: Tree-Based Consistency Objective Function for Alignment Evaluation 79
5.3.5 MAFFT: MSA Based on Fast Fourier Transform 80
5.3.6 AVID 81
5.3.7 Eulerian Path MSA 81
5.4 Genetic Algorithms 82
5.4.1 SAGA: Sequence Alignment by Genetic Algorith…