{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:57:57Z","timestamp":1725537477308},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_31","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"337-348","source":"Crossref","is-referenced-by-count":2,"title":["Complete Parsimony Haplotype Inference Problem and Algorithms"],"prefix":"10.1007","author":[{"given":"Gerold","family":"J\u00e4ger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharlee","family":"Climer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weixiong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1002\/gepi.20185","volume":"31","author":"A.M. Andr\u00e9s","year":"2007","unstructured":"Andr\u00e9s, A.M., Clark, A.G., Boerwinkle, E., Sing, C.F., Hixson, J.E.: Assessing the accuracy of statistical haplotype inference with sequence data of known phase. Genet. Epi.\u00a031, 659\u2013671 (2007)","journal-title":"Genet. Epi."},{"issue":"5","key":"31_CR2","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.camwa.2006.12.095","volume":"55","author":"P. Bertolazzi","year":"2008","unstructured":"Bertolazzi, P., Godi, A., Labb\u00e9, M., Tininini, L.: Solving haplotyping inference parsimony problem using a new basic polynomial formulation. Comput. Math. Appl.\u00a055(5), 900\u2013911 (2008)","journal-title":"Comput. Math. Appl."},{"issue":"2","key":"31_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1109\/TCBB.2006.24","volume":"3","author":"D.G. Brown","year":"2006","unstructured":"Brown, D.G., Harrower, I.M.: Integer Programming Approaches to Haplotype Inference by Pure Parsimony. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a03(2), 141\u2013154 (2006)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"31_CR4","first-page":"111","volume":"7","author":"A.G. Clark","year":"1990","unstructured":"Clark, A.G.: Inference of Haplotypes from PCR-Amplified Samples of Diploid Populations. Molecular Biology and Evolution\u00a07, 111\u2013122 (1990)","journal-title":"Molecular Biology and Evolution"},{"issue":"1","key":"31_CR5","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1093\/bioinformatics\/btn572","volume":"25","author":"S. Climer","year":"2009","unstructured":"Climer, S., J\u00e4ger, G., Templeton, A.R., Zhang, W.: How Frugal is Mother Nature with Haplotypes? Bioinformatics\u00a025(1), 68\u201374 (2009)","journal-title":"Bioinformatics"},{"key":"31_CR6","unstructured":"Climer, S., Zhang, W.: Searching for Backbones and Fat: A Limit-Crossing Approach with Applications. In: Proc. 18th National Conference on Artificial Intelligence (AAAI), pp. 707\u2013712 (2002)"},{"key":"31_CR7","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"1","key":"31_CR8","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News\u00a038(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"issue":"3","key":"31_CR9","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1089\/10665270152530863","volume":"8","author":"D. Gusfield","year":"2001","unstructured":"Gusfield, D.: Inference of Haplotypes from Samples of Diploid Populations: Complexity and Algorithms. J. Computational Biology\u00a08(3), 305\u2013313 (2001)","journal-title":"J. Computational Biology"},{"key":"31_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/3-540-44888-8_11","volume-title":"Combinatorial Pattern Matching","author":"D. Gusfield","year":"2003","unstructured":"Gusfield, D.: Haplotype Inference by Pure Parsimony. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 144\u2013155. Springer, Heidelberg (2003)"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Gusfield, D., Orzack, S.H.: Haplotype Inference. In: Handbook on Bioinformatics (2005)","DOI":"10.1201\/9781420036275.ch18"},{"key":"31_CR12","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-540-24719-7_3","volume-title":"Computational Methods for SNPs and Haplotype Inference","author":"B.V. Halld\u00f3rsson","year":"2004","unstructured":"Halld\u00f3rsson, B.V., Bafna, V., Edwards, N., Lippert, R., Yooseph, S., Istrail, S.: A survey of computational methods for determining haplotypes. In: Istrail, S., Waterman, M.S., Clark, A. (eds.) DIMACS\/RECOMB Satellite Workshop 2002. LNCS (LNBI), vol.\u00a02983, pp. 26\u201347. Springer, Heidelberg (2004)"},{"issue":"4","key":"31_CR13","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1287\/ijoc.1040.0085","volume":"16","author":"G. Lancia","year":"2004","unstructured":"Lancia, G., Pinotti, C.M., Rizzi, R.: Haplotype Populations by Pure Parsimony: Complexity of Exact and Approximation Algorithms. INFORMS J. Computing\u00a016(4), 348\u2013359 (2004)","journal-title":"INFORMS J. Computing"},{"key":"31_CR14","unstructured":"Lynce, I., Marques-Silva, J.: Efficient Haplotype Inference with Boolean Satisfiability. In: Proc. 21st National Conference on Artificial Intelligence (AAAI), pp. 104\u2013109 (2006)"},{"key":"31_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/11814948_16","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"I. Lynce","year":"2006","unstructured":"Lynce, I., Marques-Silva, J.: SAT in Bioinformatics: Making the Case with Haplotype Inference. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 136\u2013141. Springer, Heidelberg (2006)"},{"issue":"1-2","key":"31_CR16","doi-asserted-by":"publisher","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.: Boosting Haplotype Inference with Local Search. Constraints\u00a013(1-2), 155\u2013179 (2008)","journal-title":"Constraints"},{"key":"31_CR17","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Tractability","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Tractability. Oxford University Press, Oxford (2006)"},{"key":"31_CR18","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1093\/genetics\/165.2.915","volume":"165","author":"S.H. Orzack","year":"2003","unstructured":"Orzack, S.H., Gusfield, D., Olson, J., Nesbitt, S., Subrahmanyan, L., Stanton Jr., V.P.: Analysis and Exploration of the Use of Rule-Based Algorithms and Consensus Methods for the Inferral of Haplotypes. Genetics\u00a0165, 915\u2013928 (2003)","journal-title":"Genetics"},{"key":"31_CR19","unstructured":"Slaney, J., Walsh, T.: Backbones in Optimization and Approximation. In: Proc. 17th Intern. Joint Conf. on Artificial Intelligence (IJCAI 2001), pp. 254\u2013259 (2001)"},{"issue":"14","key":"31_CR20","doi-asserted-by":"publisher","first-page":"1773","DOI":"10.1093\/bioinformatics\/btg239","volume":"19","author":"L. Wang","year":"2003","unstructured":"Wang, L., Xu, Y.: Haplotype Inference by Maximum Parsimony. Bioinformatics\u00a019(14), 1773\u20131780 (2003)","journal-title":"Bioinformatics"},{"key":"31_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/3-540-45578-7_11","volume-title":"Principles and Practice of Constraint Programming - CP 2001","author":"W. Zhang","year":"2001","unstructured":"Zhang, W.: Phase transitions and backbones of 3-SAT and maximum 3-SAT. In: Walsh, T. (ed.) CP 2001. LNCS, vol.\u00a02239, pp. 153\u2013167. Springer, Heidelberg (2001)"},{"issue":"1","key":"31_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2004.04.001","volume":"158","author":"W. Zhang","year":"2004","unstructured":"Zhang, W.: Configuration Landscape Analysis and Backbone Guided Local Search: Part I: Satisfiability and Maximum Satisfiability. Artificial Intelligence\u00a0158(1), 1\u201326 (2004)","journal-title":"Artificial Intelligence"},{"key":"31_CR23","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1613\/jair.1389","volume":"20","author":"W. Zhang","year":"2004","unstructured":"Zhang, W.: Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem. J. Artificial Intelligence Research\u00a020, 471\u2013497 (2004)","journal-title":"J. Artificial Intelligence Research"},{"key":"31_CR24","unstructured":"Zhang, W., Looks, M.: A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits Backbones. In: Proc. 19th International Joint Conference on Artificial Intelligence (IJCAI), pp. 343\u2013350 (2005)"},{"key":"31_CR25","unstructured":"Homepage of Cplex, http:\/\/www.ilog.com\/products\/optimization\/archive.cfm"},{"key":"31_CR26","doi-asserted-by":"crossref","unstructured":"The International HapMap Consortium: A Haplotype Map of the Human Genome. Nature\u00a0437, 1299\u20131320 (2005)","DOI":"10.1038\/nature04226"},{"key":"31_CR27","unstructured":"Supporting Information to this paper, http:\/\/www.cse.wustl.edu\/~zhang\/publications\/supplemental\/ChippSup.pdf"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T18:06:57Z","timestamp":1633889217000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}