Searching Gapped Palindromes Using Inverted Suffix Array

Palindrome pattern matching is a classical and well-studied problem in computer science. A palindrome is a string that reads the same forward and backward. Gapped palindrome is an interesting version of the palindrome which is defined as the one having a space between left and right palindromic arms of the string. In this paper, we develop efficient algorithms to detect two different classes of gapped palindromes: long armed and length constrained in a biological sequences by using inverted suffix array. The algorithms perform the computation in O(n) time. Also, we determine palindromic weights (number and size of gapped palindromes) in the input biological string.