摘要
讨论关于单体型的无间隙的最小单核苷酸多态性位点的移去问题.通过分析其对应图模型的性质讨论问题等价形式;证明求解该问题等价于求对应图的最大独立集与独立数;给出求最大独立集与独立数的算法,从而得到此问题的有效的多项式时间算法.
The problem of minimum single nucleotide polymorphisms removal （MSR） on haplotyping was considered. The equivalent form of the problem was discussed by analyzing the properties of its mathematics model. It was proved that the problem of gapless case＇s MSR is equivalent to compute the maximum independent set and independence number of its graph. The algorithm for computing the maximum independent set and independence number was given; therefore an effective polynomial algorithm for the gapless case＇s minimum SNPs removal problem was given, which was easy to execute and would give a practical solution.
出处
《南阳师范学院学报》
CAS
2007年第3期1-4,共4页
Journal of Nanyang Normal University
