| 单体型推断问题与配对图 |
| |
| 引用本文： | 李珍萍,王勇,赵玉英,章祥荪.单体型推断问题与配对图[J].高校应用数学学报(A辑),2004,19(Z1):567-576. |
| |
| 作者姓名： | 李珍萍 王勇 赵玉英 章祥荪 |
| |
| 作者单位： | 1. 北京物资学院,基础部,北京,101149;中国科学院,数学与系统科学研究院生物信息中心,北京,100080
2. 中国科学院,数学与系统科学研究院生物信息中心,北京,100080 |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China(10471141),the Foundation of BeijingMaterials Institute. |
| |
| 摘 要： | 纯节俭型单体型推断(PPHI)问题是这样一类单体型推断问题给定n个基因型向量,要求寻找n对单体型,使得每一个基因型刚好由其中一对单体型组合生成,并且这2n个单体型中所含的不同单体型数目最小.u-限制单体型推断(u-PPHI)问题是一类特殊的纯节俭型单体型推断问题,要求每一个单体型至多可以用于分解u个基因型.PPHI和u-PPHI问题都是NP-困难的.文中首先介绍了配对图的概念,并通过配对图将两类问题转化为图论问题;然后分别给出了两类问题的近似算法;最后,专门讨论了当u=2时的2-PPHI问题,并在配对图上给出了相应的算法.
|
| 关 键 词： | 单体型 基因型 配对图 SNP |
| 修稿时间： | 2004年7月8日 |
HAPLOTYPE INFERENCE AND MATING GRAPH |
| |
| LI Zhen-ping,WANG Yong,ZHAO Yu-ying,ZHANG Xiang-sun.HAPLOTYPE INFERENCE AND MATING GRAPH[J].Applied Mathematics A Journal of Chinese Universities,2004,19(Z1):567-576. |
| |
| Authors: | LI Zhen-ping WANG Yong ZHAO Yu-ying ZHANG Xiang-sun |
| |
| Institution: | LI Zhen-ping 1,2,WANG Yong 2,ZHAO Yu-ying2,ZHANG Xiang-sun2 |
| |
| Abstract: | Pure Parsimony Haplotype Inference (PPHI) Problem is one of the haplotyping problems:Given an input set of n genotype vectors,find a set of n pairs of haplotypes,one for each genotype vector,such that the number of distinct haplotypes is minimum.An u-Restricted Pure Parsimony Haplotype Inference (u-PPHI) Problem is a special PPHI problem such that every haplotype can be used to resolve at most u genotypes.Both PPHI problem and u-PPHI problem are NP-hard.In this paper,a mating graph is introduced and both problems are turned into graph theory problems.Two approximate algorithms are proposed,one for the PPHI problem and the other for the u-PPHI problem.Especially,the 2-PPHI problem is investigated and an algorithm for solving the 2-PPHI problem on the mateing graph is given. |
| |
| Keywords: | haplotype genostype mating graph SNP |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
