Searching for gapped palindromes

• DOI: 10.1016/j.tcs.2009.09.013
• Publication Date: 2009-09-16T12:33:30Z
• Authors: Roman Kolpakov; Gregory Kucherov
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology; Theoretical Computer Science; Computer Science(all)

AbstractWe study the problem of finding, in a given word, all maximal gapped palindromes verifying two types of constraints, that we call long-armed and length-constrained palindromes. For each of the two classes, we propose an algorithm that runs in time O(n+S) for a constant-size alphabet, where S is the number of output palindromes. Both algorithms can be extended to compute biological gapped palindromes within the same time bound.