{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:26:22Z","timestamp":1725567982562},"publisher-location":"New York, NY","reference-count":45,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781441967992"},{"type":"electronic","value":"9781441968005"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-1-4419-6800-5_7","type":"book-chapter","created":{"date-parts":[[2010,10,14]],"date-time":"2010-10-14T14:29:12Z","timestamp":1287066552000},"page":"127-147","source":"Crossref","is-referenced-by-count":1,"title":["Haplotype Inference Using Propositional Satisfiability"],"prefix":"10.1007","author":[{"given":"Ana","family":"Gra\u00e7a","sequence":"first","affiliation":[]},{"given":"Jo\u00e3o","family":"Marques-Silva","sequence":"additional","affiliation":[]},{"given":"In\u00eas","family":"Lynce","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,9,21]]},"reference":[{"issue":"5","key":"7_CR1_7","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.camwa.2006.12.095","volume":"55","author":"P Bertolazzi","year":"2008","unstructured":"P. Bertolazzi, A. Godi, M. Labb\u00e9, and L. Tininini. Solving haplotyping inference parsimony problem using a new basic polynomial formulation. Computers & Mathematics with Applications, 55(5):900\u2013911, 2008","journal-title":"Computers & Mathematics with Applications"},{"key":"7_CR2_7","doi-asserted-by":"crossref","unstructured":"D. Brown and I. Harrower. A new integer programming formulation for the pure parsimony problem in haplotype analysis. In Workshop on Algorithms in Bioinformatics (WABI\u201904), volume 3240 of LNCS, pages 254\u2013265, 2004","DOI":"10.1007\/978-3-540-30219-3_22"},{"issue":"2","key":"7_CR3_7","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1109\/TCBB.2006.24","volume":"3","author":"D Brown","year":"2006","unstructured":"D. Brown and I. Harrower. Integer programming approaches to haplotype inference by pure parsimony. IEEE\/ACM Transactions on Computational Biology and Bioinformatics, 3(2):141\u2013154, 2006","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"issue":"5","key":"7_CR4_7","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1086\/521987","volume":"81","author":"S Browning","year":"2007","unstructured":"S. Browning and B. Browning. Rapid and accurate haplotype phasing and missing data inference for whole genome association studies using localized haplotype clustering. American Journal of Human Genetics, 81(5):1084\u20131097, 2007","journal-title":"American Journal of Human Genetics"},{"issue":"2","key":"7_CR5_7","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1287\/ijoc.1090.0333","volume":"22","author":"D Catanzaro","year":"2009","unstructured":"D. Catanzaro, A. Godi, and M. Labb\u00e9. A class representative model for pure parsimony haplotyping. INFORMS Journal on Computing, 22(2):195\u2013209, 2009","journal-title":"INFORMS Journal on Computing"},{"issue":"2","key":"7_CR6_7","first-page":"111","volume":"7","author":"AG Clark","year":"1990","unstructured":"A. G. Clark. Inference of haplotypes from PCR-amplified samples of diploid populations. Molecular Biology and Evolution, 7(2):111\u2013122, 1990","journal-title":"Molecular Biology and Evolution"},{"key":"7_CR7_7","doi-asserted-by":"crossref","unstructured":"S. A. Cook. The complexity of theorem-proving procedures. In ACM Symposium on Theory of Computing (STOC\u201971), pages 151\u2013158, 1971","DOI":"10.1145\/800157.805047"},{"key":"7_CR8_7","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1146\/annurev.med.56.082103.104540","volume":"56","author":"DC Crawford","year":"2005","unstructured":"D. C. Crawford and D. A. Nickerson. Definition and clinical importance of haplotypes. Annual Review of Medicine, 56:303\u2013320, 2005","journal-title":"Annual Review of Medicine"},{"key":"7_CR9_7","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1038\/ng1001-229","volume":"29","author":"MJ Daly","year":"2001","unstructured":"M. J. Daly, J. D. Rioux, S. F. Schaffner, T. J. Hudson, and E. S. Lander. High-resolution haplotype structure in the human genome. Nature Genetics, 29:229\u2013232, 2001","journal-title":"Nature Genetics"},{"key":"7_CR10_7","doi-asserted-by":"crossref","unstructured":"C. M. Drysdale, D. W. McGraw, C. B. Stack, J. C. Stephens, R. S. Judson, K. Nandabalan, K. Arnold, G. Ruano, and S. B. Liggett. Complex promoter and coding region \u03b22-adrenergic receptor haplotypes alter receptor expression and predict in vivo responsiveness. In National Academy of Sciences, volume 97, pages 10483\u201310488, 2000","DOI":"10.1073\/pnas.97.19.10483"},{"key":"7_CR11_7","doi-asserted-by":"crossref","unstructured":"N. E\u00e9n and N. S\u00f6rensson. An extensible SAT-solver. In International Conference on Theory and Applications of Satisfiability Testing (SAT\u201903), pages 502\u2013518, 2003","DOI":"10.1007\/978-3-540-24605-3_37"},{"key":"7_CR12_7","unstructured":"E. Erdem and F. Ture. Efficient haplotype inference with answer set programming. In National Conference on Artificial Intelligence (AAAI\u201908), pages 434\u2013441, 2008"},{"issue":"1\u20133","key":"7_CR13_7","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2008.02.004","volume":"63","author":"L Gaspero","year":"2008","unstructured":"L. Gaspero and A. Roli. Stochastic local search for large-scale instances of the haplotype inference problem by pure parsimony. Journal of Algorithms, 63(1\u20133):55\u201369, 2008","journal-title":"Journal of Algorithms"},{"issue":"4","key":"7_CR14_7","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10817-006-9033-2","volume":"36","author":"E Giunchiglia","year":"2006","unstructured":"E. Giunchiglia, Y. Lierler, and M. Maratea. Answer set programming based on propositional satisfiability. Journal of Automated Reasoning, 36(4):345\u2013377, 2006","journal-title":"Journal of Automated Reasoning"},{"issue":"12","key":"7_CR15_7","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1038\/nrg1229","volume":"4","author":"DB Goldstein","year":"2003","unstructured":"D. B. Goldstein, S. K. Tate, and S. M. Sisodiya. Pharmacogenetics goes genomic. Nature Reviews Genetics, 4(12):937\u2013947, 2003","journal-title":"Nature Reviews Genetics"},{"key":"7_CR16_7","doi-asserted-by":"crossref","unstructured":"A. Gra\u00e7a, J. Marques-Silva, I. Lynce, and A. Oliveira. Efficient haplotype inference with pseudo-Boolean optimization. In Algebraic Biology (AB\u201907), volume 4545 of LNCS, pages 125\u2013139, 2007","DOI":"10.1007\/978-3-540-73433-8_10"},{"key":"7_CR17_7","doi-asserted-by":"crossref","unstructured":"A. Gra\u00e7a, J. Marques-Silva, I. Lynce, and A. Oliveira. Haplotype inference with pseudo-Boolean optimization. Annals of Operations Research, doi:10.1007\/s10479-009-0675-4, 2010 (in Press) http:\/\/www.springerlink.com\/content\/f8p2583387721p5t\/","DOI":"10.1007\/s10479-009-0675-4"},{"key":"7_CR18_7","doi-asserted-by":"crossref","unstructured":"D. Gusfield. Haplotyping as perfect phylogeny: conceptual framework and efficient solutions. In International Conference on Research in Computational Molecular Biology (RECOMB\u201902), pages 166\u2013175, 2002","DOI":"10.1145\/565196.565218"},{"key":"7_CR19_7","doi-asserted-by":"crossref","unstructured":"D. Gusfield. Haplotype inference by pure parsimony. In Annual Symposium on Combinatorial Pattern Matching (CPM\u201903), pages 144\u2013155, 2003","DOI":"10.1007\/3-540-44888-8_11"},{"key":"7_CR20_7","doi-asserted-by":"crossref","unstructured":"B.V. Halld\u00f3rsson, V. Bafna, N. Edwards, R. Lippert, S. Yooseph, and S. Istrail. A survey of computational methods for determining haplotypes. In DIMACS\/RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotype Inference, volume 2983 of LNCS, pages 26\u201347, 2004","DOI":"10.1007\/978-3-540-24719-7_3"},{"issue":"10","key":"7_CR21_7","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1089\/cmb.2005.12.1261","volume":"12","author":"Y-T. Huang","year":"2005","unstructured":"Y-T. Huang, K-M. Chao, and T. Chen. An approximation algorithm for haplotype inference by maximum parsimony. Journal of Computational Biology, 12(10):1261\u20131274, 2005","journal-title":"Journal of Computational Biology"},{"key":"7_CR22_7","first-page":"1","volume":"7","author":"R Hudson","year":"1990","unstructured":"R. Hudson. Gene genealogies and the coalescent process. Oxford Survey of Evolutionary Biology, 7:1\u201344, 1990","journal-title":"Oxford Survey of Evolutionary Biology"},{"issue":"2","key":"7_CR23_7","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","volume":"18","author":"RR Hudson","year":"2002","unstructured":"R. R. Hudson. Generating samples under a Wright-Fisher neutral model of genetic variation. Bioinformatics, 18(2):337\u2013338, 2002","journal-title":"Bioinformatics"},{"key":"7_CR24_7","first-page":"233","volume":"29","author":"G Johnson","year":"2001","unstructured":"G. Johnson, L. Esposito, B. Barratt, A. Smith, J. Heward, G. Genova, H. Ueda, H. Cordell, I. Eaves, F. Dudbridge, R. Twells, F. Payne, W. Hughes, S. Nutland, H. Stevens, P. Carr, E. Tuomilehto-Wolf, J. Tuomilehto, S. Gough, D. Clayton, and J. Todd. Haplotype tagging for the identification of common disease genes. Nature, 29:233\u2013237, 2001","journal-title":"Nature"},{"key":"7_CR25_7","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1186\/1471-2105-5-188","volume":"5","author":"E Kelly","year":"2004","unstructured":"E. Kelly, F. Sievers, and R. McManus. Haplotype frequency estimation error analysis in the presence of missing genotype data. BMC Bioinformatics, 5:188, 2004","journal-title":"BMC Bioinformatics"},{"key":"7_CR26_7","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1097\/00008571-200308000-00006","volume":"13","author":"DL Kroetz","year":"2003","unstructured":"D. L. Kroetz, C. Pauli-Magnus, L. M. Hodges, C. C. Huang, M. Kawamoto, S. J. Johns, D. Stryke, T. E. Ferrin, J. DeYoung, T. Taylor, E. J. Carlson, I. Herskowitz, K. M. Giacomini, and A. G. Clark. Sequence diversity and haplotype structure in the human ABCD1 (MDR1, multidrug resistance transporter). Pharmacogenetics, 13:481\u2013494, 2003","journal-title":"Pharmacogenetics"},{"issue":"1","key":"7_CR27_7","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1287\/ijoc.1080.0285","volume":"21","author":"G Lancia","year":"2009","unstructured":"G. Lancia and P. Serafini. A set-covering approach with column generation for parsimony haplotyping. INFORMS Journal on Computing, 21(1):151\u2013166, 2009","journal-title":"INFORMS Journal on Computing"},{"issue":"4","key":"7_CR28_7","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1287\/ijoc.1040.0085","volume":"16","author":"G Lancia","year":"2004","unstructured":"G. Lancia, C. M. Pinotti, and R. Rizzi. Haplotyping populations by pure parsimony: complexity of exact and approximation algorithms. INFORMS Journal on Computing, 16(4):348\u2013359, 2004","journal-title":"INFORMS Journal on Computing"},{"key":"7_CR29_7","unstructured":"I. Lynce and J. Marques-Silva. Efficient haplotype inference with Boolean satisfiability. In National Conference on Artificial Intelligence (AAAI\u201906), pages 104\u2013109, 2006"},{"key":"7_CR30_7","doi-asserted-by":"crossref","unstructured":"I. Lynce and J. Marques-Silva. SAT in bioinformatics: Making the case with haplotype inference. In International Conference on Theory and Applications of Satisfiability Testing (SAT\u201906), volume 4121 of LNCS, pages 136\u2013141, 2006","DOI":"10.1007\/11814948_16"},{"issue":"2","key":"7_CR31_7","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1142\/S0218213008003935","volume":"17","author":"I Lynce","year":"2008","unstructured":"I. Lynce and J. Marques-Silva. Haplotype inference with Boolean satisfiability. International Journal on Artificial Intelligence Tools, 17(2):355\u2013387, 2008","journal-title":"International Journal on Artificial Intelligence Tools"},{"key":"7_CR32_7","doi-asserted-by":"crossref","unstructured":"I. Lynce, A. Gra\u00e7a, J. Marques-Silva, and A. Oliveira. Haplotype inference with Boolean constraint solving: an overview. In IEEE International Conference on Tools with Artificial Intelligence (ICTAI\u201908), volume I, pages 92\u2013100, 2008","DOI":"10.1109\/ICTAI.2008.135"},{"key":"7_CR33_7","doi-asserted-by":"crossref","unstructured":"J. Marques-Silva. Practical applications of Boolean satisfiability. In Workshop on Discrete Event Systems (WODES\u201908), 2008","DOI":"10.1109\/WODES.2008.4605925"},{"key":"7_CR34_7","doi-asserted-by":"crossref","unstructured":"J. Marques-Silva, I. Lynce, A. Gra\u00e7a, and A. Oliveira. Efficient and tight upper bounds for haplotype inference by pure parsimony using delayed haplotype selection. In 13th Portuguese Conference on Artificial Intelligence (EPIA\u201907), volume 4874 of LNAI, pages 621\u2013632. Springer, 2007","DOI":"10.1007\/978-3-540-77002-2_52"},{"issue":"1","key":"7_CR35_7","first-page":"3","volume":"1","author":"J McCluskey","year":"1999","unstructured":"J. McCluskey and C. A. Peh. The human leucocyte antigens and clinical medicine: an overview. Reviews in Immunogenetics, 1(1):3\u201320, 1999","journal-title":"Reviews in Immunogenetics"},{"key":"7_CR36_7","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1186\/1471-2164-9-356","volume":"9","author":"J Neigenfind","year":"2008","unstructured":"J. Neigenfind, G. Gyetvai, R. Basekow, S. Diehl, U. Achenbach, C. Gebhardt, J. Selbig, and B. Kersten. Haplotype inference from unphased SNP data in heterozygous polyploids based on SAT. BMC Genomics, 9:356, 2008","journal-title":"BMC Genomics"},{"key":"7_CR37_7","volume-title":"Haplotype inference by pure parsimony with constraint programming","author":"X Pan","year":"2009","unstructured":"X. Pan. Haplotype inference by pure parsimony with constraint programming. Master\u2019s thesis, Faculty of Science and Technology, Uppsala Universitet, Sweden, 2009"},{"key":"7_CR38_7","first-page":"481","volume":"22","author":"MJ Rieder","year":"2001","unstructured":"M. J. Rieder, S. T. Taylor, A. G. Clark, and D. A. Nickerson. Sequence variation in the human angiotensin converting enzyme. Nature Genetics, 22:481\u2013494, 2001","journal-title":"Nature Genetics"},{"key":"7_CR39_7","doi-asserted-by":"publisher","first-page":"1576","DOI":"10.1101\/gr.3709305","volume":"15","author":"SF Schaffner","year":"2005","unstructured":"S.F. Schaffner, C. Foo, S. Gabriel, D. Reich, M.J. Daly, and D. Altshuler. Calibrating a coalescent simulation of human genome sequence variation. Genome Research, 15:1576\u20131583, 2005","journal-title":"Genome Research"},{"key":"7_CR40_7","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1093\/nar\/29.1.308","volume":"29","author":"ST Sherry","year":"2001","unstructured":"S. T. Sherry, M. H. Ward, M. Kholodov, J. Baker, L. Phan, E. M. Smigielski, and K. Sirotkin. dbSNP: the NCBI database of genetic variation. Nucleic Acids Research, 29:308\u2013311, 2001","journal-title":"Nucleic Acids Research"},{"key":"7_CR41_7","doi-asserted-by":"publisher","first-page":"978","DOI":"10.1086\/319501","volume":"68","author":"M Stephens","year":"2001","unstructured":"M. Stephens, N. Smith, and P. Donelly. A new statistical method for haplotype reconstruction. American Journal of Human Genetics, 68:978\u2013989, 2001","journal-title":"American Journal of Human Genetics"},{"key":"7_CR42_7","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1038\/nature06258","volume":"449","author":"The International HapMap Consortium","year":"2007","unstructured":"The International HapMap Consortium. A second generation human haplotype map over 3.1 million snps. Nature, 449:851\u2013861, 2007","journal-title":"Nature"},{"key":"7_CR43_7","unstructured":"L. Tininini, P. Bertolazzi, A. Godi, and G. Lancia. CollHaps: A heuristic approach to haplotype inference by parsimony. IEEE\/ACM Transactions on Computational Biology and Bioinformatics, 99(1), 2008"},{"issue":"14","key":"7_CR44_7","doi-asserted-by":"publisher","first-page":"1773","DOI":"10.1093\/bioinformatics\/btg239","volume":"19","author":"L Wang","year":"2003","unstructured":"L. Wang and Y. Xu. Haplotype inference by maximum parsimony. Bioinformatics, 19(14):1773\u20131780, 2003","journal-title":"Bioinformatics"},{"key":"7_CR45_7","unstructured":"R.-S. Wang, X.-S. Zhang, and L. Sheng. Haplotype inference by pure parsimony via genetic algorithm. In International Symposium on Operations Research and Its Applications (ISORA\u201905), pages 308\u2013318, 2005"}],"container-title":["Mathematical Approaches to Polymer Sequence Analysis and Related Problems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4419-6800-5_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T00:37:57Z","timestamp":1605659877000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4419-6800-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,21]]},"ISBN":["9781441967992","9781441968005"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-1-4419-6800-5_7","relation":{},"subject":[],"published":{"date-parts":[[2010,9,21]]}}}