Preface
Contents
Part I: Background
1: Multiple Sequence Assignments: An Introduction
1.1 Introduction
1.2 Areas of Application of MSAs
1.2.1 Preserved Sequence Sections: Motifs and Domains
1.2.2 Prediction of Function and Structure
1.2.3 Phylogeny
1.2.4 MSAs as Everyday Tools
1.3 Representation Formats of MSAs
1.3.1 FASTA
1.3.2 Clustal
1.3.3 MSF
1.3.4 PHYLIP
1.3.5 NEXUS
1.3.6 Tree Formats
1.3.7 Graphical Visualizations
2: How Do MSA Programs Work?
2.1 Introduction
2.2 Pairwise Sequence Alignments
2.2.1 A Naive Method
2.2.2 Dynamic Programming
The Two Phases of the Algorithm
Phase 1: Filling the Matrix
Phase 2: Generation of the Alignment
2.2.3 Gaps and the Similarity Matrix
Gap Penalties
Substitution Matrices
The BLOSUM Matrix
The PAM Matrix
The EDNAFULL Matrix
2.2.4 Global and Local Alignments
The Smith-Waterman Algorithm
2.3 Multiple Sequence Alignments
2.3.1 The Central Problem
2.3.2 Solution 1: The Progressive Method
Generation of the Guide Tree
Generation of the MSA
Problems of the Progressive Method
2.3.3 Solution 2: The Iterative Method
2.3.4 Solution 3: The Consistency-Based Method
2.3.5 Solution 4: The Probabilistic Method
2.3.6 Solution 5: The Meta or Ensemble Method
2.3.7 Methods of the Future
2.3.8 Special Cases Require Special Methods
The Normal Case
Transmembrane Proteins
Proteins with Highly Conserved Domains
Non-coding RNA
The Twilight Zone
2.4 Further Topics
2.4.1 Structure-Based MSAs
2.4.2 BLAST and Co.
2.4.3 Alignment-Free Methods
2.4.4 Genome and Chromosome Alignments
3: Overview of Current MSA Programs
3.1 Introduction
3.2 List of Common MSA Programs
3.2.1 DFalign
3.2.2 Clustal
3.2.3 ClustalW
3.2.4 SAGA
3.2.5 PRRP
3.2.6 DIALIGN
3.2.7 DIALIGN2
3.2.8 T-Coffee
3.2.9 MAFFT
3.2.10 POA
3.2.11 PRALINE
3.2.12 Align-M
3.2.13 MUSCLE
3.2.14 3D-Coffee
3.2.15 Kalign
3.2.16 DIALIGN-T
3.2.17 ProbCons
3.2.18 M-Coffee
3.2.19 R-Coffee and RM-Coffee
3.2.20 DIALIGN-TX
3.2.21 PRALINE
3.2.22 PRANK
3.2.23 PSI-Coffee and TM-Coffee
3.2.24 MSAProbs
3.2.25 PicXAA
3.2.26 AlignMe
3.2.27 Clustal Omega
3.2.28 ReformAlign
3.2.29 DECIPHER
Part II: Which Program Fits My Data?
4: Details of the Analysis
4.1 Benchmarking
4.1.1 A Marathon for MSA Programs
4.1.2 The Crux of MSA Benchmarking
4.2 Benchmark Datasets Used (Table 4.1)
4.2.1 BAliBASE
Reference Set 1: Evolutionary Distances
Reference Sets 2 and 3: Orphans and Families
Reference Sets 4 and 5: Insertions and Extensions
Reference Sets 6, 7 and 8: Transmembrane Proteins, Repeats and Inversions
Reference Set 9: Motifs in Longer Sequences
Reference Set 10: Complicated Datasets
Evaluation
4.2.2 BRAliBASE
4.2.3 Bench
Oxbench
PREFAB
SABmark or SABRE
BAliBASE
4.2.4 Artificial Benchmarks: Rose, IRMBASE and DIRMBASE
4.2.5 HOMSTRAD
4.3 Scores
4.3.1 Sum-of-Pairs
4.3.2 The Column Score
4.3.3 Modeler Score
4.3.4 ClineΒ΄s Shift Score
4.3.5 Transitive Consistency Score
5: Decision Aid
5.1 Introduction
5.2 Implementation
5.3 Results
5.3.1 RNA
5.3.2 DNA
5.3.3 Proteins
Glossary
Literature
Index