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

Md Aashikur Rahman Azim; Costas S. Iliopoulos; M. Sohel Rahman; M Samir Uzzaman

doi:10.1109/TNB.2016.2542062

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

Md Aashikur Rahman Azim, Costas S. Iliopoulos, M. Sohel Rahman, M Samir Uzzaman

Informatics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

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.

Original language	English
Article number	7433432
Pages (from-to)	93-100
Number of pages	8
Journal	IEEE TRANSACTIONS ON NANOBIOSCIENCE
Volume	15
Issue number	2
DOIs	https://doi.org/10.1109/TNB.2016.2542062
Publication status	Published - 14 Mar 2016

Keywords

Circular DNA sequence
circular pattern matching
pattern recognition

Access to Document

10.1109/TNB.2016.2542062

Cite this

@article{9000646815a242a6b6aba1ca3ebc5378,

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

abstract = "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.",

keywords = "Circular DNA sequence, circular pattern matching, pattern recognition",

author = "Azim, {Md Aashikur Rahman} and Iliopoulos, {Costas S.} and Rahman, {M. Sohel} and {Samir Uzzaman}, M",

year = "2016",

month = mar,

day = "14",

doi = "10.1109/TNB.2016.2542062",

language = "English",

volume = "15",

pages = "93--100",

journal = "IEEE TRANSACTIONS ON NANOBIOSCIENCE",

issn = "1536-1241",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "2",

}

TY - JOUR

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

AU - Azim, Md Aashikur Rahman

AU - Iliopoulos, Costas S.

AU - Rahman, M. Sohel

AU - Samir Uzzaman, M

PY - 2016/3/14

Y1 - 2016/3/14

N2 - 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.

AB - 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.

KW - Circular DNA sequence

KW - circular pattern matching

KW - pattern recognition

UR - http://www.scopus.com/inward/record.url?scp=84969913353&partnerID=8YFLogxK

U2 - 10.1109/TNB.2016.2542062

DO - 10.1109/TNB.2016.2542062

M3 - Article

AN - SCOPUS:84969913353

SN - 1536-1241

VL - 15

SP - 93

EP - 100

JO - IEEE TRANSACTIONS ON NANOBIOSCIENCE

JF - IEEE TRANSACTIONS ON NANOBIOSCIENCE

IS - 2

M1 - 7433432

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this