计算生物学是一门应用计算机技术对生物数据进行存储、解析、建模和计算,并从中获取生物信息的学科。计算生物学根据研究数据的类别又分为计算基因组学、计算蛋白组学和计算转录组学等。计算机基因组学研究者通常将基因组学中的生物问题抽象为组合优化问题,从而运用解决组合优化问题的方法来求解。组合优化问题属于最优化问题的范畴,即从组合问题的可行解集中求出最优解。然而,这些优化问题往往是比较难解的。因此,计算基因组学中绝大部分问题都是NP-Hard 的。计算基因组学中的研究内容一般包括基因组测序技术、组装算法、基因组之间的比较和基因组重组等,而基因组框架填充是计算基因组学中新兴的热门研究领域之一。基因组框架填充问题分为有重复基因和无重复基因两类。无重复基因的基因组框架填充问题比较简单,是多项式时间可计算的。而有重复基因的基因组框架填充却是比较难解的。很多有重复基因的基因组框架填充的变种问题已被证明是NP-Hard的,所以在P不等于NP的前提下不存在多项式时间算法。因此,研究者大多致力于设计和分析这些问题的多项式时间近似算法,希望在可接受的时间内获得一个较好的可行解。基因组框架填充问题根据给定的框架是否含有参考基因组,分为单面和双面的基因组框架填充问题。如果给定的两个框架中有一个是完整的参考基因组,即存在一个邻近物种的全基因组作为参考,则称之为单面基因组框架填充。否则,称之为双面基因组框架填充。无论是单面还是双面的基因组框架填充,如果含有重复基因,则大多数情况下都不存在多项式精确算法。在基因组组装不完全依赖全基因组测序的趋势下,基因组框架填充的目标是将缺失基因填充到不完整的基因组序列中以得到与原始基因组相近的替代基因组,从而有效改善基因组组装的结果,降低全基因组测序的成本。衡量基因组框架填充后的序列与原始基因组相似性的标准有很多,比较典型的有基因组重组距离、抽样断点距离、断点数、公共划分和公共邻接数等。由于断点数和公共邻接数本身计算的简单性,近年来基因组框架填充问题的模型大多以最小化断点数和最大化邻接数为优化目标。本文针对以最大化邻接数为目标的基因组框架填充问题,精确解析了其最优解的结构,并通过构造冲突图,将求插入串转换为在冲突图中求最大独立集问题,从而设计了一个多项式时间近似算法,将近似比由原先的1.5改进到了 1.4+ε。另外,本文首次将保留有序对引入到基因组框架填充问题,提出一个基因组框架填充问题的新模型,即块匹配模型,研究了以最大化保留有序对增加数为目标的基因组框架填充问题。通过分析大量实例,研究了其复杂性和不可近似性,设计了一个特殊情况下的线性精确算法和三个一般情况下的多项式时间近似算法。本文的主要研究工作和创新点总结如下:1、准确解析以最大化邻接数为目标的基因组框架填充问题的最优解本文通过分析大量实例,对基于最大匹配,以最大化邻接数为目标的基因组框架填充问题的最优解展开研究。通过找到插入串之间的相关关系,引入相关图（Relevant Graph）和路径分支（Path Component）的概念,将由缺失基因组成的,且必须要作为一个整体插入的若干个缺失基因串表示为一条路径分支。如果两条路径分支相互影响,则意味着两个缺失基因串集合在插入的时候相互影响,因此可以通过一定的方法将其合并为一条路径分支,使两个插入串集合并为一个。进而将合并后的插入串集中的所有基因串同时插入到对应的位置,得到更多的邻接。通过严格的证明,本文将任意一个最优解转换为一个具备最少路径分支数的特殊最优解。通过分析该最优解的结构,求得了最优解中邻接数的上界。这项工作为后续近似算法的设计和近似比的证明奠定了基础。2、设计了以最大化邻接数为目标的双面基因组框架填充问题的1.4+ε-近似算法已知,以最大化邻接数为目标的基因组框架填充问题是NP-Hard的。目前双面基因组框架填充问题最好的近似算法的近似比能达到1.5。本文针对基于最大匹配,以最大化邻接数为目标的双面基因组框架填充问题（Two-Sided Scaffold Filling to Maximize Number of Common Adjacencies,简称 TSSF-MNCA）,设计了近似比为1.4+ε的多项式时间近似算法。该近似算法通过构造具有特殊性质的冲突图,证明冲突图是一个k-Claw Free图,把求插入串的问题转换为在k-Claw Free图中求最大独立集的问题。从而,利用Halldórsson设计的求独立集的多项式时间算法,求得足够的完美插入串。通过严格的证明和分析,本文得到该近似算法的近似比为1.4+ε,其中ε为大于0的常数。3、设计了特殊情况下的以最大化基因组保留有序对增加数为目标的单面基因组框架填充问题的精确算法考虑到以最大化邻接数的模型已经难以满足生物数据分析中的实际需求,本文将保留有序对引入到基因组框架填充问题中,并提出了一个基因组框架填充问题的新模型,即基于块匹配的以最大化保留有序对数为目标的基因组框架填充。用保留有序对数来描述填充后序列的相似性可以使结果更准确。本文主要研究了特殊情况下的基于块匹配模型,以最大化保留有序对增加数为目标的单面基因组框架填充问题（One-Sided Scaffold Filling to Maximize Increased Duo-preservations,简称OSSF-MIDP）。通过对其大量实例进行分析,发现了 OSSF-MIDP问题的一种特殊情况,记为Sim-OSSF-MIDP问题。在Sim-OSSF-MIDP问题中,框架中不存在未匹配的基因。本文为其设计了一个时间复杂度为O（n）的精确算法,证明了 Sim-OSSF-MIDP问题是多项式可计算的,甚至是线性可计算的。4、分析了一般情况下的以最大化基因组保留有序对增加数为目标的单面基因组框架填充问题的复杂性和不可近似性本文主要研究了一般情况下的基于块匹配的以最大化保留有序对增加数为目标的单面基因组框架填充问题（OSSF-MIDP）的复杂性。通过构造一个从MAX SNP-Complete问题,即3DM的变种问题（（3DM-2）1）到OSSF-MIDP问题的L-归约,证明了 OSSF-MIDP 是 NP-Hard 的,甚至是 MAX SNP-Complete 的。由此证明,OSSF-MIDP问题不存在多项式时间近似方案。与此同时,本文还研究了 OSSF-MIDP问题的不可近似性,通过利用（（3DM-2）1）问题的一个不可近似界,证明了 OSSF-MIDP问题不可近似到16263/16262以内。5、设计了一般情况下的以最大化基因组保留有序对增加数为目标的单面基因组框架填充问题的3个多项式时间近似算法本文针对一般情况下的OSSF-MIDP问题,求得了该问题最优解的上界,并设计了 3个多项式时间近似算法。通过设计一个近似比为2的基本算法,保证了增加的保留有序对的个数恰好与插入的缺失基因个数相等。以此为基础,得到了最优解的公式表达,并求得其中的一个上界。然后,应用贪心策略,设计了一个近似比为12/7的多项式时间近似算法;应用局部搜索技术,设计了一个近似比为14/9的多项式时间近似算法。