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

来源 :中国科学技术大学学报 | 被引量 : 0次 | 上传用户：zidapp

【摘要】

：

基于最大节约原则，寻找可以解释基因型样本的最小单体型集合，提出一个新的单体型推导方法．通过将SAT问题和MAX-3-SAT问题归约到这种基于节约原则的单体型推导问题，证明了该问题是

【作者】

：

张强锋陈国良孙广中

【机构】

：

国家高性能中心,中国科学技术大学计算机科学与技术系

【出处】

：

中国科学技术大学学报

【发表日期】

：

2006年2期

【关键词】

：

单体型单体型推导问题复杂性 NP难 MAX-SNP完全 haplotype haplotyping/haplotype inference complexi

【基金项目】

：

Foundation item： Supported by Chinese ＂973＂ Program （G1998030401）. Acknowledgements. The authors would like to thank WANG L for introducing us to the work in [2] and [-7].

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

基于最大节约原则，寻找可以解释基因型样本的最小单体型集合，提出一个新的单体型推导方法．通过将SAT问题和MAX-3-SAT问题归约到这种基于节约原则的单体型推导问题，证明了该问题是NP—hard以及MAX-SNP完全的，从而解决了该问题在计算上的复杂性．这一结果显示，除非P等于NP，否则，该问题不存在多项式N-N算法；甚至存在一个常数e〉0，该问题不存在比1＋e好的近似算法．

其他文献

浅谈现代青花人物创作的继承与创新关系

余忠可 1964年出生，江西都昌人。艺名云海：1984年在艺术瓷厂特艺组工作，同时在陶瓷学院余进宝教授门下学习中国工笔重彩国画。1989年毕业于中国书画函授大学，被评为优秀学员、江西省陶瓷高级技师、省美协会员、市美协会员，被编入《中国美术家人名录》。作品《十里飘香》荣获省第二届青年美术作品优秀奖，《雨后晨色》获优秀奖在北京展示，《群仙芬芳满神州》入选省建军六十周年美术作品展，《独傲秋霜》获市美展二

期刊

创新人物青花创作吉祥寓意生活化

密度合理

<正> 造林密度是指单位面积上栽植点的多少。树种不同,立地条件不同,造林目的不同,造林密度也应不同。科学合理的造林密度,既可充分利用土地资源,又能满足林木生长对营养空间

期刊

水肥条件林粮间作立地条件小径材林木生长抚育管理

50例过敏性鼻炎手术治疗临床效果分析

目的探讨过敏性鼻炎手术治疗临床效果。方法选取2017年2月~2018年2月来我院接受治疗的100例过敏性鼻炎患者作为研究对象,随机将患者均分成对照组和实验组。对照组患者接受药

期刊

过敏性鼻炎手术临床效果

构建基层群众自治法律制度的思考

<正>我国要真正实现基层群众自治,不断完善和发展中国基层民主政治建设的模式,构建基层群众自治法律制度体系是前提和基础。目前,我国基层自治法制建设基本适应了当前基层群

期刊

基层群众自治基层民主政治建设《城市居民委员会组织法》

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

其他学术论文