General Information
| Description | Online multiple palindrome pattern matching |
| Homepage | http://toc.yonsei.ac.kr/OMPPM |
Publications
OMPPM: online multiple palindrome pattern matching
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 T[i−m+1:i] are pal-equivalent.
Results:
We first solve the online palindrome pattern matching problem in O(m2) preprocessing time and O(mn) query time using O(m2) space. We then extend the problem for multiple patterns and solve the online multiple palindrome pattern matching problem in O(mkM) preprocessing time and O(mkn+c) query time using O(mkM) 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.
Related Tools
slaMEM
Published December 2013
Efficient retrieval of maximal exact matches using a sampled LCP array
AlignBucket
Published July 2015
A tool to speed up ‘all-against-all’ protein sequence alignments optimizing length constraints
mDCC_tools
Published April 2016
Characterizing multi-modal atomic motions in molecular dynamics trajectories
FAIR Evaluation
Sorry, you must be signed in to evaluate this object.
