The week's pick
Random Articles
Reseach Article
Parallelizing and Analyzing the Behavior of Sequence Alignment Algorithm on a Cluster of Workstations for Large Datasets
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 74 - Number 21 |
| Year of Publication: 2013 |
| Authors: Sathe S. R, Shrimankar D. D. |
10.5120/13042-0091
|
Sathe S. R, Shrimankar D. D. . Parallelizing and Analyzing the Behavior of Sequence Alignment Algorithm on a Cluster of Workstations for Large Datasets. International Journal of Computer Applications. 74, 21 ( July 2013), 18-30. DOI=10.5120/13042-0091
Abstract
An MPI based parallelization technique for improving the scalability of the global sequence alignment algorithm on clusters of workstation is presented. We propose the parallel implementation of the Wavefront algorithm based on a chunk size transformation to handle large dataset with message passing model. Molecular biologists frequently align DNA sequences of entire genomes to detect important matched and mismatched regions. Even though efficient dynamic programming algorithms exist for this problem, the required computing time is still very high due to the size of these sequences. Because the number of sequenced organisms is increasing rapidly, fast and accurate solutions are of highest importance to research in this area. We show that an appropriate choice of the number of processes and chunk size has great impact on the overall system performance on cluster system. We have conducted the experiments on real-life DNA samples of house mouse mitochondrion and the DNA of rabbit mitochondrion obtained from the public database GenBank [GenBank, http://www. ncbi. nih. gov] in our experiment to measure the algorithm behavior appropriately. The results obtained from performed experiments, demonstrate that developed parallel Wavefront algorithm exposes high speedup and scales linearly with the increasing number of processes. Also the communication among processes and memory requirements are kept at minimum to achieve high efficiency. The experiments were performed on cluster which consists of two workstations of 12 core each with multithreading environment.
References
- A. Boukerche, Alba Melo, "Bioinformatics applications in grid computing environments," Grid Computing for Bioinformatics and Computational Biology, pp. 301-325, 2007.
- A. Boukerche, A. C. de Melo, "Computational molecular biology," Parallel Computing for Bioinformatics and Computational Biology: Models Enabling Technologies, and Case Studies, pp. 149-166, 2006.
- J. C. Setubal and J. Meidanis, Introduction to Computational Molecular Biology. Brooks/Cole Publishing Company, 1997.
- . Saul B. Needleman and Christian D. Wunsch. "A general method applicable to the search for similarities in the amino acid sequence of two sequences," Journal of Molecular Biology, pp. 443-453, 1970.
- A. Zomaya, Parallel Computing for Bioinformatics and Computational Biology: Models, Enabling Technologies, and Case Studies, 2006.
- Stephen F. Altschul, Warren Gish, Webb Miller, Eugene W. Myers, David J. Lipman, "A basic local alignment search tool," Journal of Molecular Biology, pp 403-410, 1990.
- T. F. Smith, M. S. Waterman, "Identification of common molecular subsequences," J. Mol. Biol. Pp. 195-197, 1981.
- Chaichoompu K, Kittitornkun S, Tongsima S. "MT-clustalW: multithreading multiple sequence alignment," IPDPS,
- Li KB, "ClustalW-MPI: ClustalW analysis using distributed and parallel computing," Bioinformatics, pp. 1585–1586, 2006.
- Schmollinger M, Nieselt K, Kaufmann M, Morgenstern B, "DIALIGN P: fast pair-wise and multiple sequence alignment using parallel processors," BMC Bioinform, 2004
- Tan G, Feng S, Sun N, "Parallel multiple sequences alignment in SMP clusters," Highperformance computing, 2005.
- Zola J, Yang X, Rospondek A, Aluru S, "T-Coffee: a parallel multiple sequence aligner," PDCS, pp. 248–253, 2007.
- Boukerche A, Correa JM, Melo ACMA, Jacobi RP, "A hardware accelerator for the fast retrieval of DIALIGN biological sequence alignments in linear space," IEEE Trans. Comput, pp. 808–821, 2010.
- Altschul, S. F. , Gish, W. , Miller, W. , Myers, E. W. , Lipman, D. J. , "Basic local alignment search tool," Journal of Molecular Biology, pp. 403-410, 1990.
- Chao, K. M. , Zhang, J. , Ostell, J. , Miller, W. , "A local alignment tool for long DNA sequences," Computer Applications in the Biosciences, pp. 147-153, 1994.
- Pearson, W. R. , "Comparison of methods for searching protein sequence databases," Protein Science, pp. 1145-1160, 1995.
- Martins, W. S. , del Cuvillo, J. B. , Cui, W. , Gao, G. R. , "Whole Genome Alignment using a Multithreaded Parallel Implementation," Proceedings 13th Symposium on Computer Architecture and High Performance Computing, September 2001.
- Osamu Gotoh. "An improved algorithm for matching biological sequences," Journal of Molecular Biology, pp. 705-708, 1982.
- E. W. Myers and W. Miller, "Optimal alignments in linear space," Computer Applications in the Biosciences, pp. 11-17, 1988.
- G. Navarro, "A guided tour to approximate string matching," ACM Computing Surveys, 2001.
- J. C. Setubal, J. Meidanis, "Introduction to Computational Molecular Biology," Brooks/Cole Publishing Company, 1997.
- D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences," Communications of the ACM, pp. 341-343, 1975.
- David W. Mount, Bioinformatics: Sequence and Genome Analysis, Cold Spring Harbor Laboratory Press, 2004.
- S. Aji, F. Blagojevic, W. Feng, D. S. Nikolopoulos. "Cell-SWat: Modeling and Scheduling Wavefront Computations on the Cell Broadband Engine" Proceedings of the ACM nternational Conference on Computing Frontiers, pp. 13-22, 2008
- C. Quammen, Introduction to programming shared-memory and distributed memory parallel computers, Crossroads 12, 2005.
- W. Gropp, E. Lusk, A. Skjellum, Using MPI: Portable Parallel Programming with the Message-Passing Interface, MIT Press, Cambridge, MA, USA, 1994.
- E. Gabriel, G. E. Fagg, G. Bosilca, T. Angskun, J. J. Dongarra, J. M. Squyres, V. Sahay, P. Kambadur, B. Barrett, A. Lumsdaine, R. H. Castain, D. J. Daniel, R. L. Graham,T. S. Woodall, "Open MPI: goals, concept, and design of a next generation MPI implementation," Proceedings, 11th European PVM/MPI Users' Group Meeting, Budapest, Hungary, pp. 97–104.
- Plaat, A. , Bal, H. E. , Hofman, R. H. F. , "Sensitivity of Parallel Applications to Large Differences in Bandwidth and Latency in Two-Layer Interconnects," Proceedings 5th IEEE HPCA'99, pp. 244-253, 1999.
- Foster, I. , Geisler, J. , Gropp, W. , Karonis, N. , Lusk, E. , Thiruvathukal, G. , Tuecke S. , "Wide-Area Implementation of the Message Passing Interface," Parallel Computing, pp. 1735-1749, 1998.
- http://www. niu. edu/mpi
- http://www-unix. mcs. anl. gov/mpi/mpich/
- Schmidt, B. , Schr¨oder, H. , Schimmler, M. , "Massively Parallel Solutions for Molecular Sequence Analysis," Proc. IPDPS'02, Ft. Lauderdale, Florida, 2002.
- Schmidt, B. , Schr¨oder, H. , Schimmler, M. , "A hybrid architecture for bioinformatics," Future Generations Computer Systems, pp. 855-862, 2002.
Index Terms
Keywords