基因组片段填充算法研究

　　无论是目前世界上肆意流行的各类病毒、以癌症为首的各种疾病，还是某些被发 现的新物种，人类对低成本、高效、准确地获取这些生物的全基因组序列都有着迫切 的需求。对于这种大规模数据的分析和处理，仅靠生物学手段无法高效完成，使用计 算机技术将有效节省处理问题的时间和降低经济成本。本书研究的基因组片段填充算 法是在利用生物测序手段获取基因组片段后，使用计算机领域的算法思想和技术，协 助获取完整基因组序列的有效手段，具有较好的实际应用意义。 本书以科研课题“基因组片段填充算法研究”为背景，以设计各类片段填充算法、 分析算法复杂度、提高算法近似性能比为主要目标，对如何使用计算机算法中的贪婪、 局部搜索和匹配等算法思想解决基因组片段填充中的难点问题进行了一系列探 索。本书涵盖了基因组片段填充中各类问题的定义、填充原理和算法描述，通过严谨 的理论推导证明了算法的正确性和近似性能比，并通过实例展示了算法的运行过程和 效果。本书可作为从事基因组序列填充问题研究工作的有关人员的参考用书。

　　柳楠，博士、副教授，毕业于山东大学计算机科学与技术学院。2015年10月至2016年10月于美国蒙大拿州立大学访学。主要研究领域是生物计算中基因组序列的填充问题，以及计算机算法设计与复杂度分析。以作者在IEEE/ACM Trans. Comput. Biology Bioinform、Algorithmica国际期刊和COCOON、TAMC、COCOA等国际知名学术会议上发表多篇学术论文，目前主持在研国家自然基金青年项目1项、山东省自然基金面上项目1项，结题山东省青年科学家奖励项目1项，参与4项国家和省级项目，获批软件著作权4项。

目 录
第 1 章 绪论 ·········································································.1
1.1 研究背景和意义 ························································.1
1.2 研究现状 ···································································.4
1.3 算法知识简介 ···························································.6
1.3.1 算法及算法的计算复杂性 ···········································.6
1.3.2 P 类、NP 类及 NPC 类问题 ·········································.7
1.3.3 近似算法和近似性能比 ··············································.9
1.3.4 贪婪、局部搜索策略·················································10
1.4 本书的主要贡献 ························································11
1.4.1 化公共邻接距离的基因组片段填充问题的 定义修正 ·····12
1.4.2 SF-MNCA 问题特殊实例的多项式时间精确算法 ················12
1.4.3 双面 SF-MNCA 问题的 1.5-近似算法······························13
1.4.4 单面 SF-MNCA 问题的 1.25-近似算法 ····························13
1.4.5 基于加权双向 overlap 图的可传递约减算法······················13
1.5 本书的组织结构 ························································14
第 2 章 基因组片段填充问题介绍········································17
2.1 计算基因组学相关概念·············································17
2.2 邻接、断点 ·······························································18
2.3 SF-MNCA 问题 ·························································22
2.4 封闭符号“#”··························································23
2.5 SF-MNCA 问题中的几个特性 ···································24
2.6 断点的分类 ·······························································28
2.7 k-Type-1 类型串、k-Type-2 类型串、插入串·············29
VII
第 3 章 特殊情况下的多项式时间精确算法 ·························33
3.1 引言 ··········································································33
3.2 算法的前提 ·······························································33
3.3 算法的实现 ·······························································39
3.4 算法可行解的性 ················································43
3.5 算法的时间复杂度分析·············································45
第 4 章 双面 SF-MNCA 问题的 1.5-近似算法介绍 ··············47
4.1 引言 ··········································································47
4.2 公共邻接数的一个上界·············································48
4.3 双面填充算法 ···························································61
4.4 算法的时间复杂度分析·············································65
第 5 章 单面 SF-MNCA 问题的 1.25-近似算法介绍 ············67
5.1 引言 ··········································································67
5.2 问题描述 ···································································69
5.3 插入 Type-1 串 ··························································69
5.3.1 插入 1-Type-1 串······················································69
5.3.2 插入 2-Type-1 串······················································70
5.3.3 插入 3-Type-1 串······················································72
5.3.4 插入剩余缺失基因 ···················································73
5.3.5 完整算法描述 ·························································75
5.4 近似算法分析 ···························································77
5.4.1 改进的近似下界 ······················································77
5.4.2 近似性能比分析 ······················································79
第 6 章 序列拼接的信息约减问题········································89
6.1 引言 ··········································································89
6.2 相关知识简介 ···························································90
6.2.1 碱基 ····································································90
VIII
6.2.2 加权双向 overlap 图 ··················································91
6.3 可传递约减算法 ························································93
6.3.1 可传递约减原理及正确性证明 ·····································93
6.3.2 可传递约减在加权双向 overlap 图中的实现······················94
6.3.3 可传递约减算法的设计与实现 ·····································95
6.4 实验及结果分析 ························································97
结束语 ··················································································101
参考文献 ··············································································105