一个SNP问题的多项式时间算法

讨论关于单体型的无间隙的最小单核苷酸多态性位点的移去问题.通过分析其对应图模型的性质讨论问题等价形式;证明求解该问题等价于求对应图的最大独立集与独立数;给出求最大独立集与独立数的算法,从而得到此问题的有效的多项式时间算法.

个体单体型问题参数化算法研究

个体单体型问题指如何利用个体DNA测序片断数据,根据不同的优化准则确定该个体单体型的计算问题.因为技术上的限制,DNA测序实验中能直接测定的片断长度是有限的,一个片断所覆盖的最大SNP位点数k1通常小于10;出于时间和金钱的考虑,覆盖一个SNP位点的最大片断数k2也不是很大,通常约为10左右;与要测定的单体型SNP位点总数n及所测序的DNA片断总数m相比,k1和k2均很小.在此基础上,文中对个体单体型问题最少SNP位点删除MSR和最少片段删除MFR模型进行了参数化,提出了时间复杂度分别为O(nk1k2+mlogm+mk1)和O(mk22+mk1k2+mlogm+nk2)求解无空隙MSR和MFR的精确算法.和Bafna等提出的时间复杂度为O(mn2)和O(m2n+m3)的精确算法相比,文中的算法效率提高了很多,具有较高的实用价值.

一种基于最少片段删除模型重建单体型的粒子群优化算法

利用最少片段删除(MFR)模型研究了个体单体型重建的算法。利用单核苷酸多态性(SNP)位点杂合率低的特性,引入了一种短粒子编码方式,提出了一种重建单体型的粒子群优化算法P-MFR。利用国际人类基因组单体型图计划发布的CEPH样本(祖籍是北欧或西欧的美国犹他州人)中60个个体在1号染色体上的单体型进行实验分析,实验结果显示,与以往求解MFR模型的算法相比较,P-MFR算法能够获得更高重建率的单体型。此外,由于采用了较短的粒子位置编码方式,P-MFR算法在重建长单体型时仍具有较高的执行效率,有很好的实用价值。