学位论文 > 优秀研究生学位论文题录展示

基因组片段填充问题的算法研究

作　者: 柳楠
导　师: 朱大铭
学　校: 山东大学
专　业: 计算机软件与理论
关键词: 片段填充近似算法基因组公共邻接
分类号: TP301.6
类　型: 博士论文
年　份: 2013年
下　载: 188次
引　用: 0次
阅　读: 论文下载

内容摘要

基因组片段填充问题是隶属于计算基因组学范畴的新组合优化问题。计算基因组学是一门运用计算机技术和信息技术对基因组研究数据进行分析、建模和计算,从中获取生物信息的学科。组合优化是从组合问题的可行解中求出最优解,这些组合问题往往具有问题描述简单,但最优化求解很困难的特征,比如有名的货郎问题、装箱问题、图着色问题,基因组片段填充问题便是新兴的组合优化问题之一。计算基因组学较为经典的研究领域包括基因组测序与组装(拼接)、基因组比较、基因组重组等问题。已有的结论表明,计算基因组学中的大部分问题是NP-难的,含重复基因的基因组片段填充问题也不例外。而对于这些NP-难的问题,设计和分析多项式时间近似算法具有较好的可行性和理论意义。生物测序技术不断迅速发展,产生了第一代、第二代(下一代,NGS)和第三代测序技术,人们能够在更短的时间内获得大规模的测序数据,测序的长度、深度和覆盖率有很大提高。目前,大部分基因组的完整序列仍难于通过生物测序方式直接获得,需要计算机技术相关的组装软件完成测序片段的组装。但由于测序片段的覆盖情况和组装软件的局限性,组装的最终结果往往也不是基因组的完整序列,而是以片段的形式发布。比较典型的片段包括基因组框架(Scaffold)形式和片段重叠群(Contig)形式。若直接使用这些不完整的基因组片段形式进行生物问题的分析和研究,必将影响研究结果的准确性。因此,使用基因组片段填充技术将缺失的基因填充到不完整的基因组片段中,能够提高基因组最终序列的完整性和准确性,节省全基因组生物测序成本。根据提高基因组最终序列完整性的实际需求,H. Jiang等在Sankoff等首次提出单面片段填充问题的基础上抽象出了针对基因组框架形式的片段填充问题模型,即给定一个基因集合∑,基于该基因集合的两个输入框架序列A和B,缺失基因集合X=c(B)-c(A), Y=c(A)-c(B),将集合X和Y中的缺失基因分别插入A和B中获得序列A’和B’,计算A’和B’之间的距离使之满足相应的条件。其中,距离的类型包括：基因组重组距离(二次切割与连接)、断点距离、基因抽样距离、公共子串划分距离、邻接距离等。除了基于邻接距离的片段填充问题的目标是最大化该距离,基于其他距离的片段填充问题都是最小化的目标。根据输入的基因片段中是否包含重复基因,该问题可以分为基于排列的片段填充和基于序列的片段填充。若输入的两个基因片段都是不完备的(包含缺失基因),则该问题称为双面基因组片段填充问题；若输入的两个基因组片段中有一个是完备的(不包含缺失基因),则该问题称为单面基因组片段填充问题。本文主要研究的问题包括单、双面含重复基因的基于最大化邻接的基因组片段填充问题。此外,本文还研究了基因组片段填充问题之前的环节——序列拼接中信息约减的问题,即在使用拼接软件进行序列拼接前,在不影响最终拼接结果的前提下,约减冗余原始测序数据,从而提高序列拼接效率。本文的主要创新点：1.首次提出修改基于最大化邻接的基因组片段填充问题的标准定义。在基于最大化邻接的基因组片段填充问题的标准定义中,问题实例即问题输入中包含两条Scaffold序列,倘若直接使用给出的原始序列,则在实施基因插入操作过程中无法保证每次插入基因都会产生新的邻接。而在H. Jiang的1.33-近似算法及本文的近似算法中,基因的插入都是根据是否产生相应数量的新邻接。添加封闭符号“#”能够解决序列端点基因的不公平待遇现象,即每个序列端点基因只具有一个邻接基因来产生断点或邻接的问题,确保基因插入序列时一定存在每个插入的基因至少产生一个新邻接的插入方法,同时保证了插入所有缺失基因后的两条序列之间的邻接数和断点数相同。2.针对最大化邻接的基因组片段填充问题的特殊实例,提出了一个多项式时间精确算法。基于断点距离、二次切割与连接距离及最大化邻接距离的无符号包含重复基因的基因组片段填充问题,已经被证明是NP-完全问题,因此不存在多项式时间精确算法。但对于这些问题中的某些特殊实例,人们能够找到解决它们的多项式时间精确算法。本文发现针对最大化邻接的基因组片段填充问题中存在一类特殊实例,能够通过多项式时间算法计算出最优解。因为基因组片段填充问题的最终目标是使结果序列之间产生最多的邻接,即每次插入基因能够尽可能多的消除序列中存在的断点。因此,本文对每条序列中存在的断点进行研究,按照组成断点的基因所属的位置划分成三种类型的断点集合,并确定当输入序列中不存在这样的断点：一个基因属于待插入基因集合,一个基因属于待插入序列的某个断点时,基于最大化邻接的基因组片段填充问题存在一个多项式时间精确算法。该多项式算法的时间复杂度为O(n3)。本文严谨的证明了该算法的可行性和可行解的最优性,并证明每个基因的插入至少产生一个新邻接,为后面的近似算法设计提供了依据。3.针对最大化邻接的双面基因组片段填充问题,设计了一个多项式时间近似算法,将近似性能比提高到1.5。相比单面的基因组片段填充问题,双面的基因组片段填充更具一般性,处理和分析更困难。对于基于最大化邻接的双面片段填充问题,H.Jiang等提出了一个简单的2-近似算法。本文通过分析双面片段填充问题实例的特征,得到一个双面基因组片段填充问题实例最优解方案中公共邻接数的界,根据这个界采用贪婪策略设计了一个近似算法,分析并证明算法的近似性能比是1.5。4.针对最大化邻接的单面基因组片段填充问题,设计了一个多项式时间近似算法,将近似性能比提高到1.25。此前,针对最大化邻接的单面基因组片段填充问题,近似性能比最小的算法是H. Jiang采用贪婪策略设计的1.33-近似算法。本文采用最大匹配方法和局部搜索技术设计了一个近似算法,其中最大匹配方法使算法找到了最多数量的1-Type-1串,局部搜索优化方法使利用贪婪策略找到的2-Type-1串数量进一步增多,从而使算法的近似性能提高到1.25。本文利用图论中二分图的相关方法,分析了该问题最优解与算法可行解之间的关系,通过严谨的公式推导证明了算法的近似性能比是1.25。5.设计了一个基于加权双向overlap图的可传递约减算法。该问题属于基因组片段填充前一环节的序列拼接中的信息约减问题。随着生物测序技术的不断发展,通过生物测序仪器直接获得的基因片段是海量的。直接使用这些海量的原始数据进行基因组的拼接,对拼接软件及计算设备的要求将会很高。为了提高拼接软件的运行效率,在不影响最终结果正确性的前提下,可以对海量的原始数据进行约减。本文在序列拼接常用的图论模型,加权双向overlap图中提出一个可传递约减算法,有效减少了图中的冗余边,即序列拼接中的冗余数据,简化了图的规模,提高图中求解路径的效率,并根据算法设计了一个测试软件,验证了算法的有效性。本文的进一步工作主要包括：1.继续探索SF-MNCA问题是否存在其他特殊实例,进行多项式时间精确算法设计。2.重复度为2或3的基因组的最大邻接距离计算问题。3.双面SF-MNCA问题中,设计近似度小于1.5的多项式时间近似算法。4.单面SF-MNCA问题,设计近似度小于1.25的多项式时间近似算法。5.单、双面SF-MNCA问题,输入序列不加封闭符号时,设计近似度小于2的有效近似算法。6.利用图论方法完成基因组序列拼接算法。

