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

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