Efficient string-matching allowing for non-overlapping inversions

Inversions are a class of chromosomal mutations, widely regarded as one of the major mechanisms for reorganizing the genome. In this paper we present a new algorithm for the approximate string matching problem allowing for non-overlapping inversions which runs in O ( n m ) worst-case time and O ( m 2 ) space, for a character sequence of size n and pattern of size m. This improves upon a previous O ( n m 2 ) -time algorithm. In addition we present a variant of our algorithm with the same complexity in the worst case, but with a O ( n ) time complexity in the average case.

Authors

• Domenico Cantone
• Salvatore Cristofaro
• Simone Faro

Keywords

• Approximate string matching
• Average complexity analysis
• Text processing
• Information retrieval