申論題

15. (15 points) A Single Nucleotide Polymorphism (SNP, pronounced snip) is a single nucleotide variation in the genome that recurs in a signifcant proportion of the population of a species. The patterns of Linkage Disequilibrium (LD) observed in the human population reveal a block-like structure. LD refers to the association that particular alleles at nearby sites are more likely to occur together than would be predicted by chance. The entire chromogome can be partitioned into high LD regions interspersed by low LD regions. The high LD regions are usually called "heplotype blocks," and the low LD ones are referred to as "recombination hotspots." Since there is little or no recombination within a haplotype block, these SNPs are highly correlated. Consequently, a smnall subset of SNPs, called tag SNPs or haplotype tagging SNPs, is suficient to categorize the haplotype patterns of the block. It has been shown that we can recast the tag SNP selection problem as Problem W, which is,"Given a universal set U = {u₁, u₂, ...u_n} and a family F = {F₁, F₂，...， F_m} of subsets of U, Aind a minimu um-size subset of F, such that every element of U belongs to at least one subset in