OMPPM: online multiple palindrome pattern matching

Area of Science:

• Bioinformatics
• Computational Biology
• Stringology

Background:

• Palindromic structures are crucial in analyzing biological sequences like DNA, RNA, and proteins.
• Identifying palindromes aids in understanding sequence function and evolution.
• The concept of pal-equivalence extends palindrome analysis to comparing sequence segments.

Purpose of the Study:

• To address the palindrome pattern matching problem for biological sequences.
• To develop efficient algorithms for finding pal-equivalent patterns.
• To extend the solution for single patterns to multiple patterns.

Main Methods:

• Developed an online algorithm for single pattern palindrome matching.
• Achieved O(m^2) preprocessing time and O(mn) query time.
• Extended the approach to handle multiple patterns efficiently.

Main Results:

• The single pattern algorithm uses O(m^2) space.
• The multiple pattern algorithm achieves O(M + mk*c) preprocessing time and O(M + mk*c) query time.
• Algorithms are available for public use.

Conclusions:

• Efficient algorithms for palindrome pattern matching have been developed.
• The methods are applicable to large-scale biological sequence analysis.
• The provided algorithms facilitate research in bioinformatics and computational biology.