We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

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

by Muralidhara B L
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 63 - Number 1
Year of Publication: 2013
Authors: Muralidhara B L
10.5120/10427-5096

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 },
issue_date = { February 2013 },
volume = { 63 },
number = { 1 },
month = { February },
year = { 2013 },
issn = { 0975-8887 },
pages = { 1-7 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume63/number1/10427-5096/ },
doi = { 10.5120/10427-5096 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:12:59.219653+05:30
%A Muralidhara B L
%T Staircase Method: A Novel Method for Parallelizing S-W Algorithm
%J International Journal of Computer Applications
%@ 0975-8887
%V 63
%N 1
%P 1-7
%D 2013
%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
  1. 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.
  2. 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.
  3. 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.
  4. 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).
  5. 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.
  6. 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.
  7. 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.
  8. Huang X, Hardison R C, and Miller W. 1990. "A space-efficient algorithm for local similarities". CABIOS, Vol. 6, 373-381.
  9. Hughey Richard. 1996. "Parallel Hardware for Sequence Comparison and Alignment". CABIOS, Vol. 12, No. 6, pp. 473-479.
  10. Kent James. W. 2002. "BLAT – The BLAST-Like Alignment Tool". Genome Research, Vol. 12, pp. 656-664.
  11. Kurtz Atefan and Chris Schleiermacher. 1999. "REPuter: fast computation on maximal repeats in complete genomes". Bioinformatics, Vol. 15, no. 5, 426-427.
  12. 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.
  13. Ma Bin, Joh Tromp and Ming Li. "Pattern Hunter: faster and more sensitive homology search". 2002. Bioinformatics, Vol. 18, no. 3, pp. 440-445.
  14. 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.
  15. 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.
  16. 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.
  17. 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).
  18. Person W R and Miller W. 1992. "Dynamic Programming algorithm for biological sequence comparison". Methods Enzymol, Vol. 210, pp. 575-601.
  19. 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.
  20. 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.
  21. Setubal and Meidanis. 1997. Introduction to Computational Molecular Biology. Brooks/Cole Publishing Company.
  22. Smith T. F, & M. S. Waterman. 1981. "Identification of Common Molecular Sequences". Journal of Molecular Biology, 147, 195-197.
  23. 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.
  24. 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

Keywords

Sequence alignment Efficiency Load balance Speedup staircase method

Powered by PhDFocusTM