An efficient algorithm for computing non-overlapping inversion and transposition distance

作者：Ta Toan Thang; Lin Cheng Yao; Lu Chin Lung^*

来源：Information Processing Letters, 2016, 116(12): 744-749.

DOI：10.1016/j.ipl.2016.07.004

• Algorithms
• Computational biology
• Inversion
• Transposition
• Mutation distance

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.

• 出版日期2016-12
• 单位清华大学