全文目录

摘要  11-15
ABSTRACT  15-20
第1章绪论  20-31
  1.1 研究背景和意义  20-22
  1.2 研究现状  22-23
  1.3 算法知识简介  23-27
    1.3.1 算法及算法的计算复杂性  23-24
    1.3.2 P类、NP类及NPC类问题  24-25
    1.3.3 近似算法和近似性能比  25-26
    1.3.4 贪婪、局部搜索技术  26-27
  1.4 本文的主要贡献  27-29
    1.4.1 最大化邻接的基因组片段填充问题的定义修正  27-28
    1.4.2 SF-MNCA问题特殊实例的多项式时间精确算法  28
    1.4.3 双面SF-MNCA问题的1.5-近似算法  28-29
    1.4.4 单面SF-MNCA问题的1.25-近似算法  29
    1.4.5 基于加权双向overlap图的可传递约减算法  29
  1.5 论文的组织结构  29-31
第2章基因组片段填充问题介绍  31-42
  2.1 计算基因组学相关概念  31-32
  2.2 邻接、断点  32-34
  2.3 SF-MNCA问题  34-35
  2.4 封闭符号“#”  35-37
  2.5 SF-MNCA问题中的几个特性  37-39
  2.6 断点的分类  39-40
  2.7 k-Type-1、k-Type-2串、插入串  40-41
  2.8 结论  41-42
第3章特殊情况下的多项式时间精确算法  42-54
  3.1 引言  42
  3.2 算法的前提  42-47
  3.3 算法的实现  47-50
  3.4 算法可行解的最优性  50-52
  3.5 算法的时间复杂度分析  52
  3.6 结论  52-54
第4章双面SF-MNCA问题的1.5-近似算法  54-70
  4.1 引言  54-55
  4.2 公共邻接数的一个上界  55-65
  4.3 双面填充算法  65-69
  4.4 算法时间复杂度分析  69
  4.5 总结  69-70
第5章单面SF-MNCA问题的1.25-近似算法  70-89
  5.1 引言  70-71
  5.2 问题描述  71
  5.3 插入Type-1串  71-78
    5.3.1 插入1-Type-1串  72
    5.3.2 插入2-Type-1串  72-74
    5.3.3 插入3-Type-1串  74-75
    5.3.4 插入剩余缺失基因  75-76
    5.3.5 完整算法描述  76-78
  5.4 近似算法分析  78-88
    5.4.1 改进的近似下界  78-80
    5.4.2 近似性能比分析  80-88
  5.5 结论  88-89
第6章序列拼接的信息约减问题  89-99
  6.1 引言  89-90
  6.2 相关知识简介  90-92
    6.2.1 碱基  90
    6.2.2 加权双向overlap图  90-92
  6.3 可传递约减算法  92-95
    6.3.1 可传递约减原理及正确性证明  92-93
    6.3.2 可传递约减在加权双向overlap图中的实现  93
    6.3.3 可传递约减算法的设计与实现  93-95
  6.4 实验及结果分析  95-98
  6.5 总结  98-99
第7章总结与展望  99-101
  7.1 本文总结  99-100
  7.2 研究展望  100-101
参考文献  101-106
致谢  106-107
攻读学位期间发表的学术论文  107-108
在读期间参与科研项目情况  108-109
学位论文评阅及答辩情况表  109-110
外文论文  110-144

基因组片段填充问题的算法研究

内容摘要

全文目录

相似论文