论文部分内容阅读
基因组重排问题中的反转排序(Sorting by reversals)是研究基因组进化的一种重要模式,因而成为计算分子生物学中被广泛研究的一个重要问题.该问题分为两类:基因有方向的基因组重排的反转排序问题和基因无方向的基因组重排的反转排序问题.前者是多项式时间可解的,而且目前已存在线性时间的快速求解算法;后者已经证明是NP困难问题,因而只能寻求有效的近似算法.该文主要研究基因无方向的基因组重排的反转排序问题,提出了两个求解此问题的近似算法.一个是基于断点图理论而给出的一种启发式算法,它是对Kececioglu和Sankoff(1995)近似算法的一种改进.另一个是基于"一个无向排列π的反转距离等于由π所生成的包含2个有向排列集Sign(π)中最优排列的反转距离"这一事实而设计的求Sign(π)中最优排列的一种遗传模拟退火算法.全文共分四章.作为基础,前两章阐述了该课题研究的意义、当前的研究现状和该课题研究的基础知识.第三和第四两章是该文的主要工作.第三章首先定义了一种新的断点图,并基于这种断点图给出了一个反转可消去排列中一个断点和两个断点的充要条件,设计出一个时间复杂性为O(max{b<3>(π),nb(π)}),空间复杂性为O(n)的启发式算法.其中n为基因组中基因个数,π=(π<,1>,π<,2>,…,π<,n>)表示n个基因的一种排列,b(π)表示排列π中的断点数.数据实验的结果表明,在多数情况下,该算法优于Kececioglu和Sankoff(1995)提出的近似算法.第四章鉴于有向排列的反转基因组重排问题已存在快速有效的精确算法,为此,我们通过对包含n个元素的无向排列π作变换,生成一个包含2个有向排列集Sign(π),并证明π的反转距离就等于Sign(π)中最优排列的反转距离.然后设计出求Sign(π)中最优排列反转距离的遗传模拟退火算法,给出适合于此问题的编码方案,定义了解的邻域结构和相应的交叉算子及变异算子.数据实验的结果表明该算法性能优于Christie(2001)的3/2-近似算法.