This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: Parts read like a manual. (November 2023) |
In bioinformatics, MAFFT (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 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]
| Developer(s) | Kazutaka Katoh |
|---|---|
| Initial release | 2002 |
| Stable release | 7.526
/ April 2024 |
| Written in | C |
| Operating system | Unix, Linux, Mac, Windows |
| Type | Bioinformatics tool |
| Licence | BSD, GPL, others[1] |
| Website | mafft |
History
editThere have been many variations of the MAFFT software, some of which are listed below:
- MAFFT – The first version, 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 software, released in 2005, was a rewrite of the original software.[3] This generation introduced a simplified scoring system that performs well for reducing CPU time and increasing 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 on prior versions.[3] It implemented group-to-group alignment, guide trees which had an approximate but faster O(N log N) tree-building algorithm, and made the version usable with larger datasets of ~50,000 sequences.
- MAFFT v7 – The fourth generation, released in 2012, improved the speed and accuracy substantially.[3]
- MAFFT v7.511 – A more recent version, released in December 2022, improved on version 7 with various bug fixes. One of the most notable being an overhaul to the
--mergeoption, which now includes, enabling iterative refinement, creating a single MSA from multiple sub-MSAs, as well as the combination of--mergeand--seed. There were also several minor enhancements to the speed and accuracy of MAFFT v7.
Algorithm
editThe 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 because 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 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
editWeb form
editInput
edit
This program can take in multiple sequences as input, which can be entered in two ways:
Sequence input window
edit.png)
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 partly 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
editThe 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 and Windows format have different line endings than those saved on Unix and 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
editThe user will have the option to request the Multiple Sequence Alignment (MSA) to be generated in one of the two available formats:
| Output format | Description | Abbreviation |
|---|---|---|
| Pearson/FASTA | Pearson or FASTA sequence format | fasta |
| ClustalW | ClustalW alignment format without base/residue numbering | clustalw |
Default value is: Pearson/FASTA [fasta]
| Symbol | Definition | Meaning |
|---|---|---|
| * | asterisk | Conserved sequence (identical) |
| : | colon | Conservative mutation |
| . | period | Semi-conservative mutation |
| ( ) | blank | Non-conservative mutation |
| - | dash | Gap |
Settings
editThere are many settings that affect how the MAFFT algorithm works. Adjusting the settings to 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
editMAFFT 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 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]
Later 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 accuracy and robustness of 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]
See also
editReferences
edit- ^ The base MAFFT software is distributed under one of the BSD licenses, while versions for Microsoft Windows are licensed under a GNU General Public License. Some distributions of MAFFT contain software licensed under other licenses https://mafft.cbrc.jp/alignment/software/
- ^ a b c d Katoh, Kazutaka; Misawa, Kazuharu; Kuma, Kei-ichi; Miyata, Takashi (2002). "MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform". Nucleic Acids Research. 30 (14): 3059–66. doi:10.1093/nar/gkf436. PMC 135756. PMID 12136088.
- ^ a b c d "MAFFT ver.7 - a multiple sequence alignment program". mafft.cbrc.jp. Retrieved 28 April 2021.
- ^ Katoh, K.; Toh, H. (2006). "PartTree: An algorithm to build an approximate tree from a large number of unaligned sequences". Bioinformatics. 23 (3): 372–4. doi:10.1093/bioinformatics/btl592. PMID 17118958.
- ^ Katoh, K.; Kuma, K.; Miyata, T.; Toh, H. (2005). "Improvement in the accuracy of multiple sequence alignment program MAFFT". Genome Informatics. International Conference on Genome Informatics. 16 (1): 22–33. PMID 16362903.
- ^ Katoh, Kazutaka; Toh, Hiroyuki (2008). "Improved accuracy of multiple ncRNA alignment by incorporating structural information into a MAFFT-based framework". BMC Bioinformatics. 9: 212. doi:10.1186/1471-2105-9-212. PMC 2387179. PMID 18439255.
- ^ Katoh, Kazutaka; Frith, Martin C (2012). "Adding unaligned sequences into an existing alignment using MAFFT and LAST". Bioinformatics. 28 (23): 3144–6. doi:10.1093/bioinformatics/bts578. PMC 3516148. PMID 23023983.
- ^ The base MAFFT software is released under one of the BSD licenses, while versions for Microsoft Windows are released under a GNU General Public License. Some distributions of MAFFT contain software licensed under other licenses https://mafft.cbrc.jp/alignment/software/
- ^ a b c d e f Katoh, K.; Standley, D. M. (April 2013). "MAFFT Multiple Sequence Alignment Software Version 7: Improvements in Performance and Usability". Molecular Biology and Evolution. 30 (4): 772–780. doi:10.1093/molbev/mst010. PMC 3603318. PMID 23329690.
- ^ a b c Katoh, Kazutaka; Toh, Hiroyuki (July 2008). "Recent developments in the MAFFT multiple sequence alignment program". Briefings in Bioinformatics. 9 (4): 286–298. doi:10.1093/bib/bbn013. PMID 18372315.
- ^ a b "MAFFT Help and Documentation - Job Dispatcher Sequence Analysis Tools - EMBL-EBI". www.ebi.ac.uk. Retrieved 2023-04-24.
- ^ a b "Windows vs. Unix Line Endings". www.cs.toronto.edu. Retrieved 2023-04-27.
- ^ Pearson, William R. (October 2013). "Selecting the Right Similarity‐Scoring Matrix". Current Protocols in Bioinformatics. 43 (1): 3.5.1–3.5.9. doi:10.1002/0471250953.bi0305s43. PMC 3848038. PMID 24509512.
- ^ "ROSALIND: Glossary: Gap penalty".
- ^ Carroll, Hyrum; Clement, Mark; Ridge, Perry; Snell, Quinn (October 2006). "Effects of Gap Open and Gap Extension Penalties". Faculty Publications.
- ^ Edgar, Robert; Batzoglou, Serafim (June 2006). "Multiple sequence alignment". Current Opinion in Structural Biology. 16 (3): 368–373. doi:10.1016/j.sbi.2006.04.004. PMID 16679011.
- ^ Katoh, Kazutaka (2010-04-28). "Parallelization of the MAFFT multiple sequence alignment program". Bioinformatics. 26 (15): 1899–1900. doi:10.1093/bioinformatics/btq224. PMC 2905546. PMID 20427515.
- ^ Kazunori, Yamada (4 July 2016). "Application of the MAFFT sequence alignment program to large data—reexamination of the usefulness of chained guide trees". Bioinformatics. 32 (21): 3246–3251. doi:10.1093/bioinformatics/btw412. PMC 5079479. PMID 27378296.
- ^ Kazutaka, Katoh (27 September 2012). "Adding unaligned sequences into an existing alignment using MAFFT and LAST". Bioinformatics. 28 (23): 3144–3146. doi:10.1093/bioinformatics/bts578. PMC 3516148. PMID 23023983.
- ^ Edgar, R. C. (8 March 2004). "MUSCLE: multiple sequence alignment with high accuracy and high throughput". Nucleic Acids Research. 32 (5): 1792–1797. doi:10.1093/nar/gkh340. PMC 390337. PMID 15034147.