Multiple sequence alignment

The purpose of multiple sequence alignment is to match up a number of related biological sequences against one another as well as possible, so that in each position in the resulting alignment, all residues have the same biological role in the original sequences. This is done by moving and stretching the sequences with respect to one another, eventually finding the optimal fit. This is essentially a multidimensional optimisation problem with a large solution space, so clever heuristics are needed in order to make the problem tractable. Many algorithms have been proposed for solving this with maximal efficiency, and there is often a tradeoff between quality on one hand, and speed and slim resource requirements on the other.

Examples include:

• ClustalW
• mafft
• Muscle
• T-Coffee