## Finding Approximate Palindromes in Strings Quickly and Simply

#### Lloyd __Allison__,
Technical Report 2004/162,
arxiv:cs.DS/0412004,

School of Computer Science and Software Engineering,
Monash University, Clayton, Victoria,
Australia 3800.

23 Nov. 2004 (draft 19 Sept.)

**Abstract**:
Described are two algorithms to find long approximate palindromes
in a string, for example a DNA sequence.
A simple algorithm requires O(n)-space
and almost always runs in O(k.n)-time
where n is the length of the string and
k is the number of ''errors'' allowed in the palindrome.
Its worst-case time-complexity is O(n^{2}) but this
does not occur with real biological sequences.
A more complex algorithm guarantees O(k.n) worst-case time complexity.

**See**
[arxiv:cs.DS/0412004][12/'04] &
[software.java] of the 1st algorithm.