Research Article

Staircase Method: A Novel Method for Parallelizing S-W Algorithm

by  Muralidhara B L
journal cover
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 63 - Issue 1
Published: February 2013
Authors: Muralidhara B L
10.5120/10427-5096
PDF

Muralidhara B L . Staircase Method: A Novel Method for Parallelizing S-W Algorithm. International Journal of Computer Applications. 63, 1 (February 2013), 1-7. DOI=10.5120/10427-5096

                        @article{ 10.5120/10427-5096,
                        author  = { Muralidhara B L },
                        title   = { Staircase Method: A Novel Method for Parallelizing S-W Algorithm },
                        journal = { International Journal of Computer Applications },
                        year    = { 2013 },
                        volume  = { 63 },
                        number  = { 1 },
                        pages   = { 1-7 },
                        doi     = { 10.5120/10427-5096 },
                        publisher = { Foundation of Computer Science (FCS), NY, USA }
                        }
                        %0 Journal Article
                        %D 2013
                        %A Muralidhara B L
                        %T Staircase Method: A Novel Method for Parallelizing S-W Algorithm%T 
                        %J International Journal of Computer Applications
                        %V 63
                        %N 1
                        %P 1-7
                        %R 10.5120/10427-5096
                        %I Foundation of Computer Science (FCS), NY, USA
Abstract

Sequence comparison is a basic operation in DNA sequencing projects, and most of sequence comparison methods are based on heuristics, which are fast but not sensitive. The Dynamic Programming Algorithm, Smith-Waterman, obtains the best alignment, but at the expense of computational time. Unfortunately, the inefficiency in the performance of the Smith-Waterman algorithm limits its applications in the real world. A possible way out of this is to use parallelization methods for decreasing the time taken to execute the algorithm. In this paper, we present a two master method and a novel parallel technique called staircase method to improve the performance of the Smith-Waterman algorithm.

References
  • Altschul F Stephen, Warren Gish, Webb Miller, Eugene W. Myers & David J. Lipman. 1990. "Basic Local Alignment Search Tool". Journal of Molecular Biology, 215, 403-410.
  • Altschul F Stepehn, Tomas L. Madden, Alejandro A. Schaffer, Jinghui Zhang, Zheng Zhang, Webb Miller and David J. Lipman. 1997. "Gapped BLAST and PSI-BLAST: a new generation of protein database search programs". Nucleic Acids Research, Vol. 25, No. 17, 3389-3402.
  • Batista Rodolfo Bezerra, Debora Nery Silva, Alba Cristina Magalhaes Alves de Melo, and Li Weigang. 2004. "Using a DSM Application to Locally Align DNA Sequences". 2004IEEE International Symposium on Cluster Computing and the Grid, IEEE Computer Society.
  • Boukerche Azzedine, Alba Cristina Magalhaes Alves De Melo, Maria Emilia Telles Walter, Renata Cristina Faray Melo, Marcelo Nardelli Pinto Santana, Rodolfo Bezerra Batista. 2004. "A Performance Evaluation of a Local DNA Sequence Alignment Algorithm on a Cluster of Workstations". Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04).
  • Delcher L Arthur, Adam Phillippy, Jane Carlton and Steven L. Salzberg. 2002. "Fast algorithms for large-scale genome alignment and comparison". Nucleic Acids Research, Vol. 30, No. 11, 2478-2483.
  • Delcher L Arthur, Simon Kasif, Robert D. Fleischmann, Jeremy Peterson, Owen White and Steven L Salzberg. 1999. "Alignment of whole genomes". Nucleic Acids Research, Vol. 27, No. 11, 2369-2376.
  • Florea L, Hartzell G, Zhang Z, Rubin G M, and Webb Miller W. 1998. "A computer program for aligning a cDNA sequence with a genomic DNA sequence". Genome Res. Vol. 8, pp. 967-974.
  • Huang X, Hardison R C, and Miller W. 1990. "A space-efficient algorithm for local similarities". CABIOS, Vol. 6, 373-381.
  • Hughey Richard. 1996. "Parallel Hardware for Sequence Comparison and Alignment". CABIOS, Vol. 12, No. 6, pp. 473-479.
  • Kent James. W. 2002. "BLAT – The BLAST-Like Alignment Tool". Genome Research, Vol. 12, pp. 656-664.
  • Kurtz Atefan and Chris Schleiermacher. 1999. "REPuter: fast computation on maximal repeats in complete genomes". Bioinformatics, Vol. 15, no. 5, 426-427.
  • Liao Hsien-Yu, Meng-Lai Yin, and Yi Cheng. 2004. "A Parallel Implementation of the Smith-Waterman for Massive sequences Searching". Proceedings of the 26th Annual International Conference of the IEEE EMBS, pp. 2817-2820.
  • Ma Bin, Joh Tromp and Ming Li. "Pattern Hunter: faster and more sensitive homology search". 2002. Bioinformatics, Vol. 18, no. 3, pp. 440-445.
  • Martins W. S, J. B. Del Cuvillo, F. J. Useche, K. B. Theobald, and G. R. Gao. 2001. "A Multithreaded Parallel implementation of a Dynamic Programming Algorithm for Sequence comparison". Int. Symposium on Computer Architecture and HPC (SBAC-PAD), 1-8.
  • Needleman Saul B & Christian D. Wunsch. 1970. "A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins". Journal of Molecular Biology, 48, 443-453.
  • Pekurovsky D, I. N. Shindyalov and P. E. Bourne. 2004. "A Case study of high-throughput biological data processing on parallel platforms". Bioinformatics, Vol. 20, no. 12, pp. 1940-1947.
  • Pellicer Stephen, Nova Ahmed, Yi Pan and Yao Zheng. 2005. "Gene Sequence Alignment on a Public Computing Platform". Proceedings of the 2005 International Conference on Parallel Processing Workshops (ICPPW'05).
  • Person W R and Miller W. 1992. "Dynamic Programming algorithm for biological sequence comparison". Methods Enzymol, Vol. 210, pp. 575-601.
  • Rognes Torbjorn & Erling Seeberg. 1981. "Six-fold speedup of Smith-Waterman sequence database searches using parallel processing on common microprocessors". Bioinformatics. Vol. 16, no. 8, 699-706.
  • Schwartz S, Zhang Z, Frazer K A, Smith A, Riemer C, Bouck J, Gibbs R, Hardison R, and Miller W. 2000. "PipMaker – A web server for aligning two genomic DNA sequences". Genome Res. , Vol 10, pp. 577-586.
  • Setubal and Meidanis. 1997. Introduction to Computational Molecular Biology. Brooks/Cole Publishing Company.
  • Smith T. F, & M. S. Waterman. 1981. "Identification of Common Molecular Sequences". Journal of Molecular Biology, 147, 195-197.
  • Usuka J, Zhu W, and Brendel V. 2000. "Optimal spiced alignment of homologous cDNA to a genomic DNA template". Bioinformatics, Vol. 16, pp. 203-211.
  • Zhu J, Liu J S, and Lawrence C E. 1998. "Bayesian adaptive sequence alignment algorithms". Bioinformatics, Vol. 14, pp. 25-39.
Index Terms
Computer Science
Information Sciences
No index terms available.
Keywords

Sequence alignment Efficiency Load balance Speedup staircase method

Powered by PhDFocusTM