.png){kind=icon}
Return
Flanked Block-Interchange Distance on Strings
.png){kind=icon}
PRE
AI
DOI：10.1109/TCBB.2024.3351440.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Rearrangement sorting problems impact profoundly in measuring genome similarities and tracing historic scenarios of species. However, recent studies on genome rearrangement mechanisms disclosed a statistically significant evidence, repeats are situated at the ends of rearrangement relevant segments and stay unchanged before and after rearrangements.To reflect the principle behind this evidence, we propose flanked block-interchange, an operation on strings that exchanges two substrings flanked by identical left and right symbols in a string. The flanked block-interchange distance problem is formulated as finding a shortest sequence of flanked block-interchanges to transform a string into the other. We propose a sufficient and necessary condition for deciding whether two strings can be transformed into each other by flanked block-interchanges. This condition is linear time verifiable. Under this condition for two strings, we present a $\text{4}\,k$4k-approximation algorithm for the flanked block-interchange distance problem where each symbol occurs at most $k$k times in a string and a polynomial algorithm for this problem where each symbol occurs at most twice in a string. We show that the problem of flanked block-interchange distance is NP-hard at last.
Keywords:
Algorithm
complexity
flanked block-interchange
genome
rearrangement
string
Journal
I
IF:
3.4
Papers:
3.3K
Citations:
6.4K
Organization
View more organizations
Cited Papers
ShareSaveA new bio-based thermosetting with amorphous state, sub-zero softening point and high curing efficiency.png)
Polymer
PolymerIF0
PREAI
ShareSaveShareSaveShareSaveVisual cortex ablation and thresholds for successively presented stimuli in rhesus monkeys: II. Hue
PREAI
ShareSaveShareSave
ShareSaveShareSave View more