{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T13:56:54Z","timestamp":1722866214577},"reference-count":22,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":3015,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: In genetic studies of complex diseases, haplotypes provide more information than genotypes. However, haplotyping is much more difficult than genotyping using biological techniques. Therefore effective computational techniques have been in demand. The individual haplotyping problem is the computational problem of inducing a pair of haplotypes from an individual's aligned SNP fragments. Based on various optimal criteria and including different extra information, many models for the problem have been proposed. Higher accuracy of the models has been an important issue in the study of haplotype reconstruction.<\/jats:p>\n               <jats:p>Results: The current article proposes a highly accurate model for the single individual haplotyping problem based on weighted fragments and genotypes with errors. The model is proved to be NP-hard even with gapless fragments. Based on the characteristics of Single Nucleotide Polymorphism (SNP) fragments, a parameterized algorithm of time complexity O(nk22k2 + m log m + mk1) is developed, where m is the number of fragments, n is the number of SNP sites, k1 is the maximum number of SNP sites that a fragment covers (no more than n and usually smaller than 10) and k2 is the maximum number of the fragments covering a SNP site (usually no more than 19). Extensive experiments show that this model is more accurate in haplotype reconstruction than other models.<\/jats:p>\n               <jats:p>Availability: The program of the parameterized algorithm can be obtained by sending an email to the corresponding author.<\/jats:p>\n               <jats:p>Contact: \u00a0jxwang@mail.csu.edu.cn<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn147","type":"journal-article","created":{"date-parts":[[2008,6,27]],"date-time":"2008-06-27T07:43:13Z","timestamp":1214552593000},"page":"i105-i113","source":"Crossref","is-referenced-by-count":18,"title":["A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments and genotype with errors"],"prefix":"10.1093","volume":"24","author":[{"given":"Minzhu","family":"Xie","sequence":"first","affiliation":[{"name":"1 School of Information Science and Engineering, Central South University, Changsha 410083, 2College of Physics and Information Science, Hunan Normal University, Changsha 410081, China and 3Department of Computer Science, Texas A&M University, College Station, TX 77843, USA"},{"name":"1 School of Information Science and Engineering, Central South University, Changsha 410083, 2College of Physics and Information Science, Hunan Normal University, Changsha 410081, China and 3Department of Computer Science, Texas A&M University, College Station, TX 77843, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[{"name":"1 School of Information Science and Engineering, Central South University, Changsha 410083, 2College of Physics and Information Science, Hunan Normal University, Changsha 410081, China and 3Department of Computer Science, Texas A&M University, College Station, TX 77843, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianer","family":"Chen","sequence":"additional","affiliation":[{"name":"1 School of Information Science and Engineering, Central South University, Changsha 410083, 2College of Physics and Information Science, Hunan Normal University, Changsha 410081, China and 3Department of Computer Science, Texas A&M University, College Station, TX 77843, USA"},{"name":"1 School of Information Science and Engineering, Central South University, Changsha 410083, 2College of Physics and Information Science, Hunan Normal University, Changsha 410081, China and 3Department of Computer Science, Texas A&M University, College Station, TX 77843, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,7,1]]},"reference":[{"key":"2023020210351845900_B1","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1186\/1471-2156-5-22","article-title":"Comparison of the accuracy of methods of computational haplotype inference using a large empirical dataset","volume":"5","author":"Adkins","year":"2004","journal-title":"BMC Genet"},{"key":"2023020210351845900_B2","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1038\/sj.ejhg.5200619","article-title":"Haplotypes vs single marker linkage disequilibrium tests: what do we gain?","volume":"9","author":"Akey","year":"2001","journal-title":"Eur. J. Hum. Genet."},{"key":"2023020210351845900_B3","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1007\/BF02945456","article-title":"The haplotyping problem: an overview of computational models and solutions","volume":"18","author":"Bonizzoni","year":"2003","journal-title":"J. Comp. Sci. Technol."},{"key":"2023020210351845900_B4","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1093\/biostatistics\/kxl042","article-title":"Exploration, normalization, and genotype calls of high-density oligonucleotide SNP array data","volume":"8","author":"Carvalho","year":"2007","journal-title":"Biostatistics"},{"key":"2023020210351845900_B5","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1287\/ijoc.1040.0073","article-title":"Opportunities for combinatorial optimization in computational biology","volume":"16","author":"Greenberg","year":"2004","journal-title":"INFORMS J. Comput."},{"key":"2023020210351845900_B6","first-page":"294","article-title":"Comparing assemblies using fragments and mate-pairs. In","volume-title":"Lecture Notes in Computer Science","author":"Huson","year":"2001"},{"key":"2023020210351845900_B7","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1038\/35057062","article-title":"Initial sequencing and analysis of the human genome","volume":"409","author":"International Human Genome Sequencing Consortium","year":"2001","journal-title":"Nature"},{"key":"2023020210351845900_B8","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1086\/382284","article-title":"Incorporating genotyping uncertainty in haplotype inference for single-nucleotide polymorphisms","volume":"74","author":"Kang","year":"2004","journal-title":"Am. J. Hum. Genet."},{"key":"2023020210351845900_B9","first-page":"182","article-title":"SNPs problems, complexity and algorithms. In","volume-title":"Lecture Notes in Computer Science","author":"Lancia","year":"2001"},{"key":"2023020210351845900_B10","doi-asserted-by":"crossref","first-page":"e254","DOI":"10.1371\/journal.pbio.0050254","article-title":"The diploid genome sequence of an individual human","volume":"5","author":"Levy","year":"2007","journal-title":"PLoS Biology"},{"key":"2023020210351845900_B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/bib\/3.1.23","article-title":"Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem","volume":"3","author":"Lippert","year":"2002","journal-title":"Brief. Bioinform."},{"key":"2023020210351845900_B12","first-page":"202","article-title":"A dataset generator for whole genome shotgun sequencing. In","author":"Myers","year":"1999"},{"key":"2023020210351845900_B13","first-page":"266","article-title":"Fast hare: a fast heuristic for single individual SNP haplotype reconstruction. In","volume-title":"Lecture Notes in Computer Science","author":"Panconesi","year":"2004"},{"key":"2023020210351845900_B14","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1038\/nature04226","article-title":"A haplotype map of the human genome","volume":"437","author":"The International HapMap Consortium","year":"2005","journal-title":"Nature"},{"key":"2023020210351845900_B15","doi-asserted-by":"crossref","first-page":"1304","DOI":"10.1126\/science.1058040","article-title":"The sequence of the human genome","volume":"291","author":"Venter","year":"2001","journal-title":"Science"},{"key":"2023020210351845900_B16","doi-asserted-by":"crossref","first-page":"2456","DOI":"10.1093\/bioinformatics\/bti352","article-title":"Haplotype reconstruction from SNP fragments by minimum error correction","volume":"21","author":"Wang","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020210351845900_B17","doi-asserted-by":"crossref","first-page":"1459","DOI":"10.1093\/bioinformatics\/btm131","article-title":"A multi-array multi-SNP genotyping algorithm for affymetrix SNP microarrays","volume":"23","author":"Xiao","year":"2007","journal-title":"Bioinformatics"},{"key":"2023020210351845900_B18","unstructured":"Xie\n              M\n            \n            \u00a0WangJ\n          An improved (and practical) parameterized algorithm for the individual haplotyping problem mfr with mate-pairs\n          Algorithmica\n          2007\n          DOI 10.1007\/s00453-007-9150-2, http:\/\/www.springerlink.com\/content\/p2202u8wrnr65117\/"},{"key":"2023020210351845900_B19","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1142\/S0219720007002710","article-title":"Research on parameterized algorithms of the individual haplotyping problem","volume":"5","author":"Xie","year":"2007","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023020210351845900_B20","doi-asserted-by":"crossref","first-page":"105","DOI":"10.2174\/157489306775330570","article-title":"Models and algorithms for haplotyping problem","volume":"1","author":"Zhang","year":"2006","journal-title":"Curr. Bioinform."},{"key":"2023020210351845900_B21","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/j.compbiolchem.2005.05.001","article-title":"Haplotype assembly from aligned weighted SNP fragments","volume":"29","author":"Zhao","year":"2005","journal-title":"Comput. Biol. Chem."},{"key":"2023020210351845900_B22","volume-title":"Statistical Methods for Haplotype Analysis with Genotyping Errors","author":"Zhu","year":"2006"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i105\/49050132\/bioinformatics_24_13_i105.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/24\/13\/i105\/49050132\/bioinformatics_24_13_i105.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T12:12:24Z","timestamp":1675339944000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/24\/13\/i105\/227599"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,1]]},"references-count":22,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2008,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn147","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2008,7,1]]},"published":{"date-parts":[[2008,7,1]]}}}