Parallelization of the MAFFT multiple sequence alignment program
BioinformaticsPublished 28 April 2010Open access
Kazutaka Katoh, Hiroyuki Toh
Citations955
SJR quartileQ1
SJR score2.45
SNIP1.47
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The three calculation stages, all-to-all comparison, progressive alignment and iterative refinement, of the MAFFT MSA program were parallelized using the POSIX Threads library to reduce the time required for large-scale sequence analyses.
Abstract
SUMMARY: Multiple sequence alignment (MSA) is an important step in comparative sequence analyses. Parallelization is a key technique for reducing the time required for large-scale sequence analyses. The three calculation stages, all-to-all comparison, progressive alignment and iterative refinement, of the MAFFT MSA program were parallelized using the POSIX Threads library. Two natural parallelization strategies (best-first and simple hill-climbing) were implemented for the iterative refinement stage. Based on comparisons of the objective scores and benchmark scores between the two approaches, we selected a simple hill-climbing approach as the default. AVAILABILITY: The parallelized version of MAFFT is available at http://mafft.cbrc.jp/alignment/software/. This version currently supports the Linux operating system only.
Keywords
ChemistryBiochemistry, Genetics and Molecular Biology
Nucleic Acids ResearchCLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice
64,940 Citations1994Julie Thompson, Desmond G. Higgins +1 more
The sensitivity of the commonly used progressive multiple sequence alignment method has been greatly improved and modifications are incorporated into a new program, CLUSTAL W, which is freely available.
Nucleic Acids ResearchMAFFT: a novel method for rapid multiple sequence alignment based on fast Fourier transform
17,754 Citations2002Kazutaka Katoh
A simplified scoring system is proposed 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.
Briefings in BioinformaticsRecent developments in the MAFFT multiple sequence alignment program
3,653 Citations2008Kazutaka Katoh, Hidehiro Toh
The initial version of the MAFFT program was developed in 2002 and was updated in 2007 with two new techniques: the PartTree algorithm and the Four-way consistency objective function, which improved the scalability of progressive alignment and the accuracy of ncRNA alignment.
Journal of Molecular EvolutionProgressive sequence alignment as a prerequisitetto correct phylogenetic trees
1,904 Citations1987Da-Fei Feng, Russell F. Doolittle
A progressive alignment method that utilizes the Needleman and Wunsch pairwise alignment algorithm iteratively to achieve the multiple alignment of a set of protein sequences and to construct an evolutionary tree depicting their relationship is described.
Journal of Molecular BiologyA strategy for the rapid multiple alignment of protein sequences
481 Citations1987Geoffrey J. Barton, Michael J.E. Sternberg
The multiple alignment algorithm yields an assignment of disulphide connectivity in mammalian serotransferrin that is consistent with crystallographic data, whereas pairwise alignments give an alternative assignment.
BioinformaticsBAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs.
478 Citations1999Julie Thompson, Frédéric Plewniak +1 more
BioinformaticsClustalW-MPI: ClustalW analysis using distributed and parallel computing
474 Citations2003Kuo-Bin Li
Clustal W-MPI is a distributed and parallel implementation of ClustalW that uses a message-passing library called MPI (Message Passing Interface) and runs on distributed workstation clusters as well as on traditional parallel computers.
Proteins Structure Function and BioinformaticsBAliBASE 3.0: Latest developments of the multiple sequence alignment benchmark
419 Citations2005Julie Thompson, Patrice Koehl +2 more
The latest release of the most widely used multiple alignment benchmark, BAliBASE, which provides high quality, manually refined, reference alignments based on 3D structural superpositions is presented, including new, more challenging test cases, representing the real problems encountered when aligning large sets of complex sequences.
Journal of Molecular BiologySignificant Improvement in Accuracy of Multiple Protein Sequence Alignments by Iterative Refinement as Assessed by Reference to Structural Alignments
327 Citations1996Osamu Gotoh
The improvement in accuracy of alignments obtained by these iterative methods over pairwise or progressive method tends to increase with decreasing average sequence identity, implying that iterative refinement is more effective for the generally difficult alignment of remotely related sequences.
Computer applications in the biosciencesOptimal alignment between groups of sequences and its application to multiple sequence alignment
129 Citations1993Osamu Gotoh
Four algorithms, A-D, were developed to align two groups of biological sequences, which are designed to evaluate the cost for a deletion/insertion more accurately when internal gaps are present in either or both groups of sequences.
Computer applications in the biosciencesComprehensive study on iterative algorithms of multiple sequence alignment
124 Citations1995Makoto Hirosawa, Yasushi Totoki +2 more
It is proved that performance improves remarkably when using a tree-based iterative method, which iteratively refines an alignment whenever two subalignments are merged in aTree-based way.
Computer applications in the biosciencesA novel randomized iterative strategy for aligning multiple protein sequences
101 Citations1991Mai Berger, Peter J. Munson
This work randomly divides a group of unaligned sequences into two subgroups, between which an optimal alignment is obtained by a Needleman-Wunsch style of algorithm, which modifies the intensive computer storage and time requirements of dynamic programming.
BioinformaticsParallel BLAST on split databases
74 Citations2003David R. Mathog
A group of programs is described which allows comparable performance to be achieved with a Beowulf configuration in which no node has enough memory to cache a database but the cluster as an aggregate does.
Computer applications in the biosciencesMultiple sequence alignment by parallel simulated annealing
60 Citations1993Masato Ishikawa, Tomoyuki Toya +4 more
The temperature parallel algorithm of simulated annealing is considered to be the most suitable for finding the optimal multiple sequence alignment because the algorithm does not require any scheduling for optimization.
BioinformaticsParallelized multiple alignment
42 Citations2002Jens Kleinjung, Nigel G. Douglas +1 more
Parallel processing functionality in the form of single-instruction multiple-data (SIMD) technology was implemented into the multiple alignment program Praline by using 'message passing interface' (MPI) routines.
MT-ClustalW: multithreading multiple sequence alignment
37 Citations2006Kridsadakorn Chaichoompu, Surin Kittitornkun +1 more
MT-ClustalW: multithreading multiple sequence alignment
30 Citations2006Kridsadakorn Chaichoompu, Surin Kittitornkun +1 more
The experiment results show that the MT-ClustalW framework can achieve a considerable speedup over the sequential ClUSTalW and original multithreaded Clustal W-SMP implementations.
Computer applications in the biosciencesMultiple alignment of sequences on parallel computers
12 Citations1993Shashank Date, Rajendra Kulkarni +3 more
A software package that allows one to carry out multiple alignment of protein and nucleic acid sequences of almost unlimited length and number of sequences is developed on C-DAC parallel computer--a transputer-based machine.