A 2-approximation algorithm for genome rearrangements by reversals and transpositions
A 2-approximation algorithm for genome rearrangements by reversals and transpositions
复制标题
DOI：
10.1016/s0304-3975(98)00092-9
复制
发表时间：
1999-01-17
影响因子：
1.1
通讯作者：
Sudborough, H
中科院分区：
文献类型：
--
作者：
Gu, QP;Peng, ST;Sudborough, H
最近，Sankoff等人提出了一种新的分析基因组进化的方法，该方法基于基因序列的比较和传统的DNA序列比较(Sankoff et al.(1992年)。该方法基于全局重排(例如，片段的反转和转置)。对由倒置和换位进化的基因组的分析导致了通过倒置和换位进行排序的组合问题，即使用任意片段的倒置和换位对排列进行排序。我们研究了通过颠倒和换位对带符号的排列进行排序，当DNA中的基因被定向时，这个问题可以充分地模拟基因组重排。我们建立了问题的下界，并给出了问题的2-近似算法。(C)1999-Elsevier Science B.V.保留所有权利。
Recently, a new approach to analyze genomes evolving which is based on comparision of gene orders versus traditional comparision of DNA sequences was proposed (Sankoff et al. 1992). The approach is based on the global rearrangements (e.g., inversions and transpositions of fragments). Analysis of genomes evolving by inversions and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, i.e., sorting of a permutation using reversals and transpositions of arbitrary fragments. We study sorting of signed permutations by reversals and transpositions, a problem which adequately models genome rearrangements, as the genes in DNA are oriented. We establish a lower bound and give a 2-approximation algorithm for the problem. (C) 1999-Elsevier Science B.V. All rights reserved.