Two-string consensus problem under non-overlapping inversion and transposition distance

Abstract For biological sequences that can be represented as strings over a finite alphabet, inversion and transposition are commonly observed mutation operations. The non-overlapping inversion and transposition distance (also simply called mutation distance) between two strings is defined as the minimum number of non-overlapping inversion and transposition operations used to transform one string into the other. Given two strings of the same length n and a constant c ≥ 0 , the two-string consensus problem under mutation distance is to determine whether or not there exists a string s ⁎ such that the mutation distance from s ⁎ to each input string does not exceed c . In this study, we present an O ( n 5 ) time and O ( n 4 ) space algorithm to solve this problem.