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

被引：0

作者：

Azim, Md. Aashikur Rahman ^{[1
]}

Iliopoulos, Costas S. ^{[2
]}

Rahman, M. Sohel ^{[1
]}

Samiruzzaman, M. ^{[2
]}

机构：

[1] Bangladesh Univ Engn & Technol, Dept Comp Sci & Engn, Dhaka 1215, Bangladesh

[2] Kings Coll London, Dept Informat, London WC2R 2LS, England

来源：

IEEE TRANSACTIONS ON NANOBIOSCIENCE | 2016年 / 15卷 / 02期

关键词：

Circular DNA sequence; circular pattern matching; pattern recognition;

D O I：

10.1109/TNB.2016.2542062

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

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.

引用

页码：95 / 102

页数：8

共 18 条

[1] Archaeal genetics - The third way [J].