论文部分内容阅读
随着基因测序技术的飞速发展，对大规模DNA分子的研究与它们的基因序列密切相关。基因组重组排序已经成为计算生物学和生物信息学的重要研究领域。许多研究表明，基因组重组是生物进化的一种普遍模式，也是植物、哺乳动物及细菌等呈现多样性的主要原因之一。 有三种典型的基因组重组操作：反转(Reversal)、移位(Translocation)和转位(Transposition)，一次重组将一个基因组转化为一个新基因组。反转与转位操作总是作用在单条染色体上，而移位操作则作用在两条染色体上。给定两个基因组，重组排序问题是要计算一个重组操作序列，将其中一个基因组转化为另一个，并使得重组操作次数最少。基于分子生物学积累的实验数据验证，重组操作次数最少的操作序列被认为是能较好地估计物种间的亲缘关系，有助于推断生物的实际进化过程。 基因组是一组染色体的集合，一条染色体是一个基因序列，表示为一个整数序列。每个基因都有方向。当每个基因的符号都是已知的时候，用带符号的整数表示有向基因组中的基因。当基因符号都是未知时，用正整数表示无向基因组中的基因。对于有向基因组的重组排序问题，重组排序操作在改变基因序列的同时也改变基因的符号；对于无向基因组的重组排序问题，重组排序操作只改变基因序列，不会改变基因的符号。 对于有向基因组的移位排序问题，Hannenhalli设计出O(n~3)多项式时间精确算法，并给出有向移位距离的求解公式。随后，Zhu等将算法的时间复杂度改进为O(n~2logn)，Wang等进一步改进为O(n~2)。Zhu等证明无向基因组移位排序问题也是NP-hard问题。Kececioglu和Ravi给出一个近似度为2的贪心算法，是目前该问题的最好算法。虽然有向基因组的移位排序已经有一些多项式时间算法，但是许多基因组数据并未给出基因方向，因此研究无向移位排序算法也具有十分重要的价值。 本文主要研究无向基因组的移位排序问题，即给定两个无向基因组，求最少次数的移位操作序列，将其中一个基因组转换为另一个。移位操作是将两条染色体分别断开，再重新连接成两条新的染色体。移位操作又可分为前前移位和前后移位两种，前前移位不改变基因的符号，而前后移位可能会将基因的符号取反。