Recent studies have revealed a haplotype block structure for human genome which can be decomposed into large blocks with high linkage disequilibrium (LD) and relatively limited haplotype diversity, separated by short regions of low LD. One of the practical implications of this observation is that only a small number of tag SNPs can be chosen for mapping genes responsible for human complex diseases, which can significantly reduce genotyping effort without much loss of power. In this lecture, we survey the dynamic programming algorithms developed for haplotype block partitioning and tag SNP selection, with a focus on algorithmic considerations. |
