论文部分内容阅读
纯节俭型单体型推断（PPHI）问题是这样一类单体型推断问题：给定n个基因型向量，要求寻找n对单体型，使得每一个基因型刚好由其中一对单体型组合生成，并且这2n个单体型中所含的不同单体型数目最小,u-限制单体型推断（u-PPHI）问题是一类特殊的纯节俭型单体型推断问题，要求每一个单体型至多可以用于分解u个基因型．PPHI和u-PPHI问题都是NP-困难的，文中首先介绍了配对图的概念，并通过配对图将两类问题转化为图论问题；然后分别给出了两类问题的近似算法；最后，专门讨论了当u=2时的2-PPHI问题，并在配对图