Abstract
Molecular biologists frequently scan sequence databases to detect functional similarities between proteins. Even though efficient dynamic programming algorithms exist for the problem, the required scanning time is still very high, and because of the exponential database growth finding fast solutions is of highest importance to research in this area. In this paper we present a new approach to high performance database scanning on a hybrid parallel architecture to gain supercomputer power at low cost. The architecture is built around a PC-cluster linked by a high-speed network and massively parallel processor boards connected to each node. We present the design of a parallel sequence comparison algorithm in order to derive an efficient mapping onto this architecture. This results in a database scanning implementation with significant runtime savings.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., Lipman, D. J.: Basic local alignment search tool, J. Mol. Biol., 215 (1990) 403–410.
Borah, M., Bajwa, R. S., Hannenhalli, S., Irwin, M. J.: A SIMD solution to the sequence comparison problem on the MGAP, in Proc. ASAP’94 IEEE CS (1994) 144–160.
Dahle, D., et al..: The UCSC Kestrel general purpose parallel processor, Proc. Int. Conf. Parallel and Distributed Processing Techniques and Applications, (1999) 1243–1249.
Guerdoux-Jamet, P., Lavenier, D.: SAMBA: hardware accelerator for biological sequence comparison, CABIOS 12(6) (1997) 609–615.
Hoang, D. T.: Searching genetic databases on Splash 2, in Proc. IEEE Workshop on FPGAs for Custom Computing Machines, IEEE CS, (1993) 185–191.
Hughey, R.: Parallel Hardware for Sequence Comparison and Alignment, CABIOS 12(6) (1996) 473–479.
Lang, H.-W.: The Instruction Systolic Array, a parallel architecture for VLSI, Integration, the VLSI Journal 4 (1986) 65–74.
Lang, H.-W., Maaβ, R., Schimmler, M.: The Instruction Systolic Array-Implementation of a Low-Cost Parallel Architecture as Add-On Board for Personal Computers, Proc. HPCN’94, LNCS 797, Springer (1994) 487–488.
Lavenier, D., Pacherie, J.-L.: Parallel Processing for Scanning Genomic Data-Bases, Proc. PARCO’97, Elseiver (1998) 81–88.
Lopresti, D. P.: P-NAC: A systolic array for comparing nucleic acid sequences, Computer 20(7) (1987) 98–99.
Pearson, W. R.: Comparison of methods for searching protein sequence databases, Protein Science 4(6) (1995) 1145–1160.
Singh, R. K. et al.: BIOSCAN: a network sharable computational resource for searching biosequence databases, CABIOS, 12(3) (1996) 191–196.
Schimmler, M., Lang, H.-W.: The Instruction Systolic Array in Image Processing Applications, Proc. Europto 96, SPIE 2784 (1996) 136–144.
Schmidt, B., Schimmler, M.: A Parallel Accelerator Architecture for Multimedia Video Compression, Proc. EuroPar’99, LNCS 1685, Springer (1999) 950–959.
Schmidt, B., Schimmler, M., Schröder, H.: Long Operand Arithmetic on Instruction Systolic Computer Architectures and Its Application to RSA cryptography, Proc. Euro-Par’98, LNCS 1470, Springer (1998) 916–922.
Schmidt, B.: Design of a Parallel Accelerator for Volume Rendering. In Proc. Euro-Par’2000, LNCS 1900, Springer (2000) 1095–1104.
Smith, T. F., Waterman, M.S.: Identification of common molecular subsequences, J. Mol. Biol. 147 (1981) 195–197.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schmidt, B., Schröder, H., Schimmler, M. (2001). Scanning Biosequence Databases on a Hybrid Parallel Architecture. In: Sakellariou, R., Gurd, J., Freeman, L., Keane, J. (eds) Euro-Par 2001 Parallel Processing. Euro-Par 2001. Lecture Notes in Computer Science, vol 2150. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44681-8_52
Download citation
DOI: https://doi.org/10.1007/3-540-44681-8_52
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42495-6
Online ISBN: 978-3-540-44681-1
eBook Packages: Springer Book Archive