Abstract

Bioinformatics is one of the field where high performance computation widely used. Pattern matching is essential task in Bio-informatics. A powerful technique for searching sequence patterns in the biological sequence databases is the pattern recognition. Significant increase in the number of protein sequences and DNA expanded the need for the enhancement of performance of pattern matching. Hence fast and high performance algorithms are highly demanded in many applications of computational molecular biology and bio-informatics. In this paper we present a parallel processing approach for pattern matching algorithm using distributed parallel programming paradigm Message Passing Interface (MPI). The focus of the research is the implementation of basic algorithm naïve for pattern matching by utilizing compute nodes of high performance computing server optimally. The parallel algorithm finds correct matches and experimental results show very high performance gain over sequential approach.

References

• A. Tumeo and O. Villa. Accelerating DNA analysis applications on GPU clusters. In IEEE 8th Symposium on Application Specific Processors (SASP), pages 71–76. 2010.
• Mount D. Bioinformatics: Sequence and Genome Analysis, Cold Spring Harbor Laboratory(CSHL) Press,2004.
• M. J. Quinn, Parallel Programming in C with MPI and OpenMP, Tata McGraw Hill Publications, 2003, p. 338.
• http://codeapirant.worpress.com/2013/05/20/brute-force-naiveapproach-to-string-searching
• R.S. Boyer, J.S. Moore, "A fast string searching algorithm,"Communication of the ACM, Vol. 20, No. 10, 1977, pp.762–772.
• S. Rajesh , S.Prathima, Dr.L.S.S.Reddy, “Unusual Pattern Detection in DNA Database Using KMP Algorithm”,2010 International Journal of Computer Applications(0975-8887) Volume 1 – No.22.
• KNUTH, D. E, MORRIS JR J. H , PRATT V. R,”Fast pattern matching in strings”, In the procd. Of SIAM J.Comput.Vol. 6, 1, pp.323–350, 1977.
• Lee W-P, Stromberg MP, Ward A, Stewart C, Garrison EP, et al. (2014) “MOSAIK: A Hash-Based Algorithm for Accurate Next-Generation Sequencing Short-Read Mapping.” PLoS ONE 9(3):e90581. doi:10.1371/journal.pone.0090581.
• Parida, Laxmi (2008) Pattern Discovery in Bioinformatics: Theory& Algorithms Boca Raton: Chapman & Hall/CRC pg. 139-182,183-212
• Shima Soroushnia, Masoud Daneshtalab, Tapio Pahikkala, Juhu Plosila “Parallel Implementation of Fuzzified Pattern Matching Algorithm on GPU”, IEEE 23rd Euromicro International Conference on Parallel, Distributed and Network-Based processing(PDP), 2015.
• Kefu Xu, Wenke Cui, Yue Hu, Li Guo, “Bit-Parallel Multiple Approximate String Matching based on GPU”, First International conference on Information Technology and Quantitative Management, Procedia Computer science , Vol 17,2013, pages 523-529.
• Daniel Luchaup, Randy Smith, Cristian Estan, Somesh Jha, “Speculative Parallel Pattern Matching” IEEE Transactions on Information Forensics and Security, Vol 6, Issue 2, 2011,pages 438-451.
• Spector, A. Z. 1989. Achieving application requirements. In Distributed Systems, S. Mullender
• Sinan Sameer Mahmood Al-Dabbagh, Nawaf Hazim Barnouti, Mustafa Abdul Sahib Naser, Zaid G. Ali, “Parallel Quick Search Algorithm for the exact String Matching problem using OpenMP”, Journal of Computer and Communications, Scientific Research Publishing , Vol 4,2016, pages1-11.
• Gulfishan Firdose Ahmed, Nilay khare, “String Matching Algorithms using Bit Parallelism”, International Journal of Advanced Engineering and Global Technology Vol-2, Issue-5, May 2014.
• Dale E. Parson, "Parallel reduced-instruction-set-computer architecture for real-time symbolic pattern matching", Proc. SPIE 1468, Applications of Artificial Intelligence IX, (1 March 1991); doi: 10.1117/12.45534.
• Saman Ashkiani, Nina Amenta, John D. Owens, “Parallel Appraoches to the String Matching Problem on the GPU”, SPAA 2016.