Please use this identifier to cite or link to this item:
Title: Effective algorithms for tag SNP selection
Authors: Liu, T.-F.
Sung, W.-K. 
Li, Y.
Liu, J.-J.
Mittal, A.
Mao, P.-L.
Keywords: Tag SNP selection
Tag SNP selection by A* Algorithm
Tag SNP selection by decision tree
Issue Date: 2005
Citation: Liu, T.-F.,Sung, W.-K.,Li, Y.,Liu, J.-J.,Mittal, A.,Mao, P.-L. (2005). Effective algorithms for tag SNP selection. Journal of Bioinformatics and Computational Biology 3 (5) : 1089-1106. ScholarBank@NUS Repository.
Abstract: Single nucleotide polymorphisms (SNPs), due to their abundance and low mutation rate, are very useful genetic markers for genetic association studies. However, the current genotyping technology cannot afford to genotype all common SNPs in all the genes. By making use of linkage disequilibrium, we can reduce the experiment cost by genotyping a subset of SNPs, called Tag SNPs, which have a strong association with the ungenotyped SNPs, while are as independent from each other as possible. The problem of selecting Tag SNPs is NP-complete; when there are large number of SNPs, in order to avoid extremely long computational time, most of the existing Tag SNP selection methods first partition the SNPs into blocks based on certain block definitions, then Tag SNPs are selected in each block by brute-force search. The size of the Tag SNP set obtained in this way may usually be reduced further due to the inter-dependency among blocks. This paper proposes two algorithms, TSSA and TSSD, to tackle the block-independent Tag SNP selection problem. TSSA is based on A* search algorithm, and TSSD is a heuristic algorithm. Experiments show that TSSA can find the optimal solutions for medium-sized problems in reasonable time, while TSSD can handle very large problems and report approximate solutions very close to the optimal ones. © Imperial College Press.
Source Title: Journal of Bioinformatics and Computational Biology
ISSN: 02197200
DOI: 10.1142/S0219720005001521
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Oct 26, 2020

Page view(s)

checked on Oct 25, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.