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

Sorting binary strings with length weighted transpositions

提出了对换排序的赋权模型,定义一个长度为l的对换的费用是f(l)=lα,α>0;分别给出了当0<α<1和1<α<2时,二元序列赋权对换排序问题的近似算法;证明了当α2时,起泡排序算法是此问题的精确算法.

The problem of sorting binary strings with length-weighted transpositions is considered, i.e. the cost of a transposition of length l is f（l） =l^n, α 〉 0, rather than 1. Approximation algorithms are given for 0 〈 α 〈 1 and 1 〈 α 〈 2 respectively, and bubble sort is proved to be an exact algorithm for this problem when α ≥ 2. The results have direct applications in computational biology to the field of comparative genomics.