10.3969/j.issn.1000-4424.2004.z1.009
单体型推断问题与配对图
纯节俭型单体型推断(PPHI)问题是这样一类单体型推断问题:给定n个基因型向量,要求寻找n对单体型,使得每一个基因型刚好由其中一对单体型组合生成,并且这2n个单体型中所含的不同单体型数目最小.u-限制单体型推断(u-PPHI)问题是一类特殊的纯节俭型单体型推断问题,要求每一个单体型至多可以用于分解u个基因型.PPHI和u-PPHI问题都是NP-困难的.文中首先介绍了配对图的概念,并通过配对图将两类问题转化为图论问题;然后分别给出了两类问题的近似算法;最后,专门讨论了当u=2时的2-PPHI问题,并在配对图上给出了相应的算法.
单体型、基因型、配对图、SNP
19
O157.5;Q811.4(代数、数论、组合理论)
国家自然科学基金10471141;北京市材料研究所基金
2005-09-22(万方平台首次上网日期,不代表论文的发表时间)
共10页
567-576