The week's pick
Random Articles
Reseach Article
Staircase Method: A Novel Method for Parallelizing S-W Algorithm
by
Muralidhara B L
| 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
- 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
Keywords