生物序列分析算法的研究及其应用

论文摘要

随着人类基因组计划的完成,人们获得了大量的生物学数据。在对这些生物数据进行处理和分析的过程中,涌现出了大量的数学问题。这些数学问题亟需通过有效的计算手段进行解决。DNA和蛋白质研究是分子生物学中两项核心的研究课题,我们针对DNA和蛋白质序列分析中出现的一些数学问题进行研究。单体型是一些特定的DNA位点组成的序列。单体型分析可以帮助我们了解基因与疾病之间的关联,这在遗传疾病的研究方面具有重要意义。模体是一些保守的DNA片段,模体发现对基因转录及其调控的研究很有帮助。蛋白质的空间结构决定了它的功能,基于蛋白质序列,我们可以对蛋白质的结构进行预测,从而为病毒检测以及生物制药等研究提供帮助。本文围绕单体分型、模体发现和蛋白质结构预测等问题展开研究,主要的研究内容包括：（1）提出一种群体数据集上的单体分型算法由于成本的限制,单体型难以通过实验手段大量获得。但是单体型可以利用基因型数据通过计算手段进行求解,其中分块-合并策略被广泛地应用于多个算法中,用以提高算法的效率。在传统的分块-合并策略中,分块是均匀的,但很多研究表明单体型具有特有的块结构,分块并不均匀。基于此我们统计不同位点间的关联强度,并使用动态规划算法设计了更合理的分块策略,利用贪心算法对相邻分块进行合并,我们将新的分块-合并策略其应用于EM单体分型算法中。（2）提出一种家系数据集上的单体分型算法近来,通过一些新的生物实验手段,可以获得一种新类型的数据一异或基因型。基于异或基因型的单体分型成为一项新的研究课题。研究者们对群体数据集上基于异或基因型的单体分型算法做了很多研究,但基于家系数据的研究还很少。基于完美进化树模型,我们将家系上的异或基因型分型问题转化为图论中的图实现问题进行求解,家系结构为问题求解提供了更多的约束,使得问题有更大的概率获得唯一解。（3）提出一种序列模体发现算法模体在转录因子绑定及蛋白质间相互作用中起着重要作用,对它的发现会有助于我们了解基因的功能。植入（l, d）模体发现是其中一类经典的问题,但不幸的是,这一问题是NP难解的。研究者们提出了很多算法。由于问题的NP难解性,精确算法难以在有效时间内对其进行求解。结合哈希表和剪枝策略,我们提出一种更有效的序列模体发现精确算法。（4）提出一种蛋白质二级结构预测算法蛋白质结构的确定对我们了解蛋白质的功能至关重要。以往的蛋白质结构预测算法大多是基于序列以及数据库比较的。我们结合化学位移信息和蛋白质序列来对蛋白质的二级结构进行预测。通过NMR实验,我们可以获得蛋白质中每个氨基酸对应原子的化学位移信息。利用这些化学位移信息,我们提出一种新的蛋白质二级结构预测算法。算法首先使用KNN方法对蛋白质二级结构进行初步预测,之后在利用BCJR算法对预测结果进行平滑。按照研究内容分类,本文的贡献和创新之处在于：（1）群体数据集单体分型根据单体型固有的块结构,提出了一种更合理的单体型分块-合并算法,并将其应用于群体数据集单体分型中,提高了分型的准确性。（2）家系数据集单体分型基于一种新型的异或基因型数据,结合家系信息,提出一个多项式时间的算法对单体型进行求解。和群体数据集相比,家系数据集有更大概率获得唯一解。（3）序列模体发现提出了一种新的序列模体发现算法,设计了一个完美哈希函数,对解空间进行哈希,并在计算的过程中对不可能的解进行剪枝,和已有的算法相比,该算法取得了更高的效率。（4）蛋白质二级结构预测基于化学位移数据和蛋白质序列,利用KNN方法对蛋白质二级结构进行预测,并使用BCJR算法对结果进行平滑,和已有的算法相比,该算法取得了较高的预测准确性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 生物信息学
• 1.2 本文的研究内容
• 1.2.1 群体数据集单体分型
• 1.2.2 家系数据集单体分型
• 1.2.3 生物序列模体发现
• 1.2.4 蛋白质二级结构预测
• 1.3 论文组织
• 第2章 分子生物学背景
• 2.1 基因、DNA与蛋白质
• 2.2 单体型
• 2.2.1 变异与SNP位点
• 2.2.2 单体型与基因型
• 2.2.3 重组
• 2.2.4 单体型块结构
• 2.3 序列模体
• 2.3.1 转录因子
• 2.3.2 模体
• 2.4 蛋白质结构
• 2.4.1 蛋白质
• 2.4.2 蛋白质的结构层次
• 2.5 本章小结
• 第3章 群体数据集单体分型
• 3.1 问题定义
• 3.2 已有的工作
• 3.2.1 组合优化算法
• 3.2.3 频率估计算法
• 3.3 基于分块的单体型频率估计算法
• 3.3.1 基于动态规划的分块算法
• 3.3.2 基于贪心的合并算法
• 3.3.3 实验比较
• 3.3.4 结论
• 3.4 本章小结
• 第4章 家系数据集单体分型
• 4.1 问题定义
• 4.2 已有的工作
• 4.2.1 最少重组单体分型
• 4.2.2 异或基因型
• 4.3 基于异或基因型的家系单体分型
• 4.3.1 异或基因型推导算法
• 4.3.2 实验比较
• 4.3.3 结论
• 4.4 本章小结
• 第5章 生物序列模体发现
• 5.1 问题定义
• 5.2 已有的工作
• 5.3 CVOTNG算法
• 5.3.1 基于相容模体的剪枝算法
• 5.3.2 基于投票的哈希算法
• 5.3.3 扩展的投票算法
• 5.3.4 实验比较
• 5.3.5 结论
• 5.4 本章小结
• 第6章 蛋白质二级结构预测
• 6.1 问题定义
• 6.2 已有的工作
• 6.3 基于化学位移的二级结构预测算法
• 6.3.1 数据收集
• 6.3.2 KNN预测
• 6.3.3 结果平滑
• 6.3.4 实验比较
• 6.3.5 结论
• 6.4 本章小结
• 第7章 总结
• 7.1 本文工作
• 7.2 本文贡献与创新之处
• 7.3 进一步工作
• 参考文献
• 附录1 插图索引
• 附录2 表格索引
• 致谢
• 攻读学位期间参加的科研项目
• 在读期间发表的学术论文