单体型推断问题与配对图

摘要：

纯节俭型单体型推断(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