Approximate Palindromes in Strings

Title: Approximate Palindromes in Strings

Research Question: How can we find approximate palindromes in a string with a maximum number of errors?

Methodology: The authors introduce a novel definition of approximate palindromes in strings and provide an algorithm to find all maximal approximate palindromes in a string with up to k errors. Their definition is based on the usual edit operations of approximate pattern matching, and the algorithm they give runs in O(k2n) time.

Results: The authors discuss two implementation-related improvements to the algorithm, demonstrating its efficiency in practice through both experiments and an average-case analysis.

Implications: This research has implications for the field of approximate pattern matching and string editing, particularly in domains like computational molecular biology where palindromes are often required to be complementary. The algorithm provided can be used to efficiently find approximate palindromes in strings, which can be useful in various applications.

Link to Article: https://arxiv.org/abs/0309043v1 Authors: arXiv ID: 0309043v1