反序排序

1、基因组中基因的次序可用一个排序π=π1π2...πn表示。

2、反序作用是倒换同线性块

π1πi+1...πj-1πj 的次序

实际上，反序ρ(i,j)将

π1。。。πi-1 πiπi+1...πj-1πj πj+1。。。πn

变换成

π1。。。πi-1 πjπj-1 ...πi+1πi πj+1。。。πn

3、反序距离问题

给定两个排列，寻找一个最短的反序序列使得它们能将一个排列变换成另一个排列。

输入：排列π和б

输出：将排列π和б变换成б的一系列反序(即π*ρ1*ρ2...ρt=σ)，并使得t是最小的

4、反序排序问题

给定一个排列，，寻找一个能将此排列变换成恒等排列的最短的反序序列。

输入：排列π

输出：将排列π变换成恒等排列的一系列反序ρ1,ρ2,...,ρt，并使得t最小