单体型问题及其算法研究

人类是双倍体结构，需将一条复合的基因型序列分解为两条单体型序列，这就是单体型推导或分型问题。随着国际HAPMAP计划和我国生物学领域相关研究的如火如荼地开展，单体型推导等问题得到重视和广泛研究。计算生物学是一种低成本、快速、大规模数据处理的可行手段，且当前出现的基于块结构的方法和基于图论的方法已成突破之势，现在是切入研究的良好时机。本项目主要研究内容和方式：以单体型问题合理模型和基本算法研究为基础，重点发展近期有前途的基于块结构的算法和基于图论方法的算法，以启发式算法和并行化突出算法的实际应用效果。我们已在模型和基本算法以及块划分算法上取得一定成绩，以此为基础力使项目的创新体现在：建立融入连锁不平衡特性的、合理的 k最少重组模型；应用统计和机器学习的方法提高块划分的合理性，改进我们提出的块划分算法；应用启发式算法和并行化，使当前能解问题的规模(杂合位点数和个体数)由几十量级提高到百位数。

人类是双倍体结构，需将一条复合的基因型序列分解为两条单体型序列，这就是单体型推导或分型问题。随着国际HAPMAP计划和我国生物学领域相关研究的如火如荼地开展，单体型推导等问题的计算生物学研究越来越重要。本项目以单体型问题表示模型和基本算法研究为基础，重点发展基于块结构的算法和基于图论方法的算法，解决生物序列分析中的一些关键计算技术问题。. 通过三年的项目执行，我们已取得一些代表性的工作和成果：①对于单体型表示模型和推导算法，提出了以图论方法为基础的网络流模型和其上的一个启发式推导算法FNphasing，该模型是首个具有全局视图的表示模型，并且FNphasing算法在已有的测试数据集上计算精度和速度均为最好。本项科学意义在于全局视图表示模型，避免了传统方法的“黑箱”寻优做法。②对于传统的快速2SNP算法进行了改造和优化，设计了一个计算速度与2SNP算法相当的单体型推导算法WinHap，而计算精度有明显提升。本项科学意义在于可扩展的滑动窗口捕获到的保守或频繁信息，是基于分块算法的真正目标和精髓。③对大规模生物序列分析中的关键计算技术和方法，提出了动态规划计算的尽快计算模式和并行计算中的负载平衡方法，并在多序列公共子序列、Smith-Waterman序列比对和motif发现上，应用效果显著。最后，在序列条数为800、长度为20000时，我们的算法FNphasing需要时间133.64s和空间为661MB，为目前性能最好。本项科学意义在于生物序列大数据处理的一种尝试和突破。