计算生物学是现今世界的热门学科,计算生物学研究的有关成果直接影响着人类在生物进化、基因制药等领域的研究进展.生物学、化学、数学、计算机科学等各领域专家学者都在关注着计算生物学的发展.基因重组对于计算机科学理论研究来说,其基本课题是基因组距离的计算问题,以及基于基因组距离计算的进化树问题.基因组距离主要为基因序列之间的Reversal距离(R_距离、翻转距离)和基因组之间的Translocation距离(T_距离).目前,基于基因组距离计算的各种进化树问题是理论研究的热点与难点<[20-26]>.Reversal和Translocation均是十分复杂的生物进化过程,Sankoff将这些过程归结为简单的基因组重组模型,提出Reversal排序和Translocation排序问题,并统称为基因组重组排序问题<[18,19]>.该文就与基因组重组排序有关的距离计算问题进行研究,得到三个主要结果:(1)证明基于基因组Reversal距离的星树问题是NP难解的,证明该问题不存在绝对近似算法,并给出一个该问题的近似性能比为2的近似算法<[27]>.(2)进一步研究证明固定基因序列符号顺序的3叶星树问题是NP难解的,并给出近似性能比为6的近似算法<[28,29]>.(3)在基因组Translocation距离计算研究中,给出一个改进了的多项式时间算法.