论文部分内容阅读
近年来,随着基因测序技术的发展,人们能够获得越来越多生物体的基因组,然而这些基因组并不完整。不完整的基因组被称为基因组框架。在很多计算生物学研究领域,无法直接使用基因组框架进行科学研究,可行的方法是将其补充完整再投入应用,基因组片段填充问题由此产生,并逐渐成为计算生物学的一个热门研究领域。片段填充问题通过参照相近物种的基因组来填充基因组框架,目的是使基因组框架变得完整并尽量接近原始的基因组信息。根据参照基因组的完整与否,片段填充问题又细分为单面填充和双面填充。在本文中,用一个字符表示一个基因家族,用字符串表示基因组。当基因组中不包含重复出现的基因时,片段填充问题在断点距离或DCJ距离下都是多项式时间可解的；当基因组包含重复出现的基因时,片段填充问题在断点距离或公共邻接距离下都是NP-完全的。目前主要的研究都集中在一般情况下的包含重复基因的基因组片段填充问题上,即允许在基因组框架的同一个位置上连续填充任意多个基因。但是在实际的基因组填充计算中,在同一个位置连续填充多个基因的情况并不多见,往往是在一个位置上填充1或2个基因,因此本文考虑下面的问题：在包含重复基因的基因组片段填充问题中,以公共邻接数目作为基因组之间距离的度量,以最大化公共邻接数为目的,如果填充长度为l的字符串到基因组框架的同一位置使得公共邻接数增加l+1,则l的取值仅为1或2。本文将该问题简称为SF-MNCA(2)(Scaffold Filling to Maximize the Number of Common Adjacencies)。文中对SF-MNCA(2)(?)司题进行了研究讨论。本文的主要贡献如下：(1)证明了SF-MNCA(2)是NP-完全问题。本文采用NP-完全性的理论证明方法,通过理论分析,找到适合用于归约的已知NP-完全问题：3DM,通过将3DM问题在多项式时间内归约为单面SF-MNCA(2)(?)司题,首次证明了单面SF-MNCA(2)是NP-完全的。(2)为单面SF-MNCA问题设计了简单的2-近似算法。本文给出了该算法的流程和详细的正确性证明,为后续算法的设计奠定了理论依据,具有很高的理论意义。(3)为单面SF-MNCA(2)(?)问题设计了6/5+ε-近似算法。本文在单面SF-MNCA的2-近似算法的基础上,采用局部搜索技术设计单面SF-MNCA(2)(?)问题的6/5+ε-近似算法,给出了算法流程、时间复杂度的分析和近似性能比的证明。