A Note on the Single Genotype 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.

单一基因型消解问题简报

人类基因组图谱已测序完毕。那么，我们在这个复杂图谱中如何快速发现、寻找到疾病的根源呢?DNA序列被看成是生命奥秘的载体，人们普遍认为DNA序列上的变异是人与人之间各种表型差异(如肤色，对某种疾病的易感性，或对药物的敏感度等)的重要原因。因此，基因组研究的一个重要方向是找出不同个体上的DNA变异和遗传疾病之间的相关性。在基因组中。