Related Experiment Video
Updated: Mar 28, 2026

Cross-Modal Multivariate Pattern Analysis
Published on: November 9, 2011
OMPPM: online multiple palindrome pattern matching
1Department of Computer Science, Yonsei University, Seoul 120-749, Republic of Korea.
Motivation:
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.
Results:
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.
Availability And Implementation:
The source code for all algorithms is freely available at http://toc.yonsei.ac.kr/OMPPM CONTACT: kimhwee@cs.yonsei.ac.kr
Supplementary Information:
Supplementary data are available at Bioinformatics online.
More Related Videos
Related Concept Videos
Sign Test for Matched Pairs
To conduct the sign test, we first calculate the differences in...
Wilcoxon Signed-Ranks Test for Matched Pairs
Mismatch Repair
Mismatch Repair
The Mutator Protein Family Plays a Key Role in DNA Mismatch Repair
The human genome has more than 3 billion base pairs of DNA per cell. Prior to cell division, that vast amount of genetic...
Maxam-Gilbert Sequencing
Challenges of the Maxam-Gilbert Method
The...
Multiple Comparison Tests
It would be easy to compare two samples using a significance alpha level of 0.05. In other words, there is only one sample pair to be compared. However, it would be difficult to identify a significantly different sample if the number...

