.png){kind=icon}
返回
Improved Approximation Algorithm and Hardness Result for Sorting Unsigned Strings by Symmetric Reversals
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0218-9_25.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
结构变异被广泛认为是遗传变异的重要来源。作为结构变异的一种已知类型，反转被生物学家和计算机科学家广泛研究。最近，科学家发现染色体上发生反转的片段末端通常出现重复序列，这激发了对于无符号染色体对称反转排序模型（简称MUSR）的新兴趣。MUSR问题要求找到将染色体S转换为染色体T所需的最少无符号对称反转次数，并要求对称反转操作在由相同字母界定的片段上进行。本文通过从MAX-(3,B2)-SAT问题进行复杂归约，证明了MUSR问题是NP难的。此外，我们提供了最优解的创新性描述，并开发了一种改进的近似算法，确保近似比为2 ln3+7/8（约1.15），时间复杂度为O(n²)。
Keyword:
Symmetric reversals
Approximation algorithms
NP-hard
期刊
C
IF:
0
论文数:
24
被引数:
0
机构
引用论文
Distinct retroelement classes define evolutionary breakpoints demarcating sites of evolutionary novelty.png)
BMC GENOMICS
OAAI
BMC GENOMICSIF3.7
OAAI分享收藏
查看更多内容