GPU accelerated inexact matching for multiple patterns in DNA sequences

Abstract

DNA sequencing technology generates millions of patterns on Every run of the machine and it poses a challenge for matching these patterns to the reference genome effectively with high execution speed. The main idea here is inexact matching of patterns with mismatches and gaps (insertions and deletions). In Inexact match up pattern DNA sequence is to be matched with some allowed number of errors. Here we have considered 2 errors. Errors can be mismatches or gaps. Existing algorithm as SOAP3 performs inexact matching on GPU with mismatches only. SOAP3 doesn't consider gaps (insertion and deletion). General Purpose Graphical Processing Unit (GPGPU) is an effective solution in terms of the cost and speed and there by providing a high degree of parallelism. This paper presents a parallel implementation of multiple pattern inexact matching in genome reference using CUDA based on BWT. The algorithm incorporates DFS (Depth First Search) Strategy for For matching multiple patterns, each thread of GPGPU is provided with a different pattern and hence millions of patterns can be matched using only one CUDA kernel. Since the memory of the GPU is limited then memory management should handled carefully. Synchronization of multiple threads is provided in order to prevent illegal access to the shared memory. GPU results are compared with that of CPU execution Experimental results of the proposed methodology achieved an average speedup factor of seven as compared to that of CPU execution. � 2014 IEEE.