Title: Linear reduction method for predictive and informative tag SNP selection

Authors: Jingwu He, Kelly Westbrooks, Alexander Zelikovsky

Addresses: Department of Computer Science, Georgia State University, 34 Peachtree Str., suite 1450, Atlanta, GA 30303, USA. ' Department of Computer Science, Georgia State University, 34 Peachtree Str., suite 1450, Atlanta, GA 30303, USA. ' Department of Computer Science, Georgia State University, 34 Peachtree Str., suite 1450, Atlanta, GA 30303, USA

Abstract: Constructing a complete human haplotype map is helpful when associating complex diseases with their related SNPs. Unfortunately, the number of SNPs is very large and it is costly to sequence many individuals. Therefore, it is desirable to reduce the number of SNPs that should be sequenced to a small number of informative representatives called tag SNPs. In this paper, we propose a new linear algebra-based method for selecting and using tag SNPs. We measure the quality of our tag SNP selection algorithm by comparing actual SNPs with SNPs predicted from selected linearly independent tag SNPs. Our experiments show that for sufficiently long haplotypes, knowing only 0.4% of all SNPs the proposed linear reduction method predicts an unknown haplotype with the error rate below 2% based on 10% of the population.

Keywords: single nucleotide polymorphisms; tag SNPs; linear independence; linear reduction; bioinformatics; human haplotype map; complex diseases; tag SNP selection; predictive tagging.

DOI: 10.1504/IJBRA.2005.007904

International Journal of Bioinformatics Research and Applications, 2005 Vol.1 No.3, pp.249 - 260

Published online: 30 Sep 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article