期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

A Note on the Single Genotype Resolution Problem

A Note on the Single Genotype Resolution Problem
原文传递
导出
摘要 This note settles the complexity of the single genotype resolution problemshowing 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-hardnessof Maximum Resolution problem. This note settles the complexity of the single genotype resolution problemshowing 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-hardnessof Maximum Resolution problem.
作者 HaoLin Ze-FengZhang Qiang-FengZhang Dong-BoBu MingLi
机构地区 BioinformaticsLab UniversityofScienceandTechnologyofChina UniversityofWaterloo
出处 《Journal of Computer Science & Technology》 SCIE EI CSCD 2004年第2期254-256,F003,共4页 计算机科学技术学报（英文版）
基金 中国科学院资助项目，国家自然科学基金，国家高技术研究发展计划(863计划)，国家重点基础研究发展计划(973计划)，北京市科委科研项目
关键词 haplotype inference single genotype resolution maximum resolution NP-COMPLETENESS haplotype inference single genotype resolution maximum resolution NP-completeness
分类号 Q754 [生物学—分子生物学]
  • 相关文献

参考文献1

二级参考文献29

  • 1International human genome sequencing consortium.Initial sequencing and analysis of the human genome.Nature, February 2001, 409(6822): 860-921.
  • 2Venter J C et al. The sequence of the human genome.Science, 2001, 291(5507): 1304-1351.
  • 3Patil N, Berno A J et aL Blocks of limited haplotype diversity revealed by high-resolution scanning of human chromosome 21. Science, 2001, 294(5547): 1669-1670.
  • 4iDaly M, Roux J, Schaffer Set al. Fine-Structure Haplotype Map of 5q31: Implications for Gene-Based Studies and Genomic Ld Mapping, 2001.
  • 5Gabriel S B, Schaffner S F, Nguyen H et al. The structure of haplotype blocks in the human genome. Science,2002, 296(5576): 2225-2229.
  • 6Lancia G, Bafna V, Istrail Set al. SNPs problems, complexity and algorithms. In Proc. 9th European Syrup.Algorithms (ESA), 2001, pp. 182-193.
  • 7Gusfield D. Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions. In Proc. 6th Annual Conference on Research in Computational Molecular Biology (RECOMB), 2002, pp.166-175.
  • 8Halperin E, Eskin E, Karp R M. Efficient reconstruction of haplotype structure via perfect phylogeny. Journal of Bioinformatics and Computational Biology, to appear.
  • 9Halperin E, Eskin E, Karp R M. Large scale reconstruction of haplotypes from genotype data. In Proc. 7th Annual Conference on Research in Computational Molecular Biology (RECOMB), 2003, pp.104-113.
  • 10Zhang K, Deng M, Chen T et al. A dynamic programming algorithm for haplotype block partitioning. In Pvoc. The National Academy of Sciences, USA, 2002,99(11): 7335-7339.

共引文献1

Journal of Computer Science & Technology
2004年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部