生物的遗传物质随着进化而改变.相对于序列水平的点突变，越来越多的研究更加关注基因组水平的较大的变化.计算分子生物学中的基因组重排，产生了借助于反序来排列有符号排列问题.给定由相同元素构成的代表基因组的两个有符号排列，问题在于找到由一个基因组转化成另一个基因组的最简约的反序排序方案. 目前，基于基因组重排的进化方案的重构已经成为理解相近物种间进化关系的有力工具，尤其对于哺乳动物的研究.例如，在过去的两年中人们已经借助于MGR和GRIMM软件得到了大鼠与人以及最近新测序的挪威鼠之间的几个比较有趣的进化方案.本文比较感兴趣的是不破坏组合结构(即基因组保守块)的方案.事实上，如果两个基因组拥有共同特征，那么它们的祖先很可能也拥有这一特征，这就使研究保持这一特征的进化方案更有价值. 本文中考虑的组合结构即代表两个基因组的排列的共有区间.首先，对HP理论中提及的交叉图做了重新描述和更加简单的构造，将新得到的交叉图用于基因组重排的交换方案问题的研究，得到了与Berard和Bergeron在文献相同的结论.并在此基础上提出了非交换方案的概念，同时对非交换方案转换成交换方案做了一定的研究. 然而，由于基因组进化过程的最优交换方案是一类特殊的完美方案，而一个完美方案并不一定是最优的.因此，人们更加关注的是基因组进化过程中，是否存在一般的完美方案和最优完美方案的问题.本文在Kaplan，Shamir和Tarjan等人提出的反序排序有符号排列算法基础上，加入了对保持共有区间问题的探讨，改进了KST算法.通过对排序定向分支和不定向分支得到的反序与排列的共有区间进行比较，确定得到的反序是否保持排列的共有区间.在此基础上给出一个多项式时间算法，判定一个排列能否被一个最优的完美方案进行排序.从而在一定意义上很好地解决了基因组进化过程中的最优完美方案问题.