Sorting circular binary strings with length weighted transpositions
Zhang Chen · Journal of Shandong University · 2007
The problem of sorting circular binary strings with length-weighted transpositions was considered,i.e.the cost of a transposition is f(l)=lα,0≤α1,where l is the length of the transposition.An O(log n)-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.