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

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

Sorting binary strings with length weighted transpositions

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^α, α＞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.