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

摘要

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. (C) 2017 Elsevier B.V. All rights reserved.