单体分型和单体型频率估计 ——复杂性及算法

论文摘要

计算机和网络技术的飞速发展，为分子生物学研究提供了新的强大手段。单体型信息因其在医学特别是遗传疾病研究方面具有重要意义，引起生物与医学工作者的极大关注。但绝大多数所研究的生物个体，包括人类自身，都是双倍体结构；目前由于时间和经济成本上的约束，在实验室里只能得到双倍体结构的复合基因型序列。因此，当需要知道物种或者组织的单体型序列信息时，我们必须借助于计算手段，将每一条基因型序列分解为两条单体型序列，这就是单体分型问题。本文研究了不同数据集及不同模型上单体分型问题的计算复杂性，设计和实现了一系列高效的单体分型和单体型频率估计算法。其主要内容和贡献包括： （1） 群体数据集单体分型 群体数据集不包含任何家系信息，是最常见的一种基因型数据集。关于群体数据集单体分型问题，目前常见的计算手段有Clark算法、PPH算法以及EM和GS等概率统计算法。本文对一种新近提出的基于最大节约原则的单体分型（HMP）模型进行了研究，证明其是NP-hard的和APX-hard的（即，除非NP=P，否则存在一个常数e＞0，该问题没有比1+e好的多项式时间逼近算法）。因此，我们为其设计了一个多项式时间的贪心算法以及一个将贪心策略和分支限界策略集合在统一框架下的复合算法。实验结果表明：贪心算法在保持了较准确分型结果的基础上、运行速度相当快；而复合算法虽是完全算法，但其运行效率和实例规模比原有的分枝限界算法都得到了极大提高。 群体数据集中特定基因型序列分型（SGH）判定问题与上述Clark算法相关、它可以帮助我们更好理解单体分型问题。本文证明了SGH问题为NP-complete的。 （2） 家系数据集单体分型 由于家系信息的对单体构型的限制，基于家系数据集进行的单体分型和单体型频率估计的结果会更加可靠。目前对其研究集中于寻找使得家系中发生最少重组事件的单体构型。本文提出了一个k-最少重组单体分型（k-MRH）模型，它在现有的最少重组单体分型（MRH）模型中引入额外限制，使得重组事件在家系中更加合理地平衡分布。同时设计了k-MRH模型的一个综合了寻根策略的优化动态规划算法，尽管该模型也是NP-hard的，但我们的限制条件使其解空间大大缩小，从而大大提高了算法的搜索效率，这在模拟和实际数据的实验中都得到了验证。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 全文梗概
• §1.1 计算生物学
• §1.2 本文工作背景
• §1.2.1 群体数据集单体分型
• §1.2.2 家系数据集单体分型
• §1.2.3 单体型频率估计
• §1.3 文献资源
• §1.3.1 机构、组织和个人
• §1.3.2 电子文献资源
• §1.3.3 期刊
• §1.3.4 会议
• §1.4 论文组织
• 参考文献
• 第二章 分子生物学背景
• §2.1 遗传与变异的物质基础
• §2.1.1 发现基因的历史
• §2.1.2 染色体与DNA
• §2.1.3 多态现象与SNP位点
• §2.2 单体分型
• §2.2.1 基因型与单体型
• §2.2.2 单体分型
• §2.3.本章小结
• 参考文献
• 第三章 群体数据集单体分型
• §3.1 问题定义
• §3.2 已有的工作
• §3.2.1 Clark算法
• §3.2.2 其他算法
• §3.3 最大节约模型
• §3.3.1 简单有效的模型
• §3.3.2 计算复杂性
• §3.3.3 分支限界算法
• §3.3.4 贪心算法
• §3.3.5 复合算法
• §3.3.6 实验比较
• §3.3.7 结论
• §3.4 特定基因型序列分型
• §3.5 本章小结
• 参考文献
• 第四章 家系数据集单体分型
• §4.1 问题定义
• §4.1.1 家系及家系数据集单体分型
• §4.1.2 重组
• §4.2 已有的工作
• §4.3 k-最少重组单体分型
• §4.3.1 模型
• §4.3.2 动态规划算法
• §4.3.3 寻根策略
• §4.3.4 实验比较
• §4.3.5 结论
• §4.4 零重组单体分型
• §4.4.1 三元家庭单体分型和HCL-连锁
• §4.4.2 合并操作
• §4.4.3 传递操作
• §4.4.4 线性时间算法
• §4.4.5 扩展问题
• §4.4.6 实验比较
• §4.4.7 结论
• §4.5 本章小结
• 参考文献
• 第五章 单体型频率估计
• §5.1 已有的工作
• §5.1.1 最大似然估计和EM算法
• §5.1.2 群体数据集单体型频率估计
• §5.2 家系数据集单体型频率估计
• §5.2.1 三元家庭中单体型频率估计
• §5.2.2 一般家系中单体型频率估计
• §5.2.3 PL-EM算法
• §5.2.4 实验比较
• §5.2.5 结论
• §5.3 本章小结
• 参考文献
• 第六章 总结
• §6.1 本文工作
• §6.2 本文贡献与创新之处
• §6.3 进一步工作
• 参考文献
• 附录A 插图索引
• 附录B 表格索引
• 附录C 算法索引
• 致谢
• 在读期间参加的科研项目
• 在读期间发表和录用的论文