Editing Distance matrix (section)

==== Multiple sequence alignment ====
[[Multiple sequence alignment]] is an extension of pairwise alignment to align several sequences at a time. Different MSA methods are based on the same idea of the distance matrix as global and local alignments.

* Center star method. This method defines a center sequence {{Math|''S''<sub>c</sub>}} which minimizes the distance between the sequence {{Math|''S''<sub>c</sub>}} and any other sequence {{Math|''S''<sub>i</sub>}}. Then it generates a multiple alignment {{Math|M}} for the set of sequences {{Math|''S''}} so that for every {{Math|''S''<sub>i</sub>}} the alignment distance {{Math|''d''<sub>''M''</sub>(''S''<sub>c</sub>,''S''<sub>i</sub>)}} is the optimal pairwise alignment. This method has the characteristic that the computed alignment for {{Math|''S''}} whose sum-of-pair distance is at most twice the optimal multiple alignment.
* Progressive alignment method. This heuristic method to create MSA first aligns the two most related sequences, and then it progressively aligns the next two most related sequences until all sequences are aligned.

There are other methods that have their own program due to their popularity:

* [[Clustal|ClustalW]]
* [[MUSCLE (alignment software)|MUSCLE]]
* [[MAFFT]]
* MANGO
* And many more

===== MAFFT =====
Multiple alignment using fast Fourier transform (MAFFT) is a program with an algorithm based on progressive alignment, and it offers various multiple alignment strategies. First, MAFFT constructs a distance matrix based on the number of shared 6-tuples. Second, it builds the guide tree based on the previous matrix. Third, it clusters the sequences with the help of the [[fast Fourier transform]] and starts the alignment. Based on the new alignment, it reconstructs the guide tree and align again.