A Note on the Single Genotype Resolution Problem

来源 :计算机科学技术学报 | 被引量 : 0次 | 上传用户：Gzliao1

【摘要】

：

This note settles the complexity of the single genotype resolution problem showing it is NP-complete.This solves an open problem raised by P. Bonizzoni, G.D. Ve

【作者】

：

Hao Lin Ze-Feng Zhang Qiang-Fe

【机构】

：

Bioinformatics Lab,University of Science and Technology of China,University of Waterloo,Tsinghua Uni

【出处】

：

计算机科学技术学报

【发表日期】

：

2004年期

【关键词】

：

haplotype inference single genotype resolution maximum resolution NP-completenes

【基金项目】

：

中国科学院资助项目;北京市科委科研项目;国家重点基础研究发展计划(973计划);国家自然科学基金;国家高技术研究发展计划(863计划)

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

This note settles the complexity of the single genotype resolution problem showing 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-hardness of Maximum Resolution problem.

其他文献

Synthesis and Crystal Structures of Novel Keggin and Dawson Polyoxometalates Containing Amantadine

Two novel polyoxometalates containing pharmaceutical component amantadine, formulated with (C10H18N)5PMo12O40Cl2·5H2O (I) and (C10H18N) 6As2Mo18O62·6CH3CN·6H

期刊

Amantadinepolyoxometalatesynthesiscrystal structure

ESTIMATE OF THE UPPER CRITICAL FIELD AND CONCENTRATION FOR SUPERCONDUCTOR

The effect of an applied magnetic field on an inhomogeneous superconductor is studied and the value of the upper critical magnetic field Hc3 at which supercondu

期刊

SuperconductorCritical fieldNucleationGinzburg-Landau

The Isoelectric Point and the Points of Zero Charge of Fe-Al-Mg Hydrotalcite-like Compounds

The relation of the isoelectric point (IEP) and the point of zero net charge (PZNC) of the hydrotalcite-like compounds was discussed. It was found that the IEP

期刊

Isoelectric pointpoints of zero chargepotentiometric titrationhydrotalcite-li

THE EFFECT OF CLAY DISPERSION ON THE CRYSTALLIZATION AND MORPHOLOGY OF POLYPROPYLENE/CLAY COMPOSITES

PP/clay composites with different dispersions, namely, exfoliated dispersion, intercalated dispersion and agglomerates and panicle-like dispersion, were prepare

期刊

PP/clayDispersionCrystallizationMorphology

Conversion of Methane to Hydrogen via Pulsed Corona Discharge

Experiments are performed to develop a pulsed corona discharge system for the conversion of methane to hydrogen at atmospheric pressure (≌760 Tort) without usi

期刊

pulsed corona dischargemass spectrometermethanehydrogen

s-BLM修饰电极对组胺电化学传感行为的研究

研究了以抗组胺剂修饰的固体支撑双层类脂膜(s-BLM)分子器件体系对组胺的电化学传感行为.结果表明,在s-BLM膜中镶嵌抗组胺剂,体系对组胺的电化学响应强烈,并随着组胺浓度的增

期刊

双层类脂膜电化学生物传感器组胺循环伏安

Influence of Interactions on Populations for Hyperons in Neutron Stars

The numerical results of the populations for the baryon octet in neutron star matter have been presented by solving a set transcendental equations in the framew

期刊

neutron star matterrelativistic mean fieldhyperon populationhyperon coupling

Syntheses and Crystal Structures of Two New Compounds Containing Triarylamineand Benzoic Hydrazide U

Two new compounds containing triarylamine and benzoic hydrazide units, 4-[N,N-di(4-toyl)amino]benzaldehyde-N-(4-ethoxylphenyl)-formyl hydrazone 3a and 4-[N,N-di

期刊

triarylaminehydrazonecrystal structure

Influence of expressed TRAIL on biophysical properties of the human leukemic cell line Jurkat

The cDNA fragment of human TRAIL (TNF-related apoptosis inducing ligand) was cloned into RevTet-On, a Tetregulated and high-level gene expression system. The ge

期刊

TRAILTet gene expression systemJurkatapoptosis

A Note on the Single Genotype Resolution Problem

其他学术论文