一些生物信息学研究人员观察到两个不同物种的基因序列可能其中一个是另一个经过分段之后的重组。人们也提出了不同的可能的重组方式，我们稍后会介绍其中三种：对换（transposition），块交换（block-interchange）, 反转（reversal）。研究人员认为，一个物种的基因序列经过一定次数的某种重组方式变到另一个物种的基因序列所经过的次数越少，可能反映两个物种在进化意义上比较接近。

基于以上描述的基因序列重组问题，人们研究了如下数字序列重组距离问题。给{1，2，…，n} 这n个数的一个任意序列（排序），如果交换该序列里相邻的两个片段（片段长度不做限制），我们称对该序列做了一次对换；如果不要求两个片段相邻，我们称对该序列做了一次块交换。将该序列通过一系列对换变成12…n（即从小到大的排列）所需要的最少对换次数称之为该序列的对换距离，块交换距离类似定义。块交换距离问题实际上比对换距离问题简单些。

例：假设n=7，给定的序列为 3521764。对换其217和64片段，可得新序列3564217；块交换其52和64片段，可得新序列3641752。

注意到，3521764à3564217à3456217à3456721à2134567à1234567，说明序列3521764的对换距离应该不超过5，具体是多少呢？感兴趣的朋友自己可以动手试一下。

Bafna和Pevzner在1995年SODA会议上提出所谓圈图模型（cycle graph）给出了对换距离的一个下界，该论文目前引用次数近千次。1996年Christie给出了块交换距离的精确计算公式。对换距离至今也没有精确计算公式。

利用我们提出的平面置换（plane permutation）模型，我们把各种距离下界表示成了一个求最大值问题。以对换距离为例，我们的结果如下：

其中，td(s)表示序列s的对换距离，其它公式、符号细节见论文。而上面介绍的Bafna-Pevzner下界仅对应于我们最大值问题优化范围内的某个具体的 gamma 确定的值。显然，我们的下界理论上更好。该结果发表在《SIAM Journal on Discrete Mathematics》期刊上。遗憾的是，我们没能解决该优化问题，求该最大值目前仍然是一个公开问题。

反转就是把一个片段逆序排列。比如，3521764-->3524671。序列的反转距离类似定义。

鲜为人知的是，微软的比尔.盖茨在读书的时候研究过该问题的一个特殊情形，也称之为煎饼排序，即被反转的片段要求只能从序列的首位开始。例：3521764-->1253764-->5213764-->… 比尔.盖茨就此问题发表了一篇论文，他论文里提出的方法目前好像还是最有效的煎饼排序算法。