In bioinformatics, MAFFT (for multiple alignment using fast Fourier transform) is a program used to create multiple sequence alignments of amino acid or nucleotide sequences. Published in 2002, the first version of MAFFT used an algorithm based on progressive alignment, in which the sequences were clustered with the help of the fast Fourier transform.^[2] Subsequent versions of MAFFT have added other algorithms and modes of operation,^[3] including options for faster alignment of large numbers of sequences,^[4] higher accuracy alignments,^[5] alignment of non-coding RNA sequences,^[6] and the addition of new sequences to existing alignments.^[7]

History

There have been many variations of the MAFFT software, some of which are listed below:

• MAFFT: The first version of MAFFT, created by Kazutaka Katoh in 2002, used an algorithm based on progressive alignment, in which the sequences were clustered with the help of the fast Fourier transform.^[2]
• MAFFT v5: The second generation of the MAFFT software was released in 2005 and was a rewrite of the original MAFFT software.^[3] This generation introduced a simplified scoring system that performs well for reducing CPU time and increasing the accuracy of alignments even for sequences having large insertions or extensions as well as distantly related sequences of similar length.^[2]
• MAFFT v6: The third generation, released in 2006, again improved upon the previous versions.^[3] It implemented group-to-group alignment, guide trees which had an approximate but faster O(N log N) tree-building algorithm, as well as making the version applicable to larger datasets with ~50,000 sequences.
• MAFFT v7: The fourth generation, released in 2012, improved the speed and accuracy of MAFFT substantially.^[3]
• MAFFT v7.511: The most recent version of MAFFT, released in December of 2022, improved upon MAFFT v7 with various bug fixes. One of the most notable being an overhaul to the --merge option, which now includes, enabling iterative refinement, creating a single MSA from multiple sub-MSAs, as well as the combination of --merge and --seed. There were also several minor enhancements to the speed and accuracy of MAFFT v7.

Algorithm

The MAFFT algorithm works following these 5 steps Pairwise Alignment, Distance Calculation, Guide Tree Construction, Progressive Alignment, Iterative Refinement.^[8]

• Pairwise Alignment: This step is used to identify the regions that are similar between the sequences inputted. The algorithm starts by using the inputted sequences executing pairwise alignments across all the sequences. This step's time complexity is O(L^2) where L is the sequence.^[9]

• Distance Matrix: Using the calculated pairwise alignments, a distance matrix calculation is done to evaluate the dissimilarity between the alignments based on their alignment scores.^[9] The distance calculation step helps organize the sequences based on their similarity. The Distance Matrix's time complexity is O(N^2L^2)^[9] where N is the number of sequences and L is the length of the sequence. This time complexity is due to the fact that the distance calculation between pairs of sequences requires comparing every position of each sequence.

• Guide Tree: Using the distance matrix a guide tree is constructed where there is a hierarchical representation of the clusters (each node is a cluster) and the branches included are the distance between the clusters. O(N^2L)^[10] is the time complexity for the guide tree construction, where N is the number of sequences.

• Progressive Alignment: Using the guide tree progressive alignment^[9] is performed from the leaves to the root. The algorithm uses the inputted sequences and aligns the child nodes to calculate a consensus alignment for the parent node. This step is done until the entire tree is traversed to result a final multiple sequence alignment. The progressive alignment method's time complexity is O(N^2L) + O(NL^2).^[10] This is because the first term corresponds to the guide tree calculation stated earlier along with the second term that corresponds to group to group alignment.

• Iterative Alignment: The iterative refinement step repeats the entire process with adjustments to the positions of gaps and insertions to improve the alignment accuracy.^[9] The time complexity of the iterative alignment depends on the number of iterations that occur. But generally the time complexity of this method is O(N2L) + O(NL2)^[10] where N is the number of sequences, and L is the length of the sequence.

Input/Output

Web Form  

Input

This program can take in multiple sequences as input, which can be entered in two ways:

Sequence Input Window  

The user can directly enter three or more sequences in the input window in any of the following formats: GCG, FASTA, EMBL (nucleotide only), GenBank, PIR, NBRF, PHYLIP, or UniProtKB/Swiss-Prot (protein only). It is important to note that partially formatted sequences are not accepted, and adding a return to the end of the sequence may help certain applications understand the input. It is also advised to avoid using data from word processors as hidden/control characters may be present.^[11]

