Palindromes are strings of symbols that read the same forward and backward. Palindromes have many applications, especially in DNA sequences. Palindromes appear frequently and are widespread in human cancers, and identify them could help advance the understanding of genomic instability. The palindrome detection problem is therefore an important issue in computational biology. Porto et al. presented an algorithm for finding the maximal approximate palindromes with error k. In this paper, we extended their results by proposing an effective algorithm based upon dynamic programming strategy to find all approximate palindromes up to error k under the similar cost complexity.
WIT Transactions on Information and Communication Technologies