MAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform
Kazutaka Katoh · Nucleic Acids Research · 2002
A multiple sequence alignment program, MAFFT, has been developed. The CPU time is drastically reduced as compared with existing methods. MAFFT includes two novel techniques. (i) Homo logous regions are rapidly identified by the fast Fourier transform (FFT), in which an amino acid sequence is converted to a sequence composed of volume and polarity values of each amino acid residue. (ii) We propose 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. Two different heuristics, the progressive method (FFT-NS-2) and the iterative refinement method (FFT-NS-i), are implemented in MAFFT. The performances of FFT-NS-2 and FFT-NS-i were compared with other methods by computer simulations and benchmark tests; the CPU time of FFT-NS-2 is drastically reduced as compared with CLUSTALW with comparable accuracy. FFT-NS-i is over 100 times faster than T-COFFEE, when the number of input sequences exceeds 60, without sacrificing the accuracy.
Cited by 16,948 works. doi:10.1093/nar/gkf436 Open-access PDF
Authors
References
- Gapped BLAST and PSI-BLAST: a new generation of protein database search programs
- CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice
- Atlas of protein sequence and structure
- A general method applicable to the search for similarities in the amino acid sequence of two proteins
- Improved tools for biological sequence comparison.
- Identification of common molecular subsequences
- A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences
- Numerical recipes in C: the art of scientific computing
- The Neutral Theory of Molecular Evolution
- Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison