The Construction of Minimal Set-covering Model for TagSNP Selection Problem and Heuristic Function Algorithm
TagSNP selection is an important step for genomewide association studies. Among selection methods that have proposed, the ones based on pairwise linkage disequilibrium (LD)measurement are attractive. The goal is to minimize the number of markers selected for genotyping and therefore reduce genotyping cost while simultaneously representing information provided by all other markers. In this paper, the minimal setcovering model is developed for tagSNP selection problem, then a heuristic function algorithm is proposed for solving the model.Heuristic function in this algorithm is constructed to measure the prioritized order of the sets in the minimal set-covering problem based on two kinds of information factors-the number of elements in the set and the covering degree of the set. The algorithm is tested on several ENCODE regions and Chromosome 22, the computational results indicate that heuristic function algorithm is effective and efficient in comparison experiment.
TagSNP selection Set-covering Tag set Heuristic function
Ying Wang Enmin Feng Ruisheng Wang
Department of Applied Mathematics Dalian University of Technology Dalian 116023, China School of Information Renmin University of China Beijing 100872, China
国际会议
武汉
英文
256-259
2007-07-06（万方平台首次上网日期，不代表论文的发表时间）