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(nm) 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(nm(2))-time algorithm. In addition we present a variant of our algorithm with the same complexity in the worst case, but with a (9(n) time complexity in the average case. (C) 2012 Elsevier B.V. All rights reserved.
approximate string matching average complexity analysis text processing information retrieval