摘要: 1．本文的创新点
　　基因组重组排序问题是指使用最少的重组操作（如反转、转位、带有反转的转位等）将一个基因组转变成另一个基因组，该问题等价于将一个排列排序为恒等排列。已经证明，无符号排列反转排序问题是NP-hard问题，而有符号排列反转排序问题则有多项式时间算法。Hannenhalli和Pevzner发现单元素是无符号排列反转排序问题的主要障碍并且设计了一个针对单元素数目在O(logn)以内的无符号排列反转排序问题的多项式时间算法。本文指出该算法失败的一类情况并给出修正方案。进一步研究了用赋权的反转、转位和带有反转的转位对无符号排列排序问题，设计了权值比为1:2情况下的(1+e)近似度算法，其中排列的单元素数目同样限制在O(logn)以内。
2．实现方法
　　针对单元素数目受限的无符号排列反转排序问题，首先找到原算法失败的反例，通过研究反例的性质找出原算法失败的原因，发现将一个2-带变为反带时断点图中圈数的变化密切依赖于2-带的结构。进一步将原算法中要取反的2-带限制为一个子集，即目标2-带。在此基础上提出超-r-旋转的定义并证明无单元素排列的每个超-r-旋转都是最优-r-旋转。
针对用赋权的反转、转位和带有反转的转位对无符号排列排序问题，发现权值比为1:2情况下与反转排序问题的相似性，即对有符号排列的距离计算公式相类似。但由于赋权问题涉及到转位操作，用转位操作排序问题复杂性未知，因而断点图中存在一种特殊的结构即强无向分支给讨论带来困难，对应的赋权距离公式中的两个变量只能求得近似解。尽管目前不能在多项式时间内不能识别出强无向分支，但已经知道一个强无向分支一定是无向的。利用这个性质，在寻找最优旋转的过程中就可以确定出flip(s)操作对赋权距离的影响。通过对2-带、3-带以及距离公式中每个变量的逐步讨论，发现无单元素排列的每个超-r-旋转不仅是最优-r-旋转，也是最优-rt-旋转。在证明的基础上，利用有符号排列赋权距离问题的1+e近似度算法，通过枚举单元素符号和不等式放缩，得到了单元素数目在O(logn)以内的无符号排列赋权距离问题的1+e近似度多项式时间算法。
3．结论及未来待解决的问题
　　本文针对单元素数目受限的无符号排列，修正了反转排序问题的多项式时间算法，并设计了赋权问题的1+e近似度算法，其允许的操作为反转、转位和带有反转的转位，权值比为1:2。尽管由于强无向分支的存在我们不能在多项式时间内求得超-r-旋转的最优赋权距离和赋权方案，但是可以确切的知道该旋转是最优的。一个值得讨论的问题是是否可以设计一个针对所有无符号排列的用权值比为1:2的反转和转位\带有反转的转位排序问题的多项式时间近似算法。该问题或许比已有的用不赋权的反转和转位排序问题更有实际意义。
4．实用价值或应用前景
　　基因组重组排序问题是用于研究基因次序和基因家族进化的一个新的领域。随着快速测序技术的发展，人们可以得到大规模DNA分子中的基因的相对位序。研究表明，物种基因组之间的联系非常紧密，但在基因的排列次序上有着显著的差异。基因组重组是生物进化的一种普遍模式，也是植物、哺乳动物及细菌等呈现多样性的主要原因之一。最节俭方案是研究这类问题最常用的技术，人们设计了各种组合算法。反转操作是研究最多的重组操作，算法日臻完善。另一方面，在实际进化中，不止一种重排事件会发生，因而考虑同时用反转、转位排序问题有助于研究真正的进化模型。设计特定权值下的算法有助于人们认识实际进化中各种重组事件发生的比例和概率，以及在什么样的权值下能够得到更有意义的解。