随着快速测序技术的发展,基因组重组排序已经成为计算生物学的一个重要研究领域。其研究的目标是寻找最短的重组操作序列,将一种基因组转变为另一种基因组。基于分子生物学家的实验数据表明,基因组重组是生物进化的一种普遍模式,也是衡量不同生物之间亲缘关系的一种重要手段。存在三种典型的基因组重组操作:反转(reversal)、转位(transposition)和移位(translocation)。其中,反转与转位操作作用在单条染色体上,而移位操作则作用在两条染色体上。过去,人们主要关注于单一重组操作的基因组重组排序问题,而对于多种混合重组操作的基因组重组排序问题的研究则相对较为缓慢。目前,对于无符号排列的反转和转位排序问题,娄晓文和朱大铭给出了一个2.25近似度的算法;对于有向基因组的反转和转位排序问题,Hartman和Sharan给出了一个1.5近似度的算法。本文首先讨论了经典的有向基因组的反转和转位排序问题,并介绍了Hartman的1.5近似度算法。此外,本文考虑重组操作的所花费的费用,引入了有向基因组重组排序的最小权重问题。其目标为求解花费最少费用的重组操作序列,使一个基因组转变成另一个基因组。对于该问题,本文给出了一个1.5k近似度的算法。本文的创新点主要有4个:1.考虑了重组操作的所花费的费用,提出了有向基因组反转和转位排序的最小权重问题,并分析了该问题的背景和研究价值;2.对于该问题,证明了一个下界;3.基于这个下界,给出了该问题的一个1.5k近似度的算法,其中k是一个常数,且k≥1;4.给出了有向基因组反转和转位排序问题的1.5近似度算法和有向基因组反转和转位排序的最小权重问题的1.5k近似度算法的C++实现。