Sequence File Upload  

The user can upload a file containing three or more valid sequences in any format mentioned above. Word processor files may yield unpredictable results due to the presence of hidden/control characters, so it is best to save files with the Unix format option to avoid hidden Windows characters. Once the file is uploaded, it can be used as input for multiple sequence alignment.^[11]

Text files saved on DOS/Windows format have different line endings than those saved on Unix/Linux. DOS/Windows uses a combination of carriage return and line feed characters ("\r\n") to indicate the end of a line, while Unix/Linux systems use only a line feed character ("\n").^[12]

When transferring files between Windows and Unix-based systems, it's important to be aware of these differences to ensure that the line endings are correctly translated. Otherwise, the hidden carriage return characters in the Windows-formatted files may cause issues when viewed or edited on Unix-based systems, and vice versa.^[12]

Output

The user will have the option to request the Multiple Sequence Alignment (MSA) to be generated in one of the two available formats:

Default value is: Pearson/FASTA [fasta]

Settings

There are many settings that affect how the MAFFT algorithm works. Adjusting the settings to your needs is the best way to get accurate and meaningful results. The most important settings to understand are: the Scoring Matrix, Gap Open Penalty, and Gap Extension Penalty.

• Scoring Matrix: "Protein sequence similarity searching programs like BLASTP, SSEARCH (UNIT 3.10), and FASTA use scoring matrices that are designed to identify distant evolutionary relationships (BLOSUM62 for BLAST, BLOSUM50 for SEARCH and FASTA). Different similarity scoring matrices are most effective at different evolutionary distances. “Deep” scoring matrices like BLOSUM62 and BLOSUM50 target alignments with 20 – 30% identity, while “shallow” scoring matrices (e.g. VTML10 – VTML80), target alignments that share 90 – 50% identity, reflecting much less evolutionary change."^[13] In original MAFFT the scoring equation is shown below.

• Gap Open Penalty: A gap penalty is a negative score assigned to a gap in an alignment. It can be constant, where a fixed cost is charged for the gap, or linear, where a fixed cost is charged for each symbol inserted or deleted. An affine gap penalty combines the two by charging a constant penalty for the first symbol of a gap and another constant penalty for each additional symbol inserted or deleted.^[14]

• Gap Extension Penalty: Gap extension penalty is a cost score assigned for each additional gap symbol in a gap region in sequence alignment. It is used to discourage the formation of long gap regions. It is typically smaller than the gap opening penalty.^[15]

Accuracy and Results

MAFFT is widely considered to be one of the most accurate and versatile tools for multiple sequence alignment in bioinformatics. In fact, studies have shown that MAFFT performs exceptionally well when compared to other popular algorithms such as ClustalW and T-Coffee, particularly for larger datasets and sequences with high degrees of divergence.^[16] For example, in a study comparing the performance of various alignment algorithms on increasing sequence lengths, MAFFT's FFT-NS-2 algorithm was found to be the fastest program for all tested sequence sizes. This is due to its use of fast Fourier transform (FFT) algorithms, which enable rapid and accurate alignment of even highly divergent sequences. Because of the use of fast Fourier transform(FFT) the algorithm runs in either O(n^2) or O(n) depending on the given data set. MAFFT takes less CPU runtime than other algorithms that have the same or similar accuracies especially T-Coffee, ClustalW, and Needleman-Wunsch.^[2]

Subsequent versions of MAFFT have added other algorithms and modes of operation, including options for faster alignment of large numbers of sequences,^[9] higher accuracy alignments,^[17] alignment of non-coding RNA sequences,^[18] and the addition of new sequences to existing alignments.^[19]

MAFFT stands out among other popular algorithms such as ClustalW and T-Coffee due to its high accuracy, versatility, and range of features. It offers various alignment methods and strategies, including iterative refinement and consistency-based approaches, that further enhance the accuracy and robustness of the alignments. As a result, MAFFT is widely recognized as a powerful tool for multiple sequence alignment and is highly appreciated by the scientific community.^[20]