FOCUS
A hybrid clustering and graph based algorithm for tagSNP
selection
Mao-Zu Guo Æ Jun Wang Æ Chun-yu Wang Æ
Yang Liu
Published online: 21 March 2009
Springer-Verlag 2009
Abstract TagSNP selection, which aims to select a small
subset of informative single nucleotide polymorphisms
(SNPs) to represent the whole large SNP set, has played an
important role in current genomic research. Not only can this
cut down the cost of genotyping by filtering a large number of
redundant SNPs, but also it can accelerate the study of gen-
ome-wide disease association. In this paper, we propose a new
hybrid method called CMDStagger that combines the ideas of
the clustering and the graph algorithm, to find the minimum
set of tagSNPs. The proposed algorithm uses the information
of the linkage disequilibrium association and the haplotype
diversity to reduce the information loss in tagSNP selection,
and has no limit of block partition. The approach is tested on
eight benchmark datasets from Hapmap and chromosome
5q31. Experimental results show that the algorithm in this
paper can reduce the selection time and obtain less tagSNPs
with high prediction accuracy. It indicates that this method
has better performance than previous ones.
Keywords TagSNP selection Clustering algorithm
Maximum density subgraph (MDS) Linkage
disequilibrium (LD) Haplotypes diversity
1 Introduction
The genome-wide disease association is a major interest of
current genomics research. SNPs and haplotypes, which
characterize most of the genetic variation among different
people, can provide the most complete information for
these association studies, such as identifying the genetic
components of common diseases, finding variations among
different people.
Single nucleotide polymorphisms (SNPs) are mutations
at single nucleotide positions, and the haplotypes are the
sets of associating SNPs localized on one chromosome. It
has been estimated that there are about ten million common
SNPs in the human genome (Sachidanandam et al. 2001).
Genotyping and studying all SNPs in a candidate region is
costly and time-consuming for a large number of individ-
uals. It is essential to find some useful categories to improve
the genotyping performance. SNPs are not independently
distributing in the genome. Many SNPs have nonrandom
associations with each other, which is called the linkage
disequilibrium (LD) (Lewontin 1964). The LD association
between SNPs causes the redundancy of genetic informa-
tion. This redundancy makes it possible to overcome the
genotyping and genome study problem through SNP
selection. In the process of SNP selection, only a subset of
informative SNPs (tagSNPs or tagging SNPs) is chosen and
the rest, which have redundant information are removed
(Johnson et al. 2001). The selected SNPs can accurately
represent the rest of the SNPs, and have enough information
of original set for further study, while having little infor-
mation overlapping among them. The selection of tagSNPs
has become a very active research topic. Several compu-
tational methods have been proposed in the past few years.
These methods can be mainly separated to three species.
The first common method is based on the haplotype blocks.
It assumes human genome can be delimited as a set of
discrete blocks with limited diversity. That means there is a
very small set of common haplotypes shared by most of
the population within each block. Under this assumption,
these methods first identify haplotype blocks on the
M.-Z. Guo J. Wang (&) C.-y. Wang Y. Liu
School of Computer Science and Technology,
Harbin Institute of Technology, 150001 Harbin,
Heilongjiang, China
e-mail: wjking@hit.edu.cn
123
Soft Comput (2009) 13:1143–1151
DOI 10.1007/s00500-009-0419-z
剩余8页未读，继续阅读
资源评论
