{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:39:28Z","timestamp":1773272368533,"version":"3.50.1"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: 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.<\/jats:p>\n               <jats:p>Results: We devised an improved algorithm for tagSNP selection using the pairwise r2 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.<\/jats:p>\n               <jats:p>Availability: A computer program named FESTA has been developed based on this algorithm. The program is freely available and can be downloaded at<\/jats:p>\n               <jats:p>Contact: \u00a0qin@umich.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0<\/jats:p>","DOI":"10.1093\/bioinformatics\/bti762","type":"journal-article","created":{"date-parts":[[2005,11,4]],"date-time":"2005-11-04T01:18:46Z","timestamp":1131067126000},"page":"220-225","source":"Crossref","is-referenced-by-count":37,"title":["An efficient comprehensive search algorithm for tagSNP selection using linkage disequilibrium criteria"],"prefix":"10.1093","volume":"22","author":[{"given":"Zhaohui S.","family":"Qin","sequence":"first","affiliation":[{"name":"Center for Statistical Genetics, Department of Biostatistics, School of Public Health, University of Michigan 1 \u00a0 1 \u00a0 \u00a0 1420 Washington Heights, Ann Arbor, MI 48109-2029, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shyam","family":"Gopalakrishnan","sequence":"additional","affiliation":[{"name":"Center for Statistical Genetics, Department of Biostatistics, School of Public Health, University of Michigan 1 \u00a0 1 \u00a0 \u00a0 1420 Washington Heights, Ann Arbor, MI 48109-2029, USA"},{"name":"Department of Electrical Engineering and Computer Science, University of Michigan 2 \u00a0 2 \u00a0 \u00a0 Ann Arbor, MI 48109-2122, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gon\u00e7alo R.","family":"Abecasis","sequence":"additional","affiliation":[{"name":"Center for Statistical Genetics, Department of Biostatistics, School of Public Health, University of Michigan 1 \u00a0 1 \u00a0 \u00a0 1420 Washington Heights, Ann Arbor, MI 48109-2029, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2005,11,3]]},"reference":[{"key":"2023012408301355300_b1","first-page":"466","article-title":"Selection of minimum subsets of single nucleotide polymorphisms to capture haplotype block diversity","author":"Avi-Itzhak","year":"2003","journal-title":"Pac. Symp. Biocomput."},{"key":"2023012408301355300_b2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0168-9525(03)00022-2","article-title":"Using haplotype blocks to map human complex trait loci","volume":"19","author":"Cardon","year":"2003","journal-title":"Trends Genet."},{"key":"2023012408301355300_b3","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1086\/381000","article-title":"Selecting a maximally informative set of single-nucleotide polymorphisms for association analysis using linkage disequilibrium","volume":"74","author":"Carlson","year":"2004","journal-title":"Am. J. Hum. Genet."},{"key":"2023012408301355300_b4","doi-asserted-by":"crossref","first-page":"1831","DOI":"10.1159\/000073729","article-title":"Detecting disease associations due to linkage disequilibrium using haplotype tags: a class of tests and the determinants of statistical power","volume":"56","author":"Chapman","year":"2003","journal-title":"Hum. Hered."},{"key":"2023012408301355300_b5","doi-asserted-by":"crossref","first-page":"1580","DOI":"10.1126\/science.278.5343.1580","article-title":"Variations on a theme: cataloging human DNA sequence variation","volume":"278","author":"Collins","year":"1997","journal-title":"Science"},{"key":"2023012408301355300_b6","volume-title":"Introduction to algorithms","author":"Cormen","year":"2001","edition":"2nd edition"},{"key":"2023012408301355300_b7","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1038\/ng1001-229","article-title":"High-resolution haplotype structure in the human genome","volume":"29","author":"Daly","year":"2001","journal-title":"Nat. Genet."},{"key":"2023012408301355300_b8","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1038\/nature00864","article-title":"A first generation slinkage disequilibrium map of human chromosome 22","volume":"418","author":"Dawson","year":"2002","journal-title":"Nature"},{"key":"2023012408301355300_b9","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1006\/geno.1995.9003","article-title":"A comparison of linkage disequilibrium measures for fine-scale mapping","volume":"29","author":"Devlin","year":"1995","journal-title":"Genomics"},{"key":"2023012408301355300_b10","doi-asserted-by":"crossref","first-page":"2225","DOI":"10.1126\/science.1069424","article-title":"The structure of haplotype blocks in the human genome","volume":"296","author":"Gabriel","year":"2002","journal-title":"Science"},{"key":"2023012408301355300_b11","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1016\/j.tig.2003.09.006","article-title":"Genome scans and candidate gene approaches in the study of common diseases and variable drug responses","volume":"19","author":"Goldstein","year":"2003","journal-title":"Trends Genet."},{"key":"2023012408301355300_b12","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/s00439-003-1017-2","article-title":"Entropy-based SNP selection for genetic association studies","volume":"114","author":"Hampe","year":"2003","journal-title":"Hum Genet."},{"key":"2023012408301355300_b13","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1038\/hdy.1974.89","article-title":"Estimation of linkage disequilibrium in randomly mating populations","volume":"33","author":"Hill","year":"1974","journal-title":"Heredity"},{"key":"2023012408301355300_b14","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1093\/genetics\/60.3.615","article-title":"The effects of inbreeding at loci with heterozygote advantage","volume":"60","author":"Hill","year":"1968","journal-title":"Genetics"},{"key":"2023012408301355300_b15","doi-asserted-by":"crossref","first-page":"1633","DOI":"10.1101\/gr.2570004","article-title":"Optimal haplotype block-free selection of tagging SNPs for genome-wide association studies","volume":"14","author":"Halld\u00f3rsson","year":"2004","journal-title":"Genome Res."},{"key":"2023012408301355300_b16","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1038\/ng1001-233","article-title":"Haplotype tagging for the identification of common disease genes","volume":"29","author":"Johnson","year":"2001","journal-title":"Nat. Genet."},{"key":"2023012408301355300_b17","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1038\/ng1001-217","article-title":"Intensely punctuate meiotic recombination in the class II region of the major of histocompatibility complex","volume":"29","author":"Jeffreys","year":"2001","journal-title":"Nat. Genet."},{"key":"2023012408301355300_b18","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1093\/bioinformatics\/19.2.287","article-title":"Efficient selective screening of haplotype tag SNPs","volume":"19","author":"Ke","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012408301355300_b19","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1086\/425587","article-title":"Finding haplotype tagging SNPs by use of principal components analysis","volume":"75","author":"Lin","year":"2004","journal-title":"Am. J. Hum. Genet."},{"key":"2023012408301355300_b20","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1086\/376561","article-title":"Selection of genetic markers for association analyses, using linkage disequilibrium and haplotypes","volume":"73","author":"Meng","year":"2003","journal-title":"Am. J. Hum. Genet."},{"key":"2023012408301355300_b21","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1086\/338446","article-title":"Bayesian haplotype inference for multiple linked single-nucleotide polymorphisms","volume":"70","author":"Niu","year":"2002","journal-title":"Am. J. Hum. Genet."},{"key":"2023012408301355300_b22","doi-asserted-by":"crossref","first-page":"1719","DOI":"10.1126\/science.1065573","article-title":"Blocks of limited haplotype diversity revealed by high-resolution scanning of human chromosome 21","volume":"294","author":"Patil","year":"2001","journal-title":"Science"},{"key":"2023012408301355300_b23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1086\/321275","article-title":"Linkage disequilibrium in humans: models and data","volume":"69","author":"Pritchard","year":"2001","journal-title":"Am. J. Hum. Genet."},{"key":"2023012408301355300_b24","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1038\/35075590","article-title":"Linkage disequilibrium in the human genome","volume":"411","author":"Reich","year":"2001","journal-title":"Nature"},{"key":"2023012408301355300_b25","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1002\/gepi.20056","article-title":"Characterization of multilocus linkage disequilibrium","volume":"28","author":"Rinaldo","year":"2005","journal-title":"Genet. Epidemiol."},{"key":"2023012408301355300_b26","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1038\/35057149","article-title":"A map of human genome sequence variation containing 1.42 million single nucleotide polymorphisms","volume":"409","author":"Sachidanandam","year":"2001","journal-title":"Nature"},{"key":"2023012408301355300_b27","doi-asserted-by":"crossref","first-page":"9900","DOI":"10.1073\/pnas.1633613100","article-title":"Minimal haplotype tagging","volume":"100","author":"Sebastiani","year":"2003","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012408301355300_b28","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1159\/000071807","article-title":"Choosing haplotype-tagging SNPs based on unphased genotype data using preliminary sample of unrelated subjects with an example from the multiethic cohort study","volume":"55","author":"Stram","year":"2003","journal-title":"Hum. Hered."},{"key":"2023012408301355300_b29","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1186\/1479-7364-2-2-144","article-title":"Software for tag single nucleotide polymorphism selection","volume":"2","author":"Stram","year":"2005","journal-title":"Hum. Genomics"},{"key":"2023012408301355300_b30","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1038\/nature02168","article-title":"The International HapMap Project","volume":"426","author":"The International HapMap Consortium","year":"2003","journal-title":"Nature"},{"key":"2023012408301355300_b31","doi-asserted-by":"crossref","first-page":"7335","DOI":"10.1073\/pnas.102186799","article-title":"A dynamic programming algorithm for haplotype partitioning","volume":"99","author":"Zhang","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012408301355300_b32","doi-asserted-by":"crossref","first-page":"1300","DOI":"10.1093\/bioinformatics\/btg142","article-title":"HaploBlockFinder: haplotype block analysis","volume":"19","author":"Zhang","year":"2003","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/2\/220\/48837837\/bioinformatics_22_2_220.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/2\/220\/48837837\/bioinformatics_22_2_220.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T08:32:01Z","timestamp":1674549121000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/22\/2\/220\/422422"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11,3]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bti762","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2006,1,15]]},"published":{"date-parts":[[2005,11,3]]}}}