比较基因组学是生物信息学的一个重要分支,计算两个基因组之间的量化距离是比较基因组学的基本问题,常应用于构建物种进化树、探索基因功能、分析疾病致病原理等实践中。基因组是一组染色体的集合,染色体是细胞内具有遗传性质的的物体,可以视为一个基因序列。在有向基因组中,每个基因用一个带“+”或“-”的整数表示,符号用于表示基因的方向。基因组的重组揭示了基因组改变基因排列次序的行为,在基因组重组排序问题中表述为改变基因排列次序的操作,有反转(reversal)、移位(translocation)、转位(transposation)、反转位(tranreversal)、插入(insertion)、删除(deletion)、染色体分段(fission)、染色体连接(fussion)等基本形式。我们将包含多种操作形式的基因组重组排序称为基因组的复合重组排序问题,复合重组排序问题由于更具有一般性,因而显得更有应用价值。反转操作已经被广泛承认是基因组操作中一种最普遍的操作,科学研究发现在基因组的重组演化中,还伴有插入和删除基因片段的事件,许多分子生物学实践需要人们在基因组中实施插入和删除基因片段的操作。本文首先讨论了仅基于反转操作的基因组重组全解问题,并介绍了Braga的算法框架。然后,本文对原有的经典基因组模型进行扩展,在原有数学模型的基础上增加待删除基因块用于包含临时基因。待删除基因块可以随着反转而在基因排列的不同位置出现,我们在待删除基因块每个可能出现的位置都留下一个副本,并有一个反转操作构成的路径与之对应,用于表示该副本出现在此位置所经历的反转。本文以最少重组操作为目标,将删除操作引入到基因组重组全解问题中来,并给出了一种在最少反转距离的前提下,计算基于反转和删除两种操作的基因组全解空间的算法。最后,用Java实现了该算法,并对实验结果进行了分析。