{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:23:14Z","timestamp":1773278594272,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2008,1,12]],"date-time":"2008-01-12T00:00:00Z","timestamp":1200096000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2008,6]]},"DOI":"10.1007\/s10601-007-9035-7","type":"journal-article","created":{"date-parts":[[2008,1,11]],"date-time":"2008-01-11T00:39:38Z","timestamp":1200011978000},"page":"155-179","source":"Crossref","is-referenced-by-count":11,"title":["Boosting Haplotype Inference with Local Search"],"prefix":"10.1007","volume":"13","author":[{"given":"In\u00eas","family":"Lynce","sequence":"first","affiliation":[]},{"given":"Jo\u00e3o","family":"Marques-Silva","sequence":"additional","affiliation":[]},{"given":"Steve","family":"Prestwich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,1,12]]},"reference":[{"key":"9035_CR1","doi-asserted-by":"crossref","unstructured":"Brown, D., & Harrower, I. (2004). A new integer programming formulation for the pure parsimony problem in haplotype analysis. In Workshop on algorithms in bioinformatics (WABI\u201904).","DOI":"10.1007\/978-3-540-30219-3_22"},{"issue":"2","key":"9035_CR2","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, 3(2), 141\u2013154 (April\u2013June).","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"9035_CR3","doi-asserted-by":"crossref","unstructured":"Brown, D., & Harrower, I. (2006). Toward an algebraic understanding of haplotype inference by pure parsimony. In Computational systems bioinformatics conference (August).","DOI":"10.1142\/9781860947575_0027"},{"key":"9035_CR4","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1038\/ng1001-229","volume":"29","author":"M. J. Daly","year":"2001","unstructured":"Daly, M. J., Rioux, J. D., Schaffner, S. F., Hudson, T. J., & Lander, E. S. (2001). High-resolution haplotype structure in the human genome. Nature Genetics, 29, 229\u2013232.","journal-title":"Nature Genetics"},{"issue":"1","key":"9035_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","volume":"39","author":"A. P. Dempster","year":"1977","unstructured":"Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 39(1), 1\u201338.","journal-title":"Journal of the Royal Statistical Society. Series B (Methodological)"},{"key":"9035_CR6","doi-asserted-by":"crossref","unstructured":"Ding, Z., Filkov, V., & Gusfield, D. (2005). A linear-time algorithm for the perfect phylogeny haplotyping (PPH) problem. In International conference on research in computational molecular biology (RECOMB) (pp. 585\u2013600) (May).","DOI":"10.1007\/11415770_44"},{"key":"9035_CR7","unstructured":"E\u00e9n, N., & S\u00f6rensson, N. (2003). An extensible SAT-solver. In International conference on theory and applications of satisfiability testing (SAT) (pp. 502\u2013518)."},{"key":"9035_CR8","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 Evolution, 12, 921\u2013927.","journal-title":"Molecular Biology Evolution"},{"key":"9035_CR9","doi-asserted-by":"crossref","unstructured":"Flener, P., Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., et al. (2002). Breaking row and column symmetries in matrix models. In International conference on principles and practice of constraint programming (CP).","DOI":"10.1007\/3-540-46135-3_31"},{"key":"9035_CR10","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. Freeman."},{"key":"9035_CR11","doi-asserted-by":"crossref","unstructured":"Gusfield, D. (2003). Haplotype inference by pure parsimony. In 14th annual symposium on combinatorial pattern matching (CPM\u201903) (pp. 144\u2013155).","DOI":"10.1007\/3-540-44888-8_11"},{"key":"9035_CR12","unstructured":"Gusfield, D., & Orzach, S. (2005). Handbook on computational molecular biology. Chapman and Hall\/CRC computer and information science series, Vol.\u00a09. Chapter haplotype inference. CRC Press (December)."},{"key":"9035_CR13","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, B., Bafna, V., Edwards, N., Lippert, R., Yooseph, S., & Istrail, S. (2004). A survey of computational methods for determining haplotypes. In Proceedings of the first RECOMB satellite on computational methods for SNPs and haplotype inference, LNBI (Vol. 2983, pp. 26\u201347).","DOI":"10.1007\/978-3-540-24719-7_3"},{"key":"9035_CR14","unstructured":"Halperin, E., & Karp, R. (2003). Perfect phylogeny and haplotype assignment. In Annual international conference on computational molecular biology (pp. 10\u201319) (March)."},{"key":"9035_CR15","unstructured":"Hoos, H. H., & St\u00fctzle, T. (2004). Stochastic local search: Foundations and applications. Morgan Kaufmann."},{"issue":"10","key":"9035_CR16","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1089\/cmb.2005.12.1261","volume":"12","author":"Y.-T. Huang","year":"2005","unstructured":"Huang, Y.-T., Chao, K.-M., & Chen, T. (2005). An approximation algorithm for haplotype inference by maximum parsimony. Journal of Computational Biology, 12(10), 1261\u20131274 (December).","journal-title":"Journal of Computational Biology"},{"key":"9035_CR17","doi-asserted-by":"crossref","unstructured":"Kalpakis, K., & Namjoshi, P. (2005). Haplotype phasing using semidefinite programming. In International symposium on bioinformatic and bioengineering (pp. 145\u2013152) (October).","DOI":"10.1109\/BIBE.2005.36"},{"issue":"4","key":"9035_CR18","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 of Computing, 16(4), 348\u2013359.","journal-title":"INFORMS Journal of Computing"},{"key":"9035_CR19","unstructured":"Lynce, I., & Marques-Silva, J. (2006). Efficient haplotype inference with Boolean satisfiability. In National conference on artificial intelligence (AAAI) (July)."},{"key":"9035_CR20","doi-asserted-by":"crossref","unstructured":"Lynce, I., & Marques-Silva, J. (2006). SAT in bioinformatics: Making the case with haplotype inference. In International conference on theory and applications of satisfiability testing (SAT) (August).","DOI":"10.1007\/11814948_16"},{"key":"9035_CR21","doi-asserted-by":"crossref","unstructured":"Lynce, I., & Marques-Silva, J. (2007). Breaking symmetries in SAT matrix models. In International conference on theory and applications of satisfiability testing (SAT) (May).","DOI":"10.1007\/978-3-540-72788-0_6"},{"key":"9035_CR22","unstructured":"Lynce, I., Marques-Silva, J., & Oliveira, A. L. (2006). Improved lower bounds for SAT-based haplotype inference. Technical report\u00a017, INESC-ID (June)."},{"key":"9035_CR23","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., et al. (2006). A comparison of phasing algorithms for trios and unrelated individuals. Journal of Human Genetics, 78, 437\u2013450.","journal-title":"Journal of Human Genetics"},{"key":"9035_CR24","unstructured":"McAllester, D., Selman, B., & Kautz, H. (1997). Evidence for invariants in local search. In National conference on artificial intelligence (AAAI) (pp. 321\u2013326)."},{"key":"9035_CR25","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1086\/338446","volume":"70","author":"T. Niu","year":"2002","unstructured":"Niu, T., Qin, Z., Xu, X., & Liu, J. (2002). Bayesian haplotype inference for multiple linked single-nucleotide polymorphisms. American Journal of Human Genetics, 70, 157\u2013169.","journal-title":"American Journal of Human Genetics"},{"key":"9035_CR26","doi-asserted-by":"crossref","first-page":"1719","DOI":"10.1126\/science.1065573","volume":"294","author":"N. Patil","year":"2001","unstructured":"Patil, N., Berno, A. J., Hinds, D. A., Barrett, W. A., Doshi, J. M., Hacker, C. R., et al. (2001). Blocks of limited haplotype diversity revealed by high-resolution scanning of human chromosome 21. Science, 294, 1719\u20131723.","journal-title":"Science"},{"key":"9035_CR27","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1023\/A:1021809724362","volume":"118","author":"S. Prestwich","year":"2003","unstructured":"Prestwich, S. (2003). Negative effects of modeling techniques on search performance. Annals of Operation Research, 118, 137\u2013150.","journal-title":"Annals of Operation Research"},{"key":"9035_CR28","doi-asserted-by":"crossref","unstructured":"Prestwich, S. (2005). Random walk with continuously smoothed variable weights. In International conference on theory and applications of satisfiability testing (SAT) (pp. 203\u2013215).","DOI":"10.1007\/11499107_15"},{"key":"9035_CR29","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":"9035_CR30","unstructured":"Selman, B., Kautz, H., & Cohen, B. (1994). Noise strategies for improving local search. In National conference on artificial intelligence (AAAI) (pp. 337\u2013343)."},{"key":"9035_CR31","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":"9035_CR32","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1038\/nature02168","volume":"426","author":"The International HapMap Consortium","year":"2003","unstructured":"The\u00a0International\u00a0HapMap\u00a0Consortium (2003). The international hapmap project. Nature, 426, 789\u2013796.","journal-title":"Nature"},{"key":"9035_CR33","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1038\/nature04226","volume":"437","author":"The International HapMap Consortium","year":"2005","unstructured":"The\u00a0International\u00a0HapMap\u00a0Consortium (2005). A haplotype map of the human genome. Nature, 437, 1299\u20131320 (27 October).","journal-title":"Nature"},{"issue":"14","key":"9035_CR34","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"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-007-9035-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-007-9035-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-007-9035-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T15:14:14Z","timestamp":1559229254000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-007-9035-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,12]]},"references-count":34,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["9035"],"URL":"https:\/\/doi.org\/10.1007\/s10601-007-9035-7","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,12]]}}}