title: 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.
authors.affiliation: Department of Computer Science, Yonsei University, Seoul 120-749, Republic of Korea.
authors.forename: Hwee
authors.initials: H
authors.lastname: Kim
authors.affiliation: Department of Computer Science, Yonsei University, Seoul 120-749, Republic of Korea.
authors.forename: Yo-Sub
authors.initials: YS
authors.lastname: Han
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D004247:DNA; D055029:Inverted Repeat Sequences; D011381:Programming Languages; D012313:RNA; D017422:Sequence Analysis, DNA
chemical_list: D012313:RNA; D004247:DNA