MT-ClustalW: Multithreading multiple sequence alignment

DNA sequences; Natural sciences computing; Program processors; Response time (computer systems); Guide tree generation; Multithreaded implementation; Nucleotide sequences; Symmetric Multiprocessor (SMP) machines; Parallel processing systems

Abstract :

[en] ClustalW is the most widely used tool for aligning multiple protein or nucleotide sequences. The alignment is achieved via three stages: pairwise alignment, guide tree generation and progressive alignment. This paper analyzes and enhances a multithreaded implementation of ClustalW called ClustalW-SMP for higher throughput. Our goal is to maximize the degree of parallelism on multithreading ClustalW called MultiThreading-ClustalW (MT-ClustalW). As a result, bioinformatics laboratories are able to use this MT-ClustalW with much less energy consumption on multicore and SMP (Symmetric Multiprocessor) machines than that of PC clusters. The experiment results show that the MT-ClustalW framework can achieve a considerable speedup over the sequential ClustalW and original multithreaded ClustalW-SMP implementations. © 2006 IEEE.

Disciplines :

Engineering, computing & technology: Multidisciplinary, general & others

Author, co-author :

Chaichoompu, Kridsadakorn ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Bioinformatique

Kittitornkun, S.; Dept. of Computer Engineering, Faculty of Engineering, King Mongkut's Institute of Technology, Ladkrabang, Bangkok 10520, Thailand

Tongsima, S.; National Center for Genetic Engineering and Biotechnology, Klong 1, Klong Luang, Pathumtani 12120, Thailand

Language :

English

Title :

MT-ClustalW: Multithreading multiple sequence alignment

Publication date :

April 2006

Event name :

the 20th International Parallel and Distributed Processing Symposium, 2006 (IPDPS 2006)

Event place :

Rhodes Island, Greece

Event date :

25-04-2006 to 29-04-2006

Audience :

International

Main work title :

the 20th International Parallel and Distributed Processing Symposium, 2006 (IPDPS 2006)

ISBN/EAN :

1-4244-0054-6

Peer reviewed :

Peer reviewed

Commentary :

1424400546; 9781424400546

Available on ORBi :

since 31 January 2014

Statistics

Number of views

82 (3 by ULiège)

Number of downloads

0 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

D. J. Lipman, S. F. Altschul, and J. D. Kececioglu, "A tool for multiple sequence alignment," Proc. Nail. Acad. Sci. USA, vol. 86, pp. 4412-4415, 1989.
V. A. Simossis and J. Heringa, "Praline: a multiple sequence alignment toolbox that integrates homology-extended and secondary structure information," Nucleic Acids Research, 2005, vol. 33, pp. 289-294, 2005.
C. Notredame, D. G. Higgins, and J. Heringa, "T-coffee: A novel method for fast and accurate multiple sequence alignment," IDEAL J. Mol. Biol. (2000), vol. 302, pp. 205-217, 2000.
M. Schmollinger, K. Nieselt, M. Kaufmann, and B. Morgenstern, "Dialign p: Fast pair-wise and multiple sequence alignment using parallel processors," BMC Bioinformatics 2004, vol. 5, no. 128, 2004.
K. Katoh, K. Misawa, K. Kuma, and T. Miyata, "Mafft: a novel method for rapid multiple sequence alignment based on fast fourier transform," Nucleic Acids Research, 2002, vol. 30, no. 14, pp. 3059-3066, 2002.
J.D. Thompson, D.G. Higgins, and T.J. Gibson, "Clustal w: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, positions-specific gap penalties and weight matrix choice," Nucleic Acids Research 22, vol. 22, no. 22, pp. 4673-4680, 1994.
J. D. Thompson, T. J. Gibson, F. Plewniak, F. Jeanmougin, and D. G. Higgins, "The clustal_x windows interface: flexible strategies for multiple sequence alignment aided by quality analysis tools," Nucleic Acids Research, 1997, vol. 25, no. 24, pp. 48764882, 1997.
U. Catalyurek, E. Stahlberg, R. Ferreira, and J. Saltz, "Improving performance of multiple sequence alignment analysis in multi-client environments," Proceedings of the First IEEE Int. Workshop on High Performance Computational Biology (HiCOMB 2002, IPDPS 2002), 2002.
U. Catalyurek, M. Gray, T. Kurc, J. Saltz, E. Stahlberg, and R. Ferreira, "A component-based implementation of multiple sequence alignment," Proceedings of the 2003 ACM Symposium on Applied Computing (SAC2003), pp. 122-126, 2003.
http://www.sgi.com, "Silicon graphics, inc,".
D. Mikhailov, Haruna C., and R. Gomperts, "Performance optimization of clustal w: Parallel clustal w, ht clustal, and multiclustal," SGI ChemBio.
J. Cheetham, F. Dehne, S. Pitre, A. Rau-Chaplin, and P. J. Taillon, "Parallel clustal w for pc clusters," Proceedings of International Conference on Computational Science and Its Applications (ICCSA), vol. 2668, pp. 300-309, 2003.
K.B. Li, "Clustalw-mpi: Clustalw analysis using distributed and parallel computing," Bioinformatics 19, vol. 19, no. 12, pp. 1585-1586, 2003.
J. Luo, I. Ahmad, M. Ahmed, and R. Paul, "Parallel multiple sequence alignment with dynamic scheduling," Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05), 2005.
D. Nathan, R. Clemens, T. Oliver, B. Schmidt, and D. Maskell, "Multiple sequence alignment on an fpga," Proceedings of the Forth IEEE Int. Workshop on High Performance Computational Biology (HiCOMB 2005, IPDPS 2005), 2005.
N. Saitou and M. Nei, "The neighbor-joining method: a new method for reconstructing phylogenetic. trees," Mol Biol Evol, vol. 4, no. 4, pp. 406-425, 1987.
R.C. Edgar, "Muscle: a multiple sequence alignment method with reduced time and space complexity," BMC Bioinformatics. 2004, vol. 5, 2004.
http://bioinfo.pbi.nrc.ca, "Clustalw_smp ver. 0.99-9," 2002.
http://www.intel.com, "Intel thread profiler,".