Improved Approximation Algorithm and Hardness Result for Sorting Unsigned Strings by Symmetric Reversals
摘要
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)\) .