{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,22]],"date-time":"2024-06-22T15:55:55Z","timestamp":1719071755977},"reference-count":36,"publisher":"Oxford University Press (OUP)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Inference of haplotypes from genotype data is crucial and challenging for many vitally important studies. The first, and most critical step, is the ascertainment of a biologically sound model to be optimized. Many models that have been proposed rely partially or entirely on reducing the number of unique haplotypes in the solution.<\/jats:p>\n               <jats:p>Results: This article examines the parsimony of haplotypes using known haplotypes as well as genotypes from the HapMap project. Our study reveals that there are relatively few unique haplotypes, but not always the least possible, for the datasets with known solutions. Furthermore, we show that there are frequently very large numbers of parsimonious solutions, and the number increases exponentially with increasing cardinality. Moreover, these solutions are quite varied, most of which are not consistent with the true solutions. These results quantify the limitations of the Pure Parsimony model and demonstrate the imperative need to consider additional properties for haplotype inference models. At a higher level, and with broad applicability, this article illustrates the power of combinatorial methods to tease out imperfections in a given biological model.<\/jats:p>\n               <jats:p>Contact: \u00a0weixiong.zhang@wustl.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btn572","type":"journal-article","created":{"date-parts":[[2008,11,6]],"date-time":"2008-11-06T01:14:26Z","timestamp":1225934066000},"page":"68-74","source":"Crossref","is-referenced-by-count":8,"title":["How frugal is mother nature with haplotypes?"],"prefix":"10.1093","volume":"25","author":[{"given":"Sharlee","family":"Climer","sequence":"first","affiliation":[{"name":"1 Department of Computer Science and Engineering, 2Department of Cardiology, 3Division of Biostatistics, 4Department of Biology and 5Department of Genetics, Washington University, St. Louis, MO, USA"},{"name":"1 Department of Computer Science and Engineering, 2Department of Cardiology, 3Division of Biostatistics, 4Department of Biology and 5Department of Genetics, Washington University, St. Louis, MO, USA"},{"name":"1 Department of Computer Science and Engineering, 2Department of Cardiology, 3Division of Biostatistics, 4Department of Biology and 5Department of Genetics, Washington University, St. Louis, MO, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerold","family":"J\u00e4ger","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science and Engineering, 2Department of Cardiology, 3Division of Biostatistics, 4Department of Biology and 5Department of Genetics, Washington University, St. Louis, MO, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan R.","family":"Templeton","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science and Engineering, 2Department of Cardiology, 3Division of Biostatistics, 4Department of Biology and 5Department of Genetics, Washington University, St. Louis, MO, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weixiong","family":"Zhang","sequence":"additional","affiliation":[{"name":"1 Department of Computer Science and Engineering, 2Department of Cardiology, 3Division of Biostatistics, 4Department of Biology and 5Department of Genetics, Washington University, St. Louis, MO, USA"},{"name":"1 Department of Computer Science and Engineering, 2Department of Cardiology, 3Division of Biostatistics, 4Department of Biology and 5Department of Genetics, Washington University, St. Louis, MO, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2008,11,4]]},"reference":[{"key":"2023013110033482300_B1","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1002\/gepi.20185","article-title":"Understanding the accuracy of statistical haplotype inference with sequence data of known phase","volume":"31","author":"Andr\u00e9s","year":"2007","journal-title":"Genet. Epi."},{"key":"2023013110033482300_B2","article-title":"Mathematical approaches to the pure parsimony problem","volume-title":"Technical Report S40","author":"Blain","year":"2005"},{"key":"2023013110033482300_B3","first-page":"254","article-title":"A new integer programming formulation for the pure parsimony problem in haplotype analysis","volume-title":"Proceedings of 2004 Workshop on Algorithms in Bioinformatics (WABI)","author":"Brown","year":"2004"},{"key":"2023013110033482300_B4","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1109\/TCBB.2006.24","article-title":"Integer programming approaches to haplotype inference by pure parsimony","volume":"3","author":"Brown","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023013110033482300_B5","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1142\/9781860947575_0027","article-title":"Toward an algebraic understanding of haplotype inference pure parsimony","volume-title":"Proceedings of the Computational Systems Bioinformatics Conference","author":"Brown","year":"2006"},{"key":"2023013110033482300_B6","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/11557067_11","article-title":"On the complexity of several haplotyping problems","volume-title":"5th Workshop on Algorithms in Bioinformatics (WABI 2005).","author":"Cilibrasi","year":"2005"},{"key":"2023013110033482300_B7","first-page":"111","article-title":"Inference of haplotypes from PCR-amplified samples of diploid populations","volume":"77","author":"Clark","year":"1990","journal-title":"Mol. Biol. Evol."},{"key":"2023013110033482300_B8","first-page":"55","article-title":"Stochastic local search for large-scale instances of the haplotype inference problem by pure parsimony","volume":"63","author":"Di Gaspero","year":"2008","journal-title":"J. Algorithm. Logic Inform. Cogn."},{"key":"2023013110033482300_B9","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1145\/640075.640088","article-title":"Large scale reconstruction of haplotypes from genotype data","volume-title":"Proceedings of the Seventh Annual International Conference on Research in Computational Molecular Biology.","author":"Eskin","year":"2003"},{"key":"2023013110033482300_B10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness.","author":"Garey","year":"1979"},{"key":"2023013110033482300_B11","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-540-73433-8_10","article-title":"Efficient haplotype inference with pseudo-boolean optimization","volume-title":"Proceedings of Algebraic Biology","author":"Graca","year":"2007"},{"key":"2023013110033482300_B12","first-page":"183","article-title":"A practical algorithm for optimal inference of haplotypes from diploid populations","volume-title":"Proceedings of the Eighth International Conference on Intelligent System for Molecular Biology","author":"Gusfield","year":"2000"},{"key":"2023013110033482300_B13","first-page":"166","article-title":"Haplotyping as perfect phylogeny: conceptual framework and efficient solutions","volume-title":"Research in Computational Molecular Biology (RECOMB '02)","author":"Gusfield","year":"2002"},{"key":"2023013110033482300_B14","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1007\/3-540-44888-8_11","article-title":"Haplotype inference by pure parsimony","volume-title":"14th Annual Symposium on Combinatorial Pattern Matching (CPM'03).","author":"Gusfield","year":"2003"},{"key":"2023013110033482300_B15","first-page":"1","article-title":"Haplotype inference","volume-title":"Handbook on Bioinformatics","author":"Gusfield","year":"2005"},{"key":"2023013110033482300_B16","first-page":"26","article-title":"Combinatorial problems arising in SNP and haplotype analysis","volume-title":"Discrete Mathematics and Theoretical Computer Science, Proceedings of DMTCS 2003.","author":"Halldorsson","year":"2003"},{"key":"2023013110033482300_B17","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1089\/cmb.2005.12.1261","article-title":"An approximation algorithm for haplotype inference by maximum parsimony","volume":"12","author":"Huang","year":"2005","journal-title":"J. Comput. Biol."},{"key":"2023013110033482300_B18","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.orl.2005.05.007","article-title":"A polynomial case of the parsimony haplotyping problem","volume":"34","author":"Lancia","year":"2006","journal-title":"Operations Res. Lett."},{"key":"2023013110033482300_B19","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1287\/ijoc.1040.0085","article-title":"Haplotyping populations by pure parsimony: Complexity of exact and approximation algorithms","volume":"16","author":"Lancia","year":"2004","journal-title":"INFORMS J. Comput."},{"key":"2023013110033482300_B20","doi-asserted-by":"crossref","first-page":"3475","DOI":"10.1093\/bioinformatics\/bti572","article-title":"A parsimonious tree-grow method for haplotype inference","volume":"21","author":"Li","year":"2005","journal-title":"Bioinformatics"},{"key":"2023013110033482300_B21","first-page":"104","article-title":"Efficient haplotype inference with Boolean satisfiability","volume-title":"National Conference in Artificial Intelligence (AAAI)","author":"Lynce","year":"2006"},{"key":"2023013110033482300_B22","article-title":"Efficient and tight upper bounds for haplotype inference","author":"Marques-Silva","year":"2006","journal-title":"Technical Report 16"},{"key":"2023013110033482300_B23","article-title":"Improved lower bounds for SAT-based haplotype inference","author":"Marques-Silva","year":"2006","journal-title":"Technical Report 17"},{"key":"2023013110033482300_B24","first-page":"259","article-title":"Linear assignment problems","volume":"31","author":"Martello","year":"1987","journal-title":"Ann. Discrete Math."},{"key":"2023013110033482300_B25","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1126\/science.1117196","article-title":"A fine-scale map of recombination rates and hotspots across the human genome","volume":"310","author":"Myers","year":"2005","journal-title":"Science"},{"key":"2023013110033482300_B26","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":"2023013110033482300_B27","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1093\/genetics\/165.2.915","article-title":"Analysis and exploration of the use of rule-based algorithms and consensus methods for the inferral of haplotypes","volume":"165","author":"Orzack","year":"2003","journal-title":"Genetics"},{"key":"2023013110033482300_B28","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0010-4655(96)00062-8","article-title":"Searching for backbones \u2013 an efficient parallel algorithm for the traveling salesman problem","volume":"96","author":"Schneider","year":"1996","journal-title":"Comput. Phys. Commun."},{"key":"2023013110033482300_B29","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1109\/TCBB.2006.40","article-title":"Islands of tractability for parsimony haplotyping","volume":"3","author":"Sharan","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023013110033482300_B30","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":"2023013110033482300_B31","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1534\/genetics.104.030080","article-title":"Tree scanning: a method for using haplotype trees in genotype\/phenotype association studies","volume":"169","author":"Templeton","year":"2005","journal-title":"Genetics"},{"key":"2023013110033482300_B32","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":"2023013110033482300_B33","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":"2023013110033482300_B34","doi-asserted-by":"crossref","first-page":"824","DOI":"10.2991\/jcis.2006.243","article-title":"Computational experiments on algorithms for haplotype inference problems by pure parsimony","volume-title":"Proceedings of the 9th Joint Conference on Information Sciences (JCIS)","author":"Wang","year":"2006"},{"key":"2023013110033482300_B35","doi-asserted-by":"crossref","first-page":"1773","DOI":"10.1093\/bioinformatics\/btg239","article-title":"Haplotype inference by maximum parsimony","volume":"19","author":"Wang","year":"2003","journal-title":"Bioinformatics"},{"key":"2023013110033482300_B36","first-page":"308","article-title":"Haplotype inference by pure parsimony via genetic algorithm","volume-title":"Operations Research and Its Applications, The Fifth International Symposium, (ISORA'05)","author":"Wang","year":"2005"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/1\/68\/48983607\/bioinformatics_25_1_68.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/1\/68\/48983607\/bioinformatics_25_1_68.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T19:31:40Z","timestamp":1675193500000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/1\/68\/302176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11,4]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btn572","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,1,1]]},"published":{"date-parts":[[2008,11,4]]}}}