TagSNPs selection using maximum density subgraph

The genome-wide disease association is a major interest of current genomics research. However, these works are limited by the high cost of genotyping large number of single nucleotide polymorphisms (SNPs). Therefore, it is essential to choose a small subset of informative SNPs (tagSNPs) to represent the rest of the SNPs. To find the minimum set of tagSNPs, we propose a new method that combines the ideas of the clustering method and the graph algorithm. Compared to most previous methods, the selection algorithm uses both the LD association and the diversity of haplotypes to select tagSNPs without the information loss and the limit of block partition. It also allows the user to adjust the efficiency of the program and quality of solutions. The experimental results on 6 different dataset from Hapmap indicate that the algorithm in this paper has better performance than previous ones.