SimpLiFiCPM: A Simple and Lightweight Filter-Based Algorithm for Circular Pattern Matching
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 pattern P of length m in a text T of length n. In this paper, we present SimpLiFiCPM (pronounced “Simp...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2015-01-01
|
| Series: | International Journal of Genomics |
| Online Access: | http://dx.doi.org/10.1155/2015/259320 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850224466445991936 |
|---|---|
| author | Md. Aashikur Rahman Azim Costas S. Iliopoulos M. Sohel Rahman M. Samiruzzaman |
| author_facet | Md. Aashikur Rahman Azim Costas S. Iliopoulos M. Sohel Rahman M. Samiruzzaman |
| author_sort | Md. Aashikur Rahman Azim |
| collection | DOAJ |
| description | 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 pattern P of length m in a text T of length n. 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. |
| format | Article |
| id | doaj-art-4e8188bb305443b4ae75ac6160b58932 |
| institution | OA Journals |
| issn | 2314-436X 2314-4378 |
| language | English |
| publishDate | 2015-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Genomics |
| spelling | doaj-art-4e8188bb305443b4ae75ac6160b589322025-08-20T02:05:36ZengWileyInternational Journal of Genomics2314-436X2314-43782015-01-01201510.1155/2015/259320259320SimpLiFiCPM: A Simple and Lightweight Filter-Based Algorithm for Circular Pattern MatchingMd. Aashikur Rahman Azim0Costas S. Iliopoulos1M. Sohel Rahman2M. Samiruzzaman3AℓEDA Group, Department of CSE, Bangladesh University of Engineering & Technology, Dhaka 1215, BangladeshDepartment of Informatics, King's College London, Strand, London WC2R 2LS, UKAℓEDA Group, Department of CSE, Bangladesh University of Engineering & Technology, Dhaka 1215, BangladeshDepartment of Informatics, King's College London, Strand, London WC2R 2LS, UKThis 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 pattern P of length m in a text T of length n. 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.http://dx.doi.org/10.1155/2015/259320 |
| spellingShingle | Md. Aashikur Rahman Azim Costas S. Iliopoulos M. Sohel Rahman M. Samiruzzaman SimpLiFiCPM: A Simple and Lightweight Filter-Based Algorithm for Circular Pattern Matching International Journal of Genomics |
| title | SimpLiFiCPM: A Simple and Lightweight Filter-Based Algorithm for Circular Pattern Matching |
| title_full | SimpLiFiCPM: A Simple and Lightweight Filter-Based Algorithm for Circular Pattern Matching |
| title_fullStr | SimpLiFiCPM: A Simple and Lightweight Filter-Based Algorithm for Circular Pattern Matching |
| title_full_unstemmed | SimpLiFiCPM: A Simple and Lightweight Filter-Based Algorithm for Circular Pattern Matching |
| title_short | SimpLiFiCPM: A Simple and Lightweight Filter-Based Algorithm for Circular Pattern Matching |
| title_sort | simplificpm a simple and lightweight filter based algorithm for circular pattern matching |
| url | http://dx.doi.org/10.1155/2015/259320 |
| work_keys_str_mv | AT mdaashikurrahmanazim simplificpmasimpleandlightweightfilterbasedalgorithmforcircularpatternmatching AT costassiliopoulos simplificpmasimpleandlightweightfilterbasedalgorithmforcircularpatternmatching AT msohelrahman simplificpmasimpleandlightweightfilterbasedalgorithmforcircularpatternmatching AT msamiruzzaman simplificpmasimpleandlightweightfilterbasedalgorithmforcircularpatternmatching |