论文摘要
分析和识别单体型对复杂疾病致病基因的精确定位有重要作用。单体型组装问题是利用个体DNA测序片段数据推出该个体一对单体型的计算问题。根据不同的优化准则,单体型组装问题有MSR、MFR、MEC和MEC/GI等计算模型。单体型组装问题的绝大部分计算模型都被证明是NP-难的,缺乏实用的精确算法。在实际DNA片段数据中,一个片段所覆盖的最大SNP位点数k1通常小于10,覆盖一个SNP位点的最大片段数k2通常不大于19。基于以上事实,本文对MSR和MFR进行参数化建模。在此基础上,为求解无空隙的MSR和MFR,本文设计了时间复杂度分别为O（nk1k2+mlogm+mk1）和O（mk22+mk1k2+mlogm+nk2）的精确算法PMSR和PMFR,其中m为片段数,n为单体型的SNP位点数;为求解有空隙的MSR和MFR,本文设计了时间复杂度分别为O（2knk1k2+mlogm+nk2+mk1）和O(2kmk1k2+23kmk22+mlogm+nk2+mk1)的精确算法PGMSR和PGMFR,其中k为片段中最大洞数。大量实验结果表明,在Bafna等的对应算法基础上,上述参数化算法的效率显著提高,适用于全基因组规模上的单体型组装。针对长的mate-pair中洞的个数较多的情况,本文提出了求解MSR和MFR时间复杂度分别为O(nk1k222h+k12h+nk2+mk1)和O(nk23k2+mlogm+nk2+mk1)的参数化精确算法PMMSR和PMMFR,其中h为覆盖同一SNP位点且在该位点取空值的片段的最大数。在实际的DNA测序数据中,k2通常不大于19,而h不大于17,理论分析和实验结果均表明PMMSR和PMMFR算法所需的时间与片段中洞的个数的最大值k没有直接的关系,在片段数据中存在长mate-pair的情况下仍然能有效计算。根据实际DNA测序片段数据的特点,本文对MEC和MEC/GI进行参数化建模,进而设计出求解这两个模型时间复杂度均为O(nk22k2+mlogm+mk1)的精确算法PMEC和PMEC/GI。实验结果表明,在片段数达到100,Wang等提出的分支限界算法已无法运行的情况下,PMEC、PMEC/GI和Wang等提出的遗传算法一样,仍然能快速运行。而作为精确算法,PMEC和PMEC/GI在单体型重构精度上比Wang等对应的遗传算法有明显优势。为了提高单体型的重构精度,本文提出了一个基于加权片段数据和有误差基因型的单体型组装问题计算模型WMEC/GS,然后证明了即使片段中无空隙其也是NP-难的。进而根据片段数据的特点,提出了求解该模型的时间复杂度为O(nk22k2+mlogm+mk1)的参数化算法PWMEC/GS。对MEC/GI、WMLF和WMEC/GS三模型的大量实验表明WMEC/GS模型具有最高的单体型重构精度。