Flanked Transposition Distance for Two Strings
IEEE Transactions on Computational Biology and Bioinformatics · 2025
DOI: 10.1109/tcbbio.2025.3608066 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Computational Biology and Bioinformatics, 2025. Verfasst von Huixiu Xu und 5 weiteren Autor:innen. Hauptthemen laut MEDLINE: Models, Genetic, Gene Rearrangement, Genome, Genomics. Die Arbeit nennt 32 Literaturangaben. Gefördert von: Nature Science Foundation of China, Joint Funds of the National Nature Science Foundation of China, General Research funds.
Abstract (Originalsprache)
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 $\mathcal {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 $\mathcal {O}(n^{2})$ approximation algorithm with ratio 2 for the optimization version of the special case, where both input strings are simple.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Förderung
- Nature Science Foundation of China
- Joint Funds of the National Nature Science Foundation of China
- General Research funds
Zitieren
APA
Xu, H., Tong, X., Jiang, H., Wang, L., Zhu, B., & Zhu, D. (2025). Flanked Transposition Distance for Two Strings. IEEE Transactions on Computational Biology and Bioinformatics. https://doi.org/10.1109/tcbbio.2025.3608066
Vancouver
Xu H, Tong X, Jiang H, Wang L, Zhu B, Zhu D. Flanked Transposition Distance for Two Strings. IEEE Transactions on Computational Biology and Bioinformatics. 2025. doi:10.1109/tcbbio.2025.3608066
BibTeX
@article{Xu2025,
author = {Xu, Huixiu and Tong, Xin and Jiang, Haitao and Wang, Lusheng and Zhu, Binhai and Zhu, Daming},
title = {Flanked Transposition Distance for Two Strings},
journal = {IEEE Transactions on Computational Biology and Bioinformatics},
year = {2025},
doi = {10.1109/tcbbio.2025.3608066}
}
EUVIMED