A Character Frequency based Approach to Search for Substrings of a Circular Pattern and its Conjugates in an Online Text
Keywords:Pattern matching in Strings, Circular Pattern Matching, Similarity Search
A fundamental problem in computational biology is to deal with circular patterns. The problem consists of finding the least certain length substrings of a pattern and its rotations in the database. In this paper, a novel method is presented to deal with circular patterns. The problem is solved using two incremental steps. First, an algorithm is provided that reports all substrings of a given linear pattern in an online text. Next, without losing efficiency, the algorithm is extended to process all circular rotations of the pattern. For a given pattern P of size M, and a text T of size N, the algorithm reports all locations in the text where a substring of Pc is found, where Pc is one of the rotations of P. For an alphabet size σ, using O(M) space, desired goals are achieved in an average O(MN/σ) time, which is O(N) for all patterns of length M ≤ σ. Traditional string processing algorithms make use of advanced data structures such as suffix trees and automaton. We show that basic data structures such as arrays can be used in the text processing algorithms without compromising the efficiency.
M. Crochemore and W. Rytter, Text Algorithms. Oxford University Press, 1994.
A. Apostolico and Z. Galil, Pattern Matching Algorithms. Oxford University Press, 1997.
E. McCreight, A space-economical suffix tree construction algorithm, Journal of ACM 23, 1976, pp. 262-272.
E. Ukkonen, On-line construction of suffix trees. Algorithmica, 41, 1995, pp. 249-260.
D. Gusfield , Algorithms on strings, trees and sequences. Computer Science and Computational Biology, Cambridge University Press, 1999, ISBN 0-521-58519-8.
C. Iliopoulos and M. Rahman, Indexing circular patterns, WALCOM’08, Berlin, Springer-Verlag, 2008, pp. 46–57.
F. Fernandes, L. Pereira, and A Freitas, CSA: An efficient algorithm to improve circular DNA multiple alignments. BMC Bioinformatics, 2009, 10:1–13.
G.Navarro and M. Raffinot, , Fast and Flexible String Matching by Combining bit-parallelism and Suffix Automata. ACM Journal of Experimental Algorithmics 2000, 5(4).
K. Chen, G. Huang, and R. Lee: Exact circular pattern matching using the BNDM algorithm. In Proceedings of the 28th Workshop on Combinatorial Mathematics and Computation Theory, 2011, pp. 152-161.
T. Hirvola and J. Tarhio, Approximate Online Matching of Circular Strings. Lecture Notes in Computer Science, Vol 8504, 2014, pp 315-325.
K. Chen, G. Huang, and R. Lee, Bit-parallel algorithms for exact circular string matching, Computer Journal. 57 (5), 2014, pp. 731-743.
J. Lin and D. Adjeroh, All-against-all circular pattern matching. Computer Journal 55(7), 2012, pp. 897–906.
M. Lothaire, Applied Combinatorics on Words, Cambridge University Press, 2005.
C. Barton, C Iliopoulos, and S Pissis, Fast Algorithms for approximate circular matching. Algorithms for Molecular Biology, 9:9, 2014.
P. Vinodprasad, A Novel Algorithm for String Matching with Mismatches, 5th international conference of Pattern Recognitions Applications and Methods Rome, Feb 2016, pp. 638-644.
How to Cite
Copyright (c) 2021 Computer Science
This work is licensed under a Creative Commons Attribution 4.0 International License.