新一代测序技术下单体型组装问题计算模型和算法研究

单体型在复杂疾病致病基因定位等领域有重要的应用，而直接测定单体型代价过分昂贵，因此利用DNA片段数据组装出单体型的计算问题深受研究，已有多个计算模型。这些模型绝大多数是NP-难及APX-难的，已有启发式算法的验证实验均隐含着一个片段覆盖单体型的大部分区域，已有精确算法则受片段覆盖深度不能太大的约束。目前开始使用的新一代测序技术存在着能直接测序的片段较短、测序误差较大和覆盖深度大的特点，因此已有模型和算法的有效性受到了挑战。本项目将深入分析新一代测序技术产生数据的特征，结合分子遗传学规律提出适用新一代测序技术的具有更高单体型重建精度的计算模型，对目前研究的单体型组装问题进行扩展，使之适应病毒群需要组装出多个单体型的场合。进而利用参数计算、图论算法和聚类分析等技术，寻求实用有效算法。本项目的开展将进一步激发单体型计算模型及算法研究，有力地促进单体型检测及其应用。

在本基金的支持下，课题组在新一代测序技术下单体型组装计算问题组合优化模型的构建、高效算法的设计与分析上取得了显著的进展。通过对单体型组装问题相关真实生物数据的整合和数据特征的抽取，课题组完成了模拟数据生成器的设计和测试平台的建设；结合图论和聚类分析等技术提出了一个新的平衡优化划分单体型组装模型；课题组根据单体型组装的实质是利用片段包含的两个杂合SNP位点之间的组合模式来组装一条染色体上较大区域的SNP序列，把片段数据转化成两位点连锁图，提出了新的连锁图标签优化单体型组装模型。这些新的单体型模型比已有的模型在单体型重建精度上有明显的改善。通过对新一代测序技术下真实生物数据特征的挖掘，课题组发现了测序片段数据具有一些小参数特征：一个片段覆盖的杂合SNP位点和覆盖一个SNP位点的片段数通常都比较小；进而利用参数计算理论，为多个NP-难的单体型组装优化模型设计了快速的参数化动态规划精确算法。动态规划递推过程中要保留的中间计算结果的多少是影响动态规划算法时空复杂度的决定因素，课题组通过大量的测试发现只保留一部分较优的中间结果能大大加快算法的速度，而对最终计算结果没有显著影响。为了进一步加快单体型的重建，课题组为单体型组装设计了基于top-k个中间最优解的启发式动态规划算法。项目促进了单体型计算模型及算法研究，项目的研究成果为生物信息学中大量复杂的计算问题的实用算法设计提供了新思路，也将促进单体型在复杂疾病全基因关联分析中的应用。