摘要
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.