Paper Info
Title
Haplotypes and informative SNP selection algorithms: don't block out information
Abstract
It is widely hoped that variation in the human genome will provide a means of predicting risk of a variety of complex, chronic diseases. A major stumbling block to the successful identification of association between human DNA polymorphisms (SNPs) and variability in risk of complex diseases is the enormous number of SNPs in the human genome (4,9). The large number of SNPs results in unacceptably high costs for exhaustive genotyping, and so there is a broad effort to determine ways to select SNPs so as to maximize the informativeness of a subset.In this paper we contrast two methods for reducing the complexity of SNP variation: haplotype tagging, i.e. typing a subset of SNPs to identify segments of the genome that appear to be nearly unrecombined (haplotype blocks), and a new block-free model that we develop in this report. We present a statistic for comparing haplotype blocks and show that while the concept of haplotype blocks is reasonably robust there is substantial variability among block partitions. We develop a measure for selecting an informative subset of SNPs in a block free model. We show that the general version of this problem is NP-hard and give efficient algorithms for two important special cases of this problem.
Year
DOI
Venue
2003
10.1145/640075.640078
RECOMB
Keywords
Field
DocType
major stumbling block,haplotype blocks,snps result,block free model,human genome,block partition,haplotype tagging,informative snp selection algorithm,snps,haplotype block,human dna polymorphism,informative subset,snp variation
Genome,Biology,Tag SNP,Haplotype,Algorithm,SNP genotyping,Single-nucleotide polymorphism,Bioinformatics,Human genome,Genetics,SNP,Haplotype estimation
Conference
ISBN
Citations 
PageRank 
1-58113-635-8
44
8.04
References 
Authors
8
5
Name
Order
Citations
PageRank
Vineet Bafna11967226.80
Bjarni V Halldórsson2529.96
Russell Schwartz354868.68
Andrew G. Clark49618.60
Sorin Istrail51415170.40