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.