Abstract
One of the most significant issues of the computational biology is the multiple pattern matching for locating nucleotides and amino acid sequence patterns into biological databases. Sequential implementations for these processes have become inadequate, due to an increasing demand for more computational power. Graphic cards offer a high parallelism computational power improving the performance of applications. This paper evaluates the performance of the Wu-Manber algorithm implemented with the OpenCL framework, by presenting the running time of the experiments compared with the corresponding sequential time.
Chapter PDF
Similar content being viewed by others
References
Aho, A.V., Corasick, M.J.: Efficient String Matching: An Aid to Bibliographic Search. Communications of the ACM 18(6), 333–340 (1975)
Kouzinopoulos, C.S., Michailidis, P.D., Margaritis, K.G.: Performance Study of Parallel Hybrid Multiple Pattern Matching Algorithms for Biological Sequences. In: International Conference on Bioinformatics - Models, Methods and Algorithms, pp. 182–187. BIOINFORMATICS (2012)
Li, H., Ni, B., Wong, M., Leung, K.: A fast CUDA implementation of agrep algorithm for approximate nucleotide sequence matching. In: 2011 IEEE 9th Symposium on Application Specific Processors, pp. 74–77 (2011)
Khronos OpenCL Working Group: The OpenCL Specification, version 1.1 (2011), http://www.khronos.org/registry/cl/specs/opencl-1.1.pdf
Lin, C.-H., Tsai, S.-Y., Liu, C.-H., Chang, S.-C., Shyu, J.-M.: Accelerating String Matching Using Multi-threaded Algorithm on GPU, pp. 1–5. Communications Society (2010)
Huang, N.F., Hung, H.W., Lai, S.H., Chu, Y.M., Tsai, W.Y.: A gpu-based multiple-pattern matching algorithm for network intrusion detection systems. In: 22nd International Conference on Advanced Information Networking and Applications (AINA), pp. 62–67 (2008)
Nvidia: OpenCL Programming Guide for the CUDA Architecture, version 4.0 (2011)
OpenCL - The Open Standard for Parallel Programming of Heterogeneous Systems, http://www.khronos.org/opencl
Wu, S., Manber, U.: Agrep - A Fast Approximate Pattern-Matching Tool. In: Proceedings of USENIX Technical Conference, pp. 153–162 (1992)
Wu, S., Manber, U.: A fast algorithm for multi-pattern searching. Technical report TR-94-17, University of Arizona (1994)
Snort, http://www.snort.org
Tran, T.T., Giraud, M., Varré, J.-S.: Bit-Parallel Multiple Pattern Matching. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Waśniewski, J. (eds.) PPAM 2011, Part II. LNCS, vol. 7204, pp. 292–301. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 IFIP International Federation for Information Processing
About this paper
Cite this paper
Pyrgiotis, T.K., Kouzinopoulos, C.S., Margaritis, K.G. (2012). Parallel Implementation of the Wu-Manber Algorithm Using the OpenCL Framework. In: Iliadis, L., Maglogiannis, I., Papadopoulos, H., Karatzas, K., Sioutas, S. (eds) Artificial Intelligence Applications and Innovations. AIAI 2012. IFIP Advances in Information and Communication Technology, vol 382. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33412-2_59
Download citation
DOI: https://doi.org/10.1007/978-3-642-33412-2_59
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33411-5
Online ISBN: 978-3-642-33412-2
eBook Packages: Computer ScienceComputer Science (R0)