A Simple, Fast, Filter-Based Algorithm for Approximate Circular Pattern Matching

This paper deals with the approximate version of the circular pattern matching (ACPM) problem, which appears as an interesting problem in many biological contexts. The circular pattern matching problem consists in finding all occurrences of the rotations of a pattern P of length m in a text T of len...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on nanobioscience 2016-03, Vol.15 (2), p.93-100
Main Authors: Azim, Md Aashikur Rahman, Iliopoulos, Costas S., Rahman, M. Sohel, Samiruzzaman, M.
Format: Magazinearticle
Language:English
Subjects:
Algorithms
Approximation
Approximation algorithms
Circular DNA sequence
circular pattern matching
Circularity
Computational Biology - methods
Context
DNA
DNA, Circular - analysis
DNA, Circular - chemistry
DNA, Circular - genetics
Hamming distance
Nanobioscience
Nanostructure
Pattern analysis
Pattern matching
pattern recognition
Pattern Recognition, Automated - methods
Sequence Analysis, DNA - methods
State of the art
Texts
Weight reduction
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper deals with the approximate version of the circular pattern matching (ACPM) problem, which appears as an interesting problem in many biological contexts. The circular pattern matching problem consists in finding all occurrences of the rotations of a pattern P of length m in a text T of length n. In ACPM, we consider occurrences with k-mismatches under the Hamming distance model. In this paper, we present a simple and fast filter-based algorithm to solve the ACPM problem. We compare our algorithm with the state of the art algorithms and the results are found to be excellent. In particular, our algorithm runs almost twice as fast than the state of the art. Much of the efficiency of our algorithm can be attributed to its filters that are effective but extremely simple and lightweight.
ISSN:1536-1241
1558-2639
DOI:10.1109/TNB.2016.2542062