Character frequency-based approach for searching for substrings of circular patterns and their conjugates in online text

• Autorzy: Prasad Vinod

Identyfikatory

DOI

doi.org/10.7494/csci.2021.22.2.3401

• Języki publikacji: EN

Abstrakty

EN

A fundamental problem in computational biology is dealing with circular patterns. The problem consists of finding a pattern and its rotations in a database. In this paper, we present two online algorithms. The first algorithm reports all of the substrings (factors) of a given pattern in an online text. Then, without losing efficiency, we extend the algorithm to process the circular rotations of the pattern. For a given pattern P of size M and a text T of size N, the extended algorithm reports all of the 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, the desired goals are achieved in an average O(MN/σ) time, which is O(N) for all patterns with length M ≤ σ. Traditional string-processing algorithms make use of advanced data structures such as suffix trees and automaton. The experimental results we have provided show that basic data structures such as arrays can be used in text-processing algorithms without compromising efficiency.

Słowa kluczowe

EN

pattern matching in strings; circular pattern matching; similarity search; substring search

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2021
• Tom: T. 22 (2)
• Strony: 235–250
• Opis fizyczny: Bibliogr. 18 poz., rys.

Twórcy

autor

Prasad Vinod

• University of Technology and Applied Sciences, Department of IT

Bibliografia

• [1] Apostolico A., Gali Z.: Pattern Matching Algorithms, Oxford University Press, 1997.
• [2] Barton C., Iliopoulos C., Pissis S.: Fast algorithms for approximate circular string matching, Algorithms for Molecular Biology, vol. 9, 2014.
• [3] Blumer A., Blumer J., Haussler D., Ehrenfeucht A., Chen M.T., Seiferas J.: The smallest automation recognizing the subwords text, Theoretical Computer Science, vol. 40, pp. 31–55, 1985.
• [4] Chen K., Huang G.S., Lee R.C.T.: Exact Circular Pattern Matching Using the BNDM Algorithm. In: 28th Workshop on Combinatorial Mathematics and Computation Theory, pp. 152–161, 2011.
• [5] Chen K., Huang G.S., Lee R.C.T.: Bit-Parallel Algorithms for Exact Circular String Matching, Computer Journal, vol. 57, pp. 731–743, 2014.
• [6] Crochemore M., Rytter W.: Jewels of Stringology: Text Algorithms, World Scientific Press, Singapore, 2003.
• [7] Faro S., Lecroq T.: Forward Dawg Matching algorithm, https://www-igm. univ-mlv.fr/∼lecroq/string/fdm.html#SECTION00220, 2016.
• [8] Faro S., Lecroq T.: A String Matching Algorithms Research Tool, https: //smart-tool.github.io/smart, 2016.
• [9] Fernandes F., Pereira L., Freitas A.: CSA: An efficient algorithm to improve circular DNA multiple alignment, BMC Bioinformatics, vol. 10, pp. 1–13, 2009.
• [10] Gusfield D.: Algorithms on Strings, Trees and Sequences. Computer Science and Computational Biology, Cambridge University Press, 1999.
• [11] Hirvola T., Tarhio J.: Approximate Online Matching of Circular Strings. In: Proceedings of the 13th International Symposium on Experimental Algorithms, pp. 315–325, 2014.
• [12] Iliopoulos C.S., Rahman M.S.: Indexing Circular Patterns. In: Proceedings of the 2nd International Conference on Algorithms and Computation, pp. 46–57, 2008.
• [13] Lin J., Adjeroh D.: All-Against-All Circular Pattern Matching, Computer Journal, vol. 55, pp. 897–906, 2012.
• [14] Lothaire M.: Applied Combinatorics on Words, Cambridge University Press, 2005.
• [15] McCreight E.: A Space-Economical Suffix Tree Construction Algorithm, Journal of ACM, vol. 23, pp. 262–272, 1976.
• [16] Navarro G., Raffinot M.: Fast and flexible string matching by combining bitparallelism and suffix automata, ACM JEA, vol. 5, 2000.
• [17] Ukkonen E.: On-line construction of suffix trees, Algorithmica, vol. 14, pp. 249–260, 1995.
• [18] Vinod P.: A Novel Algorithm for String Matching with Mismatches. In: 5th International Conference of Pattern Recognition Applications and Methods, Rome, pp. 638–644, 2016.

Uwagi

PL

„Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).”