{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T16:38:43Z","timestamp":1742402323035},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,3,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Recent studies have shown that a small subset of Single Nucleotide Polymorphisms (SNPs) (called tag SNPs) is sufficient to capture the haplotype patterns in a high linkage disequilibrium region. To find the minimum set of tag SNPs, exact algorithms for finding the optimal solution could take exponential time. On the other hand, approximation algorithms are more efficient but may fail to find the optimal solution.<\/jats:p>\n               <jats:p>Results: We propose a hybrid method that combines the ideas of the branch-and-bound method and the greedy algorithm. This method explores larger solution space to obtain a better solution than a traditional greedy algorithm. It also allows the user to adjust the efficiency of the program and quality of solutions. This algorithm has been implemented and tested on a variety of simulated and biological data. The experimental results indicate that our program can find better solutions than previous methods. This approach is quite general since it can be used to adapt other greedy algorithms to solve their corresponding problems.<\/jats:p>\n               <jats:p>Availability: The program is available upon request.<\/jats:p>\n               <jats:p>Contact: \u00a0kmchao@csie.ntu.edu.tw<\/jats:p>","DOI":"10.1093\/bioinformatics\/btk035","type":"journal-article","created":{"date-parts":[[2006,1,11]],"date-time":"2006-01-11T01:18:22Z","timestamp":1136942302000},"page":"685-691","source":"Crossref","is-referenced-by-count":17,"title":["A greedier approach for finding tag SNPs"],"prefix":"10.1093","volume":"22","author":[{"given":"Chia-Jung","family":"Chang","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University 1 \u00a0 1 \u00a0 \u00a0 Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yao-Ting","family":"Huang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University 1 \u00a0 1 \u00a0 \u00a0 Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kun-Mao","family":"Chao","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Taiwan University 1 \u00a0 1 \u00a0 \u00a0 Taipei, Taiwan"},{"name":"Graduate Institute of Networking and Multimedia, National Taiwan University 2 \u00a0 2 \u00a0 \u00a0 Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2006,1,10]]},"reference":[{"key":"2023012408541445900_b1","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1038\/nature04226","article-title":"A haplotype map of the human genome","volume":"437","author":"Altshuler","year":"2005","journal-title":"Nature"},{"key":"2023012408541445900_b2","first-page":"19","article-title":"Haplotypes and Informative SNP Selection Algorithms: Don't Block Out Information","author":"Bafna","year":"2003"},{"key":"2023012408541445900_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 analyses using linkage disequilibrium","volume":"74","author":"Carlson","year":"2004","journal-title":"Am. J Hum. Genet."},{"key":"2023012408541445900_b4","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2001"},{"key":"2023012408541445900_b5","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1146\/annurev.med.56.082103.104540","article-title":"Definition and clinical importance of haplotypes","volume":"56","author":"Crawfod","year":"2005","journal-title":"Annu. Rev. Med."},{"key":"2023012408541445900_b6","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":"2023012408541445900_b7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Garey","year":"1979"},{"key":"2023012408541445900_b8","doi-asserted-by":"crossref","first-page":"i195","DOI":"10.1093\/bioinformatics\/bti1021","article-title":"Tag SNP selection in genotype data for maximizing SNP prediction accuracy","volume":"21","author":"Halperin","year":"2005","journal-title":"Bioinformatics."},{"key":"2023012408541445900_b9","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1504\/IJBRA.2005.007904","article-title":"Linear reduction methods for tag SNP selection","volume":"1","author":"He","year":"2005","journal-title":"Int. J. Bioinformatics Res. Appl."},{"key":"2023012408541445900_b10","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1126\/science.293.5530.583b","article-title":"Genome research: map of the human genome 3.0","volume":"293","author":"Helmuth","year":"2001","journal-title":"Science"},{"key":"2023012408541445900_b11","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1126\/science.1105436","article-title":"Whole-genome patterns of common DNA variation in three human populations","volume":"307","author":"Hinds","year":"2005","journal-title":"Science"},{"key":"2023012408541445900_b12","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1186\/1471-2105-6-263","article-title":"Selecting additional tag SNPs for tolerating missing data in genotyping","volume":"6","author":"Huang","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023012408541445900_b13","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","article-title":"Generating samples under a Wright\u2013Fisher neutral model of genetic variation","volume":"18","author":"Hudson","year":"2002","journal-title":"Bioinformatics"},{"key":"2023012408541445900_b14","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":"2023012408541445900_b15","doi-asserted-by":"crossref","first-page":"7335","DOI":"10.1073\/pnas.102186799","article-title":"A dynamic programming algorithm for haplotype block partitioning","volume":"99","author":"Zhang","year":"2002","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012408541445900_b16","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1086\/376437","article-title":"Haplotype block partition with limited resources and applications to human chromosome 21 haplotype data","volume":"73","author":"Zhang","year":"2003","journal-title":"Am. J. Hum. Genet."},{"key":"2023012408541445900_b17","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1101\/gr.1837404","article-title":"Haplotype block partition and tag SNP selection using genotype data and their applications to association studies","volume":"14","author":"Zhang","year":"2004","journal-title":"Genome Res."},{"key":"2023012408541445900_b18","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1186\/1471-2105-5-89","article-title":"A double classification tree search algorithm for index SNP selection","volume":"5","author":"Zhang","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023012408541445900_b19","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.artmed.2005.01.009","article-title":"Efficient RNAi-based gene family knockdown via set cover optimization","volume":"35","author":"Zhao","year":"2005","journal-title":"Artif. Intell. Med."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/6\/685\/48840667\/bioinformatics_22_6_685.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/22\/6\/685\/48840667\/bioinformatics_22_6_685.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T09:35:53Z","timestamp":1674552953000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/22\/6\/685\/295987"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1,10]]},"references-count":19,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2006,3,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btk035","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2006,3,15]]},"published":{"date-parts":[[2006,1,10]]}}}