OMPPM: online multiple palindrome pattern matching.

Abstract

A palindrome is a string that reads the same forward and backward. Finding palindromic substructures is important in DNA, RNA or protein sequence analysis. We say that two strings of the same length are pal-equivalent if, for each possible centre, they have the same length of the maximal palindrome. Given a text T of length n and a pattern P of length m, we study the palindrome pattern matching problem that finds all indices i such that P and [Formula: see text] are pal-equivalent. We first solve the online palindrome pattern matching problem in O(m(2)) preprocessing time and O(mn) query time using O(m(2)) space. We then extend the problem for multiple patterns and solve the online multiple palindrome pattern matching problem in [Formula: see text] preprocessing time and [Formula: see text] query time using [Formula: see text] space, where M is the sum of all pattern lengths, mk is the longest pattern length and c is the number of pattern occurrences. The source code for all algorithms is freely available at http://toc.yonsei.ac.kr/OMPPM CONTACT: kimhwee@cs.yonsei.ac.kr Supplementary data are available at Bioinformatics online.