.png){kind=icon}
.png){kind=icon}
Return
Flanked Transposition Distance for Two Strings
.png){kind=icon}
PRE
AI
DOI：10.1109/TCBBIO.2025.3608066.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Bioinformatics
Genomics
Approximation algorithms
Transforms
Optimization
Computational biology
Urban areas
Training
Switches
Sufficient conditions
Genome rearrangement
flanked transpositions
decision algorithm
NP-hard
Journal
I
IF:
0
Papers:
151
Citations:
0