Finding Approximate Palindromes in Strings Quickly and Simply
| dc.creator | Allison, L. | |
| dc.date | 2004-12-01 | |
| dc.date.accessioned | 2026-07-07T03:22:06Z | |
| dc.date.available | 2026-07-07T03:22:06Z | |
| dc.description | 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. | |
| dc.description | 4 pages, 3 figures, code of the simple algorithm will soon be placed at http://www.csse.monash.edu.au/~lloyd/tildeProgLang/Java2/Palindromes/ | |
| dc.identifier | https://arxiv.org/abs/cs/0412004 | |
| dc.identifier | http://arxiv.org/abs/cs/0412004 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32467 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.2.2; I.2.8 | |
| dc.title | Finding Approximate Palindromes in Strings Quickly and Simply | |
| dc.type | text |