摘要
基于最大节约原则,寻找可以解释基因型样本的最小单体型集合,提出一个新的单体型推导方法.通过将SAT问题和MAX-3-SAT问题归约到这种基于节约原则的单体型推导问题,证明了该问题是NP-hard以及MAX-SNP完全的,从而解决了该问题在计算上的复杂性.这一结果显示,除非P等于NP,否则,该问题不存在多项式时间算法;甚至存在一个常数e>0,该问题不存在比1+e好的近似算法.
A new parsimony method for haplotyping that tries to find a minimum set of haplotypes to explain the genotype sample was studied. By reducing the SAT problem and the MAX-3-SAT problem to the method, it was proved to be NP-hard and MAX-SNP complete, which means that it has no polynomial algorithm and cannot be approximated within ratio 1 ＋e for some constant e（e〉0） if P ≠NP.
基金
SupportedbyChinese"973"Program(G1998030401)
