Compressed Pattern Matching in DNA Sequences Using Multithreaded Technology

Compressed pattern matching on large DNA sequences data is very important in bioinformatics. In this paper, in order to improve the performance by searching pattern in parallel time, multithreaded programming technique is used. Then, two novel multithreaded algorithms are proposed, named MTd-BM and MTd-Horspool. The first one is a mutation of d-BM algorithm, which is based on Boyer-Moore method. And the second one is designed in the similitude of MTd-BM, but using Horspool method as its foundation. The experimental results show that these two algorithms are nearly 2 times faster than the d-BM algorithm for long DNA pattern (length>50). Moreover, compression of DNA sequences gives a guaranteed space saving of 75%.