It is widely recognized that structural variation represents a significant source of genetic variation. As a well-known type of structural variation, reversion is studied drastically by both biologists and computer scientists. Recently, scientists have found that repetitive sequences always appear at the ends of the segment where the reversal occurred on the chromosome, which has inspired new interests in models for sorting unsigned chromosomes by symmetric reversals (abbreviated MUSR). The problem of MUSR asks for a minimum number of unsigned symmetric reversals to transform a chromosome S into another chromosome T, and requires symmetric reversals to be performed on the segment flanked by the same letter. In this paper, we show that MUSR is NP-hard through an intricate reduction from the MAX-(3,B2)-SAT problem. Moreover, we provide an innovative depiction of the optimal solution and then develop an improved approximation algorithm that ensures the approximation factor of \(\frac{2\ln 3+7}{8}\) (approximately 1.15) and a time complexity of \(O(n^2)\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Improved Approximation Algorithm and Hardness Result for Sorting Unsigned Strings by Symmetric Reversals

  • Wenfeng Lai,
  • Haitao Jiang,
  • Daming Zhu,
  • Binhai Zhu

摘要

It is widely recognized that structural variation represents a significant source of genetic variation. As a well-known type of structural variation, reversion is studied drastically by both biologists and computer scientists. Recently, scientists have found that repetitive sequences always appear at the ends of the segment where the reversal occurred on the chromosome, which has inspired new interests in models for sorting unsigned chromosomes by symmetric reversals (abbreviated MUSR). The problem of MUSR asks for a minimum number of unsigned symmetric reversals to transform a chromosome S into another chromosome T, and requires symmetric reversals to be performed on the segment flanked by the same letter. In this paper, we show that MUSR is NP-hard through an intricate reduction from the MAX-(3,B2)-SAT problem. Moreover, we provide an innovative depiction of the optimal solution and then develop an improved approximation algorithm that ensures the approximation factor of \(\frac{2\ln 3+7}{8}\) (approximately 1.15) and a time complexity of \(O(n^2)\) .