Finding Approximate Palindromes in Strings Quickly and Simply

LA home
Computing
Publications
 TR 2004/162
  software

Also see:
Bioinformatics
 Algorithms
Java

Lloyd Allison,
School of Computer Science and Software Engineering, Monash University, Clayton, Victoria, Australia 3800.
Technical Report 2004/162,
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(n2) but this does not occur with real biological sequences. A more complex algorithm guarantees O(k.n) worst-case time complexity.
 
See [arxiv...pdf][12/'04] & [software.java] of the 1st algorithm.
www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Tuesday, 21-Nov-2017 01:12:44 EST.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.