Abstract
From evolutionary point of view, DNA sequences may evolve by large-scale mutations (also called rearrangements), such as inversions (i.e., replacing a fragment of DNA sequence by its reverse complement) and transpositions (i.e., moving a fragment of DNA sequence from one location to another or, equivalently, exchanging two adjacent and non-overlapping fragments on DNA sequence). Given two strings of the same length n, the non-overlapping inversion and transposition distance (also called mutation distance) between them is defined as the minimum number of non-overlapping inversion and transposition operations used to transform one string into the other. In this study, we present an O(n^3) time and O(n^2) space algorithm to compute the mutation distance of two input strings. In fact, our algorithm can be used to design an algorithm that can solve the approximate string matching problem under non-overlapping inversion and transposition distance, which is to find all substrings of a given text whose mutation distances from a given pattern are less than or equal to a given threshold k, in O(nm^3) time and O(m^2) space, where n is the length of the text and m is the length of the pattern.