Related Experiment Video
Updated: Aug 13, 2026

Pattern-based Search of Epigenomic Data Using GeNemo
Published on: October 8, 2017
Compressed pattern matching in DNA sequences
Lei Chen1, Shiyong Lu, Jeffrey Ram
1Wayne State University, USA. ak3230@wayne.edu
Abstract:
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.
Related Concept Videos
Sanger Sequencing
Mismatch Repair
Mismatch Repair
The Mutator Protein Family Plays a Key Role in DNA Mismatch Repair
The human genome has more than 3 billion base pairs of DNA per cell. Prior to cell division, that vast amount of genetic...
Maxam-Gilbert Sequencing
Challenges of the Maxam-Gilbert Method
The...
DNA as a Genetic Template
Evolutionary Relationships through Genome Comparisons

