{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T00:32:11Z","timestamp":1770337931349,"version":"3.49.0"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Integrated analysis of single nucleotide polymorphisms (SNPs) and structure variations showed that the extent of linkage disequilibrium is common across different types of genetic variants. A subset of SNPs (called tag SNPs) is sufficient for capturing alleles of bi-allelic and even multi-allelic variants. However, accuracy and power of tag SNPs are affected by several factors, including genotyping failure, errors and tagging bias of certain alleles. In addition, different sets of tag SNPs should be selected for fulfilling requirements of various genotyping platforms and projects.<\/jats:p>\n               <jats:p>Results: This study formulates the problem of selecting tag SNPs into a four-objective optimization problem that minimizes the total amount of tag SNPs, maximizes tolerance for missing data, enlarges and balances detection power of each allele class. To resolve this problem, we propose evolutionary algorithms incorporated with greedy initialization to find non-dominated solutions considering all objectives simultaneously. This method provides users with great flexibility to extract different sets of tag SNPs for different platforms and scenarios (e.g. up to 100 tags and 10% missing rate). Compared to conventional methods, our method explores larger search space and requires shorter convergence time. Experimental results revealed strong and weak conflicts among these objectives. In particular, a small number of additional tag SNPs can provide sufficient tolerance and balanced power given the low missing and error rates of today's genotyping platforms.<\/jats:p>\n               <jats:p>Availability: The software is freely available at Bioinformatics online and http:\/\/cilab.cs.ccu.edu.tw\/service_dl.html<\/jats:p>\n               <jats:p>Contact: \u00a0ckting@cs.ccu.edu.tw; ythuang@cs.ccu.edu.tw<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq158","type":"journal-article","created":{"date-parts":[[2010,4,13]],"date-time":"2010-04-13T02:32:32Z","timestamp":1271125952000},"page":"1446-1452","source":"Crossref","is-referenced-by-count":13,"title":["Multi-objective tag SNPs selection using evolutionary algorithms"],"prefix":"10.1093","volume":"26","author":[{"given":"Chuan-Kang","family":"Ting","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Chung Cheng University, Chia-Yi 621, Taiwan"}]},{"given":"Wei-Ting","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Chung Cheng University, Chia-Yi 621, Taiwan"}]},{"given":"Yao-Ting","family":"Huang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Chung Cheng University, Chia-Yi 621, Taiwan"}]}],"member":"286","published-online":{"date-parts":[[2010,4,12]]},"reference":[{"key":"2023012507513986000_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":"2023012507513986000_B2","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":"2023012507513986000_B3","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1093\/bioinformatics\/btk035","article-title":"A greedier approach for finding tag SNPs","volume":"22","author":"Chang","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012507513986000_B4","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1109\/4235.996017","article-title":"A fast and elitist multiobjective genetic algorithm: NSGA-II","volume":"6","author":"Deb","year":"2002","journal-title":"IEEE Trans. Evol. Comput."},{"key":"2023012507513986000_B5","doi-asserted-by":"crossref","first-page":"1209","DOI":"10.1002\/humu.20775","article-title":"An unusual haplotype structure on human chromosome 8p23 derived from the inversion polymorphism","volume":"29","author":"Deng","year":"2008","journal-title":"Hum. Mutat."},{"key":"2023012507513986000_B6","doi-asserted-by":"crossref","first-page":"1842","DOI":"10.1093\/bioinformatics\/bth149","article-title":"Haplotype reconstruction from genotype data using imperfect phylogeny","volume":"20","author":"Halperin","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012507513986000_B7","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":"2023012507513986000_B8","volume-title":"Adaptation in Natural and Artificial Systems.","author":"Holland","year":"1975"},{"key":"2023012507513986000_B9","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":"2023012507513986000_B10","doi-asserted-by":"crossref","first-page":"2678","DOI":"10.1109\/CEC.2003.1299427","article-title":"Multiple single objective Pareto sampling","volume":"4","author":"Hughes","year":"2003","journal-title":"Proceeding of 2003 Congress on Evolutionary Computation"},{"key":"2023012507513986000_B11","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1109\/CEC.2005.1554688","article-title":"Evolutionary many-objective optimization: many once or one many?","volume-title":"Proceedings of 2005 IEEE Congress on Evolutionary Computation","author":"Hughes","year":"2005"},{"key":"2023012507513986000_B12","doi-asserted-by":"crossref","first-page":"3944","DOI":"10.1109\/CEC.2007.4424985","article-title":"MSOPS-II: a general-purpose many-objective optimiser","volume-title":"Proceedings of 2007 IEEE Congress on Evolutionary Computation","author":"Hughes","year":"2007"},{"key":"2023012507513986000_B13","first-page":"649","article-title":"Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems","volume-title":"Proceedings of 10th Genetic and Evolutionary Computation Conference","author":"Ishibuchi","year":"2008"},{"key":"2023012507513986000_B14","first-page":"2419","article-title":"Evolutionary many-objective optimization: a short review","volume-title":"Proceedings of 2008 IEEE Congress on Evolutionary Computation","author":"Ishibuchi","year":"2008"},{"key":"2023012507513986000_B15","doi-asserted-by":"crossref","first-page":"3983","DOI":"10.1109\/CEC.2007.4424990","article-title":"Ranking-dominance and many-objective optimization","volume-title":"Proceedings of 2007 IEEE Congress on Evolutionary Computation","author":"Kukkonen","year":"2007"},{"key":"2023012507513986000_B16","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1159\/000092141","article-title":"The impact of missing and erroneous genotypes on tagging SNP selection and power of subsequent association tests","volume":"61","author":"Liu","year":"2006","journal-title":"Hum. Hered."},{"key":"2023012507513986000_B17","doi-asserted-by":"crossref","first-page":"1166","DOI":"10.1038\/ng.238","article-title":"Integrated detection and population-genetic analysis of SNPs and copy number variation","volume":"40","author":"McCarroll","year":"2008","journal-title":"Nat. Genet."},{"key":"2023012507513986000_B18","first-page":"2066","article-title":"Evolutionary many-objective optimisation: an exploratory analysis","volume-title":"Proceedings of 2003 IEEE Congress on Evolutionary Computation","author":"Purshouse","year":"2003"},{"key":"2023012507513986000_B19","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1038\/nature05329","article-title":"Global variation in copy number in the human genome","volume":"444","author":"Redon","year":"2006","journal-title":"Nature"},{"key":"2023012507513986000_B20","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1086\/502802","article-title":"A fast and flexible statistical model for large-scale population genotype data: applications to inferring missing genotypes and haplotypic phase","volume":"78","author":"Scheet","year":"2006","journal-title":"Am. J. Hum. Genet."},{"key":"2023012507513986000_B21","doi-asserted-by":"crossref","first-page":"1162","DOI":"10.1086\/379378","article-title":"A comparison of Bayesian methods for haplotype reconstruction from population genotype data","volume":"73","author":"Stephens","year":"2003","journal-title":"Am. J. Hum. Genet."},{"key":"2023012507513986000_B22","first-page":"2","article-title":"Uniform crossover in genetic algorithms","volume-title":"Proceedings of the 3rd International Conference on Genetic Algorithms.","author":"Syswerda","year":"1989"},{"key":"2023012507513986000_B23","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1007\/978-3-540-70928-2_56","article-title":"Pareto-, aggregation-, and indicator-based methods in many-objective optimization","volume-title":"Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization","author":"Wagner","year":"2007"},{"key":"2023012507513986000_B24","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1101\/gr.1837404","article-title":"Haplotype block partitioning and tag SNP selection using genotype data and their applications to association studies","volume":"14","author":"Zhang","year":"2004","journal-title":"Genome Res."},{"key":"2023012507513986000_B25","doi-asserted-by":"crossref","first-page":"1694","DOI":"10.1093\/bioinformatics\/18.12.1694","article-title":"GENECOUNTING: haplotype analysis with missing genotypes","volume":"18","author":"Zhao","year":"2002","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/11\/1446\/48851439\/bioinformatics_26_11_1446.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/11\/1446\/48851439\/bioinformatics_26_11_1446.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T07:52:08Z","timestamp":1674633128000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/11\/1446\/203000"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4,12]]},"references-count":25,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2010,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq158","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,6,1]]},"published":{"date-parts":[[2010,4,12]]}}}