最大节约原则下单体型推导问题的复杂性

摘要

基于最大节约原则,寻找可以解释基因型样本的最小单体型集合,提出一个新的单体型推导方法.通过将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.