Flanked Transposition Distance for Two Strings

doi:10.1109/TCBBIO.2025.3608066

2025-11-01

PRE

DOI：10.1109/TCBBIO.2025.3608066

原文链接

原文求助

摘要

En 中文

Transposition is a well-known genome rearrangement event that switches two consecutive sub-strings on a string. Since a transposition makes changes to a string, the genome here is just a string. The problem of transforming one string into the other by a sequence of transposition operations has attracted a lot of attention. However, it has been reported that genome rearrangement events are often associated with repeated sub-strings. In particular, a transposition operation is most likely associated with three identical repeated sub-strings. A transposition operation on two consecutive sub-strings x and y switches the two sub-strings and transforms the whole string zxyw into the other string zyxw, where z and w represents the two sub-strings on the left and right of xy, respectively. When repeated sub-strings are considered, the two consecutive sub-strings x and y are flanked with three identical repeated sub-strings R and the flanked transposition transforms the whole string zRxRyRw into zRyRxRw. For a flanked transposition operation, the neighbors of x and y remain the same before and after the transposition. In this paper, we investigate the problem of transforming one string into the other by a number of flanked transpositions. First, we present a necessary and sufficient condition to determine if a string can be transformed into the other by a sequence of flanked transpositions. We then design a decision algorithm with running time O(n) to test if such a condition holds. We also show that transforming one string into the other by using minimum number of flanked transpositions is NP-hard. A string pi of n letters is simple if the n-1 consecutive pairs of letters are distinct. We present an O(n(2)) approximation algorithm with ratio 2 for the optimization version of the special case, where both input strings are simple.

Keyword:

Bioinformatics

Genomics

Approximation algorithms

Transforms

Optimization

Computational biology

Urban areas

Training

Switches

Sufficient conditions

Genome rearrangement