| 最大节约原则下单体型推导问题的复杂性 |
| |
| 引用本文： | 张强锋,陈国良,孙广中.最大节约原则下单体型推导问题的复杂性[J].中国科学技术大学学报,2006,36(2):213-218. |
| |
| 作者姓名： | 张强锋 陈国良 孙广中 |
| |
| 作者单位： | 国家高性能中心,安徽合肥,230027;中国科学技术大学计算机科学与技术系,安徽合肥,230027 |
| |
| 基金项目： | 国家重点基础研究发展计划(973计划) |
| |
| 摘 要： | 基于最大节约原则,寻找可以解释基因型样本的最小单体型集合,提出一个新的单体型推导方法.通过将SAT问题和MAX-3-SAT问题归约到这种基于节约原则的单体型推导问题,证明了该问题是NP-hard以及MAX-SNP完全的,从而解决了该问题在计算上的复杂性.这一结果显示,除非P等于NP,否则,该问题不存在多项式时间算法;甚至存在一个常数e> 0,该问题不存在比1 e好的近似算法.
|
| 关 键 词： | 单体型 单体型推导问题 复杂性 NP-难 MAX-SNP完全 |
| 文章编号： | 0253-2778(2006)02-0213-06 |
| 收稿时间： | 10 9 2004 12:00AM |
| 修稿时间： | 04 10 2005 12:00AM |
On the complexity of haplotyping by maximum parsimony |
| |
| ZHANG Qiang-feng,CHEN Guo-liang,SUN Guang-zhong.On the complexity of haplotyping by maximum parsimony[J].Journal of University of Science and Technology of China,2006,36(2):213-218. |
| |
| Authors: | ZHANG Qiang-feng CHEN Guo-liang SUN Guang-zhong |
| |
| Institution: | 1. NHPCC, Hefei 230027, China ; 2. Dept. of Computer Science and Technology, USTC, Hefei 230027, China |
| |
| Abstract: | 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. |
| |
| Keywords: | haplotype haplotyping/haplotype inference complexity NP-hard MAX-SNP complete |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
