电子工业出版社-网上书店

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

目 录 
第 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

前 言 
基因组片段填充问题是隶属于计算基因组学范畴的新组合
优化问题。计算基因组学是一门运用计算机技术和信息技术对
基因组研究数据进行分析、建模和计算，从中获取生物信息的
学科。组合优化是指从组合问题的可行解中求出最优解，这些
组合问题往往具有问题描述简单、最优化求解困难的特征，如
装箱问题、图着色问题，而基因组片段填充问题便是新兴的组
合优化问题之一。
计算基因组学领域中较为经典的研究领域包括基因组测序
与组装、基因组比较、基因组重组等。已有的结论表明，计算
基因组学中的大部分问题是 NP 难问题，含重复基因的基因组
片段填充问题就是其中之一。而对于这些 NP 难问题，设计和
分析多项式时间近似算法具有较好的可行性和理论意义。
生物测序技术迅速发展，产生了第一代、第二代、第三代
和第四代测序技术，使得人们能够在更短的时间内获得大规模
的测序数据，测序的覆盖率有很大提高。目前，基因组的完整
序列通常在生物测序后，利用计算机技术相关的组装软件完成
测序片段的组装。但由于测序片段的覆盖情况和组装软件的局
限性，组装的最终结果往往不是基因组的完整序列，而是以片
段的形式发布的。比较典型的片段形 式包括基因组框架
(Scaffold)形式和片段重叠群(Contig)形式。若直接使用这些
不完整的基因组片段形式进行生物分析和研究，必将影响研究
结果的准确性。因此，使用基因组片段填充技术将缺失的基因
填充到不完整的基因组片段中，能够提高基因组最终序列的完
整性和准确性，节省全基因组生物测序成本。
针对上述问题，本书主要研究的问题包括单、双面含重复
基因的基于最大化公共邻接距离的基因组片段填充问题。此外，
IV
本书还研究了基因组片段填充问题之前的环节—序列拼接中
的信息约减问题，即在使用组装软件进行序列拼接前，在不影
响最终拼接结果的前提下，约减原始测序数据，从而提高序列
拼接效率。本书的研究内容和研究成果主要包括以下四个方面。
(1)针对基于最大化公共邻接距离的基因组片段填充问题
的特殊实例，本书提出了一种多项式时间精确算法。基于断点
距离、二次切割与连接距离及最大化公共邻接距离的无符号包
含重复基因的基因组片段填充问题，已经被证明是 NP 完全问
题，因此不存在多项式时间精确算法。但对于这些问题中的某
些特殊实例，人们能够找到解决它们的多项式时间精确算法。
本书针对基于最大化公共邻接距离的基因组片段填充问题中存
在的一类特殊实例，对每条序列中存在的断点进行研究，按照
组成断点的基因所属的位置划分成三种类型的断点集合，并确
定当输入序列中不存在这样的断点：一个基因属于待插入基因
集合或一个基因属于待插入序列的某个断点时，基于最大化公
共邻接距离的基因组片段填充问题存在一种时间复杂度为
O(n3
)的多项式时间精确算法，为后面的近似算法设计提供了
依据。
(2)针对基于最大化公共邻接距离的双面基因组片段填充
问题，本书设计了一种多项式时间近似算法，将近似性能比提
高到 1.5。相比单面基因组片段填充问题，双面基因组片段填
充问题更具一般性，处理和分析更困难。在基因组比较问题方
面，仅存在一种针对每个基因重复次数相同的平衡基因组之间
邻接距离的 4-近似算法。本书通过分析双面基因组片段填充问
题实例的特征，得到了一个双面基因组片段填充问题实例最优
解方案中公共邻接数的界，根据这个界采用贪婪策略设计了一
种近似算法，分析并证明了算法的近似性能比是 1.5。 (3)针对基于最大化公共邻接距离的单面基因组片段填充
问题，本书设计了一种多项式时间近似算法，将近似性能比提
高到 1.25。此前，针对基于最大化公共邻接距离的单面基因组
片段填充问题，近似性能比最小的算法是 Jiang 采用贪婪策略
设计的 1.33-近似算法。本书采用最大匹配方法和局部搜索策略
设计了一种近似算法，其中最大匹配方法使算法找到了最多数
量 的 1-Type-1 串，局部搜索策略使利用贪婪策略找到的
2-Type-1 串数量进一步增多，从而使算法的近似性能比提高到
1.25。本书利用图论中二分图的相关方法，分析了该问题的最
优解与算法可行解之间的关系，通过严谨的公式推导证明了算
法的近似性能比是 1.25。 (4)针对序列拼接中的信息约减问题，本书设计了一种基于
加权双向 overlap 图的可传递约减算法。随着生物测序技术的不
断发展，通过生物测序仪直接获得的基因组片段海量增加。直
接使用这些海量原始数据进行基因组序列的拼接，对组装软件
及计算设备的要求会很高。为了提高组装软件的运行效率，在
不影响最终结果正确性的前提下，可以对海量原始数据进行约
减。本书针对序列拼接常用的图论模型加权双向 overlap 图提出
了一种可传递约减算法，有效减少了图中的冗余边，即序列拼
接中的冗余数据，简化了图的规模，提高了图中求解路径的效
率，并根据算法设计了一个测试软件，验证了算法的有效性。
本书从基因组的生物学背景、涉及的计算机算法的基本概
念和核心思想出发，循序渐进地引入计算机技术进行生物问题
模型抽象，并利用贪婪、局部搜索和最大匹配等策略解决基因
组片段填充问题。针对由浅入深的各类问题，本书详细介绍了
算法的设计思想，并使用实例分析、数学证明、实验程序测试
等方法验证了算法的有效性和时间复杂度，为使用计算机技术
解决生物学领域问题提供了一种有效的解决方案。

本书配套资源下载

对不起，暂无音视频资源！