.png){kind=icon}
返回
Flanked Block-Interchange Distance on Strings
.png){kind=icon}
PRE
AI
DOI：10.1109/TCBB.2024.3351440.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Algorithm
complexity
flanked block-interchange
genome
rearrangement
string
期刊
I
IF:
3.4
论文数:
3.3K
被引数:
6.4K
机构
引用论文
A new bio-based thermosetting with amorphous state, sub-zero softening point and high curing efficiency一种新型的生物基热固性材料，具有非晶态，零下软化点和高固化效率.png)
Polymer
PolymerIF0
PREAI
分享收藏分享收藏分享收藏Visual cortex ablation and thresholds for successively presented stimuli in rhesus monkeys: II. Hue
PREAI
分享收藏
查看更多内容