Compressed pattern matching in DNA sequences

We propose derivative Boyer-Moore (d-BM), a new compressed pattern matching algorithm in DNA sequences. This algorithm is based on the Boyer-Moore method, which is one of the most popular string matching algorithms. In this approach, we compress both DNA sequences and patterns by using two bits to represent each A, T, C, G character. Experiments indicate that this compressed pattern matching algorithm searches long DNA patterns (length > 50) more than 10 times faster than the exact match routine of the software package Agrep, which is known as the fastest pattern matching tool. Moreover, compression of DNA sequences by this method gives a guaranteed space saving of 75%. In part the enhanced speed of the algorithm is due to the increased efficiency of the Boyer-Moore method resulting from an increase in alphabet size from 4 to 256.

1. Introduction

String pattern matching is a common important operation in many applications. Various good solutions have been presented for pattern matching. One of the most efficient methods is the Boyer-Moore algorithm (BM) [3], [5] that was developed by R. S. Boyer and J. S. Moore. The Boyer-Moore algorithm uses three clever ideas [10]: the right-to-left scan, the bad character shift rule, and the good suffix shift rule. Together, these ideas lead to a method that typically runs in “sublinear” time for sufficiently large alphabets and sufficiently long patterns.