Haplotype Inferring Via Galled-Tree Networks Is NP-Complete
The problem of determining haplotypes from genotypes has gained considerable prominence in the research community since the beginning of the HapMap project. Here the focus is on determining the sets of SNP values of individual chromosomes (haplotypes), since such information better captures the genetic causes of diseases. One of the main algorithmic tools for haplotyping is based on the assumption that the evolutionary history for the original haplotypes satisfies perfect phylogeny. The algorithm can be applied only on individual blocks of chromosomes, in which it is assumed that recombinations either do not happen or happen with small frequencies. However, exact determination of blocks is usually not possible. It would be desirable to develop a method for haplotyping which can account for recombinations, and thus can be applied on multiblock sections of chromosomes. A natural candidate for such a method is haplotyping via phylogenetic networks or their simplified version: galled-tree networks, which were
Arvind Gupta Jan Manuch Ladislav Stacho Xiaohong Zhao
School of Computing Science and Department of Mathematics Simon Fraser University, Canada
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
287-298
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）