An efficient comprehensive search algorithm for tagSNP selection using linkage disequilibrium criteria.
BACKGROUND
Selecting SNP markers for genome-wide association studies is an important and challenging task. The goal is to minimize the number of markers selected for genotyping in a particular platform and therefore reduce genotyping cost while simultaneously maximizing the information content provided by selected markers.


RESULTS
We devised an improved algorithm for tagSNP selection using the pairwise r(2) criterion. We first break down large marker sets into disjoint pieces, where more exhaustive searches can replace the greedy algorithm for tagSNP selection. These exhaustive searches lead to smaller tagSNP sets being generated. In addition, our method evaluates multiple solutions that are equivalent according to the linkage disequilibrium criteria to accommodate additional constraints. Its performance was assessed using HapMap data.


BACKGROUND
A computer program named FESTA has been developed based on this algorithm. The program is freely available and can be downloaded at http://www.sph.umich.edu/csg/qin/FESTA/
Qin
Zhaohui S
ZS
Center for Statistical Genetics, Department of Biostatistics, School of Public Health, University of Michigan 1420 Washington Heights, Ann Arbor, MI 48109-2029, USA. qin@umich.edu
Gopalakrishnan
Shyam
S
Abecasis
Gonçalo R
GR
D000465:Algorithms; D001185:Artificial Intelligence; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D020224:Expressed Sequence Tags; D005819:Genetic Markers / Q000235:genetics; D015810:Linkage Disequilibrium / Q000235:genetics*; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated / Q000379:methods; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software
D005819:Genetic Markers