环型二元序列的赋权对换排序问题

Sorting circular binary strings with length weighted transpositions

研究了环型二元序列的赋权对换排序问题。定义一个长度为l的对换的费用是f(l)=lα,0≤α<1,对环型二元序列的赋权对换排序问题给出了一个O(logn)-近似算法,其中n是环型二元序列的长度。

The problem of sorting circular binary strings with length-weighted transpositions was considered, i.e. the cost of a transposition is f（l）=l^a,0≤α〈1, where l is the length of the transposition. An O（logn）-approximation algorithm is given for sorting a circular binary string with the minimum cost, where n is the length of the circular string. The result has direct applications in computational biology in the field of comparative genomics.