{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T02:55:07Z","timestamp":1723172107390},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,12,9]],"date-time":"2009-12-09T00:00:00Z","timestamp":1260316800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2011,4]]},"DOI":"10.1007\/s10479-009-0675-4","type":"journal-article","created":{"date-parts":[[2009,12,8]],"date-time":"2009-12-08T20:23:37Z","timestamp":1260303817000},"page":"137-162","source":"Crossref","is-referenced-by-count":12,"title":["Haplotype inference with pseudo-Boolean optimization"],"prefix":"10.1007","volume":"184","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":[]},{"given":"Arlindo L.","family":"Oliveira","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,12,9]]},"reference":[{"key":"675_CR1","doi-asserted-by":"crossref","unstructured":"Aloul, F., Ramadi, A., Markov, I., & Sakallah, K. (2002). Generic ILP versus specialized 0-1 ILP: an update. In IEEE\/ACM international conference on computer-aided design (ICCAD\u201902) (pp. 450\u2013457).","DOI":"10.1145\/774572.774638"},{"key":"675_CR2","unstructured":"Brown, D., & Harrower, I. (2004). A new integer programming formulation for the pure parsimony problem in haplotype analysis. In LNCS: Vol. 3240. Workshop on algorithms in bioinformatics (WABI\u201904) (pp.\u00a0254\u2013265)."},{"issue":"2","key":"675_CR3","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1109\/TCBB.2006.24","volume":"3","author":"D. Brown","year":"2006","unstructured":"Brown, D., & Harrower, I. (2006). Integer programming approaches to haplotype inference by pure parsimony. IEEE\/ACM Transactions on Computational Biology and Bioinformatics (TCBB\u201906), 3(2), 141\u2013154.","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics (TCBB\u201906)"},{"issue":"5","key":"675_CR4","doi-asserted-by":"crossref","first-page":"1084","DOI":"10.1086\/521987","volume":"81","author":"S. Browning","year":"2007","unstructured":"Browning, S., & Browning, B. (2007). Rapid and accurate haplotype phasing and missing data inference for whole genome association studies using localized haplotype clustering. American Journal of Human Genetics (AJHG), 81(5), 1084\u20131097.","journal-title":"American Journal of Human Genetics (AJHG)"},{"issue":"12","key":"675_CR5","doi-asserted-by":"crossref","first-page":"2717","DOI":"10.1101\/gr.1442303","volume":"13","author":"C. Burgtorf","year":"2003","unstructured":"Burgtorf, C., Kepper, P., Hoehe, M., Schmitt, C., Reinhardt, R., Lehrach, H., & Sauer, S. (2003). Clone-based systematic haplotyping (CSH): a procedure for physical haplotyping of whole genomes. Genome Research, 13(12), 2717\u20132724.","journal-title":"Genome Research"},{"key":"675_CR6","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1038\/ng1001-229","volume":"29","author":"M. Daly","year":"2001","unstructured":"Daly, M., Rioux, J., Schaffner, S., Hudson, T., & Lander, E. (2001). High-resolution haplotype structure in the human genome. Nature Genetics, 29, 229\u2013232.","journal-title":"Nature Genetics"},{"key":"675_CR7","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1186\/1471-2105-9-540","volume":"9","author":"O. Delaneau","year":"2008","unstructured":"Delaneau, O., Coulonges, C., & Zagury, J. F. (2008). Shape-IT: new rapid an accurate algorithm for haplotype inference. BMC Bioinformatics, 9, 540.","journal-title":"BMC Bioinformatics"},{"key":"675_CR8","doi-asserted-by":"crossref","unstructured":"Drysdale, C., McGraw, D., Stack, C., Stephens, J., Judson, R., Nandabalan, K., Arnold, K., Ruano, G., & Liggett, S. (2000). Complex promoter and coding region \u03b2 2-adrenergic receptor haplotypes alter receptor expression and predict in vivo responsiveness. In National academy of sciences (NAS) (Vol. 97, pp.\u00a010.483\u201310.488).","DOI":"10.1073\/pnas.97.19.10483"},{"key":"675_CR9","unstructured":"E\u00e9n, N., & S\u00f6rensson, N. (2003). An extensible SAT-solver. In LNCS: vol. 2919, International conference on theory and applications of satisfiability testing (SAT\u201903) (pp. 502\u2013518)."},{"key":"675_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/SAT190014","volume":"2","author":"N. E\u00e9n","year":"2006","unstructured":"E\u00e9n, N., & S\u00f6rensson, N. (2006). Translating pseudo-Boolean constraints into SAT. Journal on Satisfiability, Boolean Modeling and Computation, 2, 1\u201326.","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"675_CR11","unstructured":"Erdem, E., & T\u00fcre, F. (2008). Efficient haplotype inference with answer set programming. In National conference on artificial intelligence (AAAI\u201908) (pp. 436\u2013441)."},{"issue":"5","key":"675_CR12","first-page":"921","volume":"12","author":"L. Excoffier","year":"1995","unstructured":"Excoffier, L., & Slatkin, M. (1995). Maximum likelihood estimation of molecular haplotype frequencies in a diploid population. Molecular Biology and Evolution, 12(5), 921\u2013927.","journal-title":"Molecular Biology and Evolution"},{"issue":"1\u20133","key":"675_CR13","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.jalgor.2008.02.004","volume":"63","author":"L. Gaspero","year":"2008","unstructured":"Gaspero, L., & Roli, A. (2008). Stochastic local search for large-scale instances of the haplotype inference problem by pure parsimony. Journal of Algorithms: Algorithms in Logic, Informatics and Cognition, 63(1\u20133), 55\u201369.","journal-title":"Journal of Algorithms: Algorithms in Logic, Informatics and Cognition"},{"key":"675_CR14","unstructured":"Gra\u00e7a, A., Marques-Silva, J., Lynce, I., & Oliveira, A. (2007). Efficient haplotype inference with pseudo-Boolean optimization. In LNCS: Vol. 4545, Algebraic biology (AB\u201907) (pp. 125\u2013139)."},{"key":"675_CR15","unstructured":"Gra\u00e7a, A., Lynce, I., Marques-Silva, J., & Oliveira, A. (2008a). Generic ILP vs specialized 0-1 ILP for haplotype inference. In Workshop on constraint based methods for bioinformatics (WCB\u201908)."},{"key":"675_CR16","doi-asserted-by":"crossref","unstructured":"Gra\u00e7a, A., Marques-Silva, J., Lynce, I., & Oliveira, A. (2008b). Efficient haplotype inference with combined CP and OR techniques. In LNCS: Vol. 5015, International conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CPAIOR\u201908) (pp. 308\u2013312).","DOI":"10.1007\/978-3-540-68155-7_28"},{"key":"675_CR17","doi-asserted-by":"crossref","unstructured":"Gusfield, D. (2003). Haplotype inference by pure parsimony. In Annual symposium on combinatorial pattern matching (CPM\u201903) (pp. 144\u2013155).","DOI":"10.1007\/3-540-44888-8_11"},{"key":"675_CR18","unstructured":"Halld\u00f3rsson, B., Bafna, V., Edwards, N., Lippert, R., Yooseph, S., & Istrail, S. (2004). A survey of computational methods for determining haplotypes. In LNCS: Vol. 2983, DIMACS\/RECOMB satellite workshop on computational methods for SNPs and haplotype inference (pp. 26\u201347)."},{"issue":"12","key":"675_CR19","doi-asserted-by":"crossref","first-page":"1842","DOI":"10.1093\/bioinformatics\/bth149","volume":"20","author":"E. Halperin","year":"2004","unstructured":"Halperin, E., & Eskin, E. (2004). Haplotype reconstruction from genotype data using imperfect phylogeny. Bioinformatics, 20(12), 1842\u20131849.","journal-title":"Bioinformatics"},{"key":"675_CR20","doi-asserted-by":"crossref","unstructured":"Halperin, E., & Karp, R. (2004). Perfect phylogeny and haplotype assignment. In Annual international conference on computational molecular biology (RECOMB\u201903) (pp. 10\u201319).","DOI":"10.1145\/974614.974617"},{"issue":"10","key":"675_CR21","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1089\/cmb.2005.12.1261","volume":"12","author":"Y. Huang","year":"2005","unstructured":"Huang, Y., Chao, K., & Chen, T. (2005). An approximation algorithm for haplotype inference by maximum parsimony. Journal of Computational Biology, 12(10), 1261\u20131274.","journal-title":"Journal of Computational Biology"},{"key":"675_CR22","first-page":"1","volume":"7","author":"R. Hudson","year":"1990","unstructured":"Hudson, R. (1990). Gene genealogies and the coalescent process. Oxford Survey of Evolutionary Biology, 7, 1\u201344.","journal-title":"Oxford Survey of Evolutionary Biology"},{"issue":"2","key":"675_CR23","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1093\/bioinformatics\/18.2.337","volume":"18","author":"R. Hudson","year":"2002","unstructured":"Hudson, R. (2002). Generating samples under a Wright-Fisher neutral model of genetic variation. Bioinformatics, 18(2), 337\u2013338.","journal-title":"Bioinformatics"},{"key":"675_CR24","first-page":"233","volume":"29","author":"G. Johnson","year":"2001","unstructured":"Johnson, G., Esposito, L., Barratt, B., Smith, A., Heward, J., Genova, G., Ueda, H., Cordell, H., Eaves, I., Dudbridge, F., Twells, R., Payne, F., Hughes, W., Nutland, S., Stevens, H., Carr, P., Tuomilehto-Wolf, E., Tuomilehto, J., Gough, S., Clayton, D., & Todd, J. (2001). Haplotype tagging for the identification of common disease genes. Nature, 29, 233\u2013237.","journal-title":"Nature"},{"key":"675_CR25","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1186\/1471-2105-5-188","volume":"5","author":"E. Kelly","year":"2004","unstructured":"Kelly, E., Sievers, F., & McManus, R. (2004). Haplotype frequency estimation error analysis in the presence of missing genotype data. BMC Bioinformatics, 5, 188.","journal-title":"BMC Bioinformatics"},{"key":"675_CR26","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1126\/science.2570460","volume":"245","author":"B. Kerem","year":"1989","unstructured":"Kerem, B., Rommens, J., Buchanan, J., Markiewicz, D., Cox, T., Chakravarti, A., Buchwald, M., & Tsui,\u00a0L.\u00a0C. (1989). Identification of the cystic fibrosis gene: Genetic analysis. Science, 245, 1073\u20131080.","journal-title":"Science"},{"key":"675_CR27","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1097\/00008571-200308000-00006","volume":"13","author":"D. L. Kroetz","year":"2003","unstructured":"Kroetz, D. L., Pauli-Magnus, C., Hodges, L. M., Huang, C. C., Kawamoto, M., Johns, S. J., Stryke, D., Ferrin, T. E., DeYoung, J., Taylor, T., Carlson, E. J., Herskowitz, I., Giacomini, K. M., & Clark, A. G. (2003). Sequence diversity and haplotype structure in the human ABCD1 (MDR1, multidrug resistance transporter). Pharmacogenetics, 13, 481\u2013494.","journal-title":"Pharmacogenetics"},{"issue":"4","key":"675_CR28","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1287\/ijoc.1040.0085","volume":"16","author":"G. Lancia","year":"2004","unstructured":"Lancia, G., Pinotti, C. M., & Rizzi, R. (2004). Haplotyping populations by pure parsimony: complexity of exact and approximation algorithms. INFORMS Journal on Computing, 16(4), 348\u2013359.","journal-title":"INFORMS Journal on Computing"},{"key":"675_CR29","unstructured":"Lynce, I., & Marques-Silva, J. (2006a). Efficient haplotype inference with Boolean satisfiability. In National conference on artificial intelligence (AAAI\u201906) (pp. 104\u2013109)."},{"key":"675_CR30","doi-asserted-by":"crossref","unstructured":"Lynce, I., & Marques-Silva, J. (2006b). SAT in bioinformatics: making the case with haplotype inference. In LNCS: Vol. 4121, International conference on theory and applications of satisfiability testing (SAT\u201906) (pp. 136\u2013141).","DOI":"10.1007\/11814948_16"},{"issue":"2","key":"675_CR31","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1142\/S0218213008003935","volume":"17","author":"I. Lynce","year":"2008","unstructured":"Lynce, I., & Marques-Silva, J. (2008). Haplotype inference with Boolean satisfiability. International Journal on Artificial Intelligence Tools, 17(2), 355\u2013387.","journal-title":"International Journal on Artificial Intelligence Tools"},{"issue":"1","key":"675_CR32","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10601-007-9035-7","volume":"13","author":"I. Lynce","year":"2008","unstructured":"Lynce, I., Marques-Silva, J., & Prestwich, S. (2008). Boosting haplotype inference with local search. Constraints, 13(1), 155\u2013179.","journal-title":"Constraints"},{"key":"675_CR33","doi-asserted-by":"crossref","unstructured":"Manquinho, V., & Marques-Silva, J. (2005). Effective lower bounding techniques for pseudo-Boolean optimization. In Design, automation and test in Europe conference and exhibition (DATE\u201905) (pp. 660\u2013665).","DOI":"10.1109\/DATE.2005.126"},{"key":"675_CR34","unstructured":"Manquinho, V., Marques-Silva, J., & Planes, J. (2009). Algorithms for weighted Boolean optimization. In LNCS: Vol. 5584, International conference on theory and applications of satisfiability testing (SAT\u201909) (pp. 495\u2013508)."},{"key":"675_CR35","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1086\/500808","volume":"78","author":"J. Marchini","year":"2006","unstructured":"Marchini, J., Cutler, D., Patterson, N., Stephens, M., Eskin, E., Halperin, E., Lin, S., Qin, Z., Munro, H., Abecassis, G., Donnelly, P., & Consortium, I. H. (2006). A comparison of phasing algorithms for trios and unrelated individuals. American Journal of Human Genetics, 78, 437\u2013450.","journal-title":"American Journal of Human Genetics"},{"key":"675_CR36","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1186\/1471-2164-9-356","volume":"9","author":"J. Neigenfind","year":"2008","unstructured":"Neigenfind, J., Gyetvai, G., Basekow, R., Diehl, S., Achenbach, U., Gebhardt, C., Selbig, J., & Kersten, B. (2008). Haplotype inference from unphased SNP data in heterozygous polyploids based on SAT. BMC Genomics, 9, 356.","journal-title":"BMC Genomics"},{"key":"675_CR37","doi-asserted-by":"crossref","first-page":"1719","DOI":"10.1126\/science.1065573","volume":"294","author":"N. Patil","year":"2001","unstructured":"Patil, N., Berno, A., Hinds, D., Barrett, W., Doshi, J., Hacker, C., Kautzer, C., Lee, D., Marjoribanks, C., McDonough, D., Nguyen, B., Norris, M., Sheehan, J., Shen, N., Stern, D., Stokowski, R., Thomas, D., Trulson, M., Vyas, K., Frazer, K., Fodor, S., & Cox, D. (2001). Blocks of limited haplotype diversity revealed by high-resolution scanning of human chromosome 21. Science, 294, 1719\u20131723.","journal-title":"Science"},{"key":"675_CR38","first-page":"481","volume":"22","author":"M. J. Rieder","year":"2001","unstructured":"Rieder, M. J., Taylor, S. T., Clark, A. G., & Nickerson, D. A. (2001). Sequence variation in the human angiotensin converting enzyme. Nature Genetics, 22, 481\u2013494.","journal-title":"Nature Genetics"},{"key":"675_CR39","doi-asserted-by":"crossref","first-page":"1576","DOI":"10.1101\/gr.3709305","volume":"15","author":"S. Schaffner","year":"2005","unstructured":"Schaffner, S., Foo, C., Gabriel, S., Reich, D., Daly, M., & Altshuler, D. (2005). Calibrating a coalescent simulation of human genome sequence variation. Genome Research, 15, 1576\u20131583.","journal-title":"Genome Research"},{"key":"675_CR40","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1086\/502802","volume":"78","author":"P. Scheet","year":"2006","unstructured":"Scheet, P., & Stephens, M. (2006). A fast and flexible statistical model for large-scale population genotype data: applications to inferring missing genotypes and haplotypic phase. American Journal of Human Genetics, 78, 629\u2013644.","journal-title":"American Journal of Human Genetics"},{"key":"675_CR41","doi-asserted-by":"crossref","first-page":"165","DOI":"10.3233\/SAT190020","volume":"2","author":"H. M. Sheini","year":"2006","unstructured":"Sheini, H. M., & Sakallah, K. A. (2006). Pueblo: A hybrid pseudo-Boolean SAT solver. Journal on Satisfiability, Boolean Modeling and Computation, 2, 165\u2013189.","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"675_CR42","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1086\/319501","volume":"68","author":"M. Stephens","year":"2001","unstructured":"Stephens, M., Smith, N., & Donelly, P. (2001). A new statistical method for haplotype reconstruction. American Journal of Human Genetics, 68, 978\u2013989.","journal-title":"American Journal of Human Genetics"},{"key":"675_CR43","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1038\/nature02168","volume":"426","author":"The International HapMap Consortium","year":"2003","unstructured":"The International HapMap Consortium (2003). The international hapmap project. Nature, 426, 789\u2013796.","journal-title":"Nature"},{"key":"675_CR44","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1038\/nature04226","volume":"437","author":"The International HapMap Consortium","year":"2005","unstructured":"The International HapMap Consortium (2005). A haplotype map of the human genome. Nature, 437, 1299\u20131320.","journal-title":"Nature"},{"key":"675_CR45","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 (2007). A second generation human haplotype map over 3.1 million SNPs. Nature, 449, 851\u2013861.","journal-title":"Nature"},{"issue":"14","key":"675_CR46","doi-asserted-by":"crossref","first-page":"1773","DOI":"10.1093\/bioinformatics\/btg239","volume":"19","author":"L. Wang","year":"2003","unstructured":"Wang, L., & Xu, Y. (2003). Haplotype inference by maximum parsimony. Bioinformatics, 19(14), 1773\u20131780.","journal-title":"Bioinformatics"},{"key":"675_CR47","unstructured":"Wang, R. S., Zhang, X. S., & Sheng, L. (2005). Haplotype inference by pure parsimony via genetic algorithm. In LNOR: Vol. 5, Operations research and its applications: the fifth international symposium (ISORA\u201905) (pp. 296\u2013306)."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-009-0675-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-009-0675-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-009-0675-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,24]],"date-time":"2020-05-24T04:32:50Z","timestamp":1590294770000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-009-0675-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,9]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["675"],"URL":"https:\/\/doi.org\/10.1007\/s10479-009-0675-4","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12,9]]}}}