Kazutaka Katoh - Multiple Sequence Alignment: Methods and Protocols

This volume is a collection of protocols to install and run tools for calculation and visualization of multiple sequence alignment (MSA) and other analyses related to MSA. Following the policy of Methods in Molecular Biology, each chapter basically consists of a brief background and a step-by-step guide for installation and actual analyses. Practical advice is also given in the Notes section in most chapters. The main target audience is experimental biologists who want to run MSA tools themselves. By reading a chapter in this volume, a reader should easily acquire basic usage of the associated tool. Detailed background and advanced usage are described in papers and/or webpages mentioned in each chapter.

To provide background for these chapters, this section explains some technical terms and established techniques that are commonly used.

Sequence alignment is an estimation of corresponding sites in a set of biological sequences. The correspondence is, in many cases, based on homology, i.e., shared ancestry in evolutionary history of the sequences compared. Alignment of just two sequences is called pairwise sequence alignment, and alignment of three or more sequences is called multiple sequence alignment, MSA, the theme of this volume. There is a long history of the study of sequence alignment methods, starting from the first application of the dynamic programming (DP) algorithm to pairwise alignment by Needleman and Wunsch [1]. This method gives the optimum pairwise alignment under a reasonable scoring system. It is theoretically possible to extend the DP algorithm to three or more sequences, if the score is derived as the summation of pairwise alignment scores. However, this calculation requires unpractical computational resources. In addition, for a real MSA, it is also usually necessary to consider the relationships between sequences in order to reflect their evolutionary history. Thus, the simple extension of the DP algorithm for MSA is rarely used. Instead, various heuristics are used. Representative heuristic techniques are outlined below.

A reasonable and widely used heuristic is the progressive method [24]. In this strategy, a tentative tree, called a guide tree, is built based on an all-to-all approximate comparison. Then, the sequences are aligned from the leaves to the root on the tree, in a group-to-group manner. When the calculation reaches the root, the full MSA is obtained. Many MSA programs use the progressive method as a part of the calculation. Among them, PRANK (Chapter ) has a notable point that it rigorously considers insertions and deletions on the guide tree.

The progressive method has a well-known problem that errors can occur in early steps (i.e., close to a leaf) of the guide tree, and those errors remain in the final step (the root of the guide tree). One effective solution is to correct this type of mistake is iterative refinement [57]. The procedure is: (i) construct an initial MSA; (ii) divide the MSA into two groups; (iii) re-align the two groups; repeat (ii) and (iii). This technique is used in Prrn5 (Chapter ).