A Note on the Single Genotype Resolution Problem  

作　　者：HaoLin Ze-FengZhang Qiang-FengZhang Dong-BoBu MingLi 

机构地区：[1]BioinformaticsLab,InstituteofComputingTechnology,TheChineseAcademyofSciences,Beijing100080,P.R.China [2]UniversityofScienceandTechnologyofChina,Hefei230026.P.R.China [3]UniversityofWaterloo,Canada

出　　处：《Journal of Computer Science & Technology》2004年第2期254-256,F003,共4页计算机科学技术学报（英文版）

基　　金：中国科学院资助项目，国家自然科学基金，国家高技术研究发展计划(863计划)，国家重点基础研究发展计划(973计划)，北京市科委科研项目

摘　　要：This note settles the complexity of the single genotype resolution problemshowing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R.Dondi, and J. Li. The same proof also gives an alternative and simpler reduction of the NP-hardnessof Maximum Resolution problem.This note settles the complexity of the single genotype resolution problemshowing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R.Dondi, and J. Li. The same proof also gives an alternative and simpler reduction of the NP-hardnessof Maximum Resolution problem.

关 键 词：haplotype inference single genotype resolution maximum resolution NP-COMPLETENESS 

分 类 号：Q754[生物学—分子生物学]