SimpLiFiCPM: A Simple and Lightweight Filter-Based Algorithm for Circular Pattern Matching. (18th October 2015)

• Record Type: Journal Article
• Authors: Azim, Md. Aashikur Rahman; Iliopoulos, Costas S.; Rahman, M. Sohel; Samiruzzaman, M.
• Other Names: Lin Chun-Yuan Academic Editor.
• Is Part Of: International journal of genomics. Volume 2015(2015)
• Publication Date: 2015-10-18
• Subjects: Genomes -- Periodicals; Genomics -- Periodicals; Cytogenetics -- Periodicals; Genomics; Genome; Molecular Biology; Cytogenetics; Genomes; Genomics; Periodicals; 572.86
• DOI: 10.1155/2015/259320
• Languages: English
• ISSNs: 2314-436X

Abstract

Abstract : This paper deals with the circular pattern matching (CPM) problem, which appears as an interesting problem in many biological contexts. CPM consists in finding all occurrences of the rotations of a patternP of lengthm in a textT of lengthn . In this paper, we present SimpLiFiCPM (pronounced "Simplify CPM"), a simple and lightweight filter-based algorithm to solve the problem. We compare our algorithm with the state-of-the-art algorithms and the results are found to be excellent. Much of the speed of our algorithm comes from the fact that our filters are effective but extremely simple and lightweight.