{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T19:02:04Z","timestamp":1794337324834,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540309352","type":"print"},{"value":"9783540324263","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11602613_38","type":"book-chapter","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T03:24:24Z","timestamp":1133493864000},"page":"370-379","source":"Crossref","is-referenced-by-count":3,"title":["Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem"],"prefix":"10.1007","author":[{"given":"Lan","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xi","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"Li, J., Jiang, T.: Efficient rule-based haplotyping algorithm for pedigree data. In: Proc. of the 7th Annual Conference on Research in Computational Molecular Biology (RECOMB 2003), pp. 197\u2013206 (2003)","DOI":"10.1145\/640075.640101"},{"key":"38_CR2","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-540-39763-2_25","volume-title":"Algorithms in Bioinformatics","author":"K. Doi","year":"2003","unstructured":"Doi, K., Li, J., Jiang, T.: Minimum recombinant haplotype configuration on tree pedigrees. In: Benson, G., Page, R.D.M. (eds.) WABI 2003. LNCS (LNBI), vol.\u00a02812, pp. 339\u2013353. Springer, Heidelberg (2003)"},{"issue":"1","key":"38_CR3","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/BF02944784","volume":"19","author":"L. Aceto","year":"2004","unstructured":"Aceto, L., et al.: The complexity of checking consistency of pedigree information and related problems. J. Comp. Sci. Tech.\u00a019(1), 42\u201359 (2004)","journal-title":"J. Comp. Sci. Tech."},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of 2-Prover 1-Round Games. In: Proc. of the 34th ACM Symposium on Theory of Computing (STOC 2002), pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"Agarwal, A., Charikar, M.: O( $\\sqrt{log(n)}$ ) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. In: Proc. STOC 2005, pp. 573\u2013581 (2005)","DOI":"10.1145\/1060590.1060675"},{"key":"38_CR6","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation: combinatorial optimization problems and their approximability properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., et al.: Complexity and approximation: combinatorial optimization problems and their approximability properties, pp. 276\u2013279. Springer, Heidelberg (1999)"},{"key":"38_CR7","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1126\/science.1110903","volume":"308","author":"L. Jorde","year":"2005","unstructured":"Jorde, L.: Where we are hot, they are not. Science\u00a0308, 60\u201362 (2005)","journal-title":"Science"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"Li, L., Kim, J.H., Waterman, M.S.: Haplotype reconstruction from SNP alignment. In: Proc. RECOMB 2003, pp. 207\u2013216 (2003)","DOI":"10.1145\/640075.640102"},{"issue":"1","key":"38_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1093\/bib\/3.1.23","volume":"3","author":"R. Lippert","year":"2002","unstructured":"Lippert, R., et al.: Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem. Briefings in Bioinformatics\u00a03(1), 23\u201331 (2002)","journal-title":"Briefings in Bioinformatics"},{"key":"38_CR10","doi-asserted-by":"crossref","unstructured":"Eskin, E., Halperin, E., Karp, R.M.: Large scale reconstruction of haplotypes from genotype data. In: Proc. RECOMB 2003, pp. 104\u2013113 (2003)","DOI":"10.1145\/640075.640088"},{"key":"38_CR11","first-page":"921","volume":"12","author":"L. Excoffier","year":"1995","unstructured":"Excoffier, L., Slatkin, M.: Maximum\u2013likelihood estimation of molecular haplotype frequencies in a diploid population. Mol. Biol. Evol.\u00a012, 921\u2013927 (1995)","journal-title":"Mol. Biol. Evol."},{"issue":"5","key":"38_CR12","doi-asserted-by":"publisher","first-page":"1250","DOI":"10.1086\/320110","volume":"68","author":"H. Seltman","year":"2001","unstructured":"Seltman, H., Roeder, K., Devlin, B.: Transmission\/disequilibrium test meets measured haplotype analysis: family-based association analysis guided by evolution of haplotypes. Am. J. Hum. Genet.\u00a068(5), 1250\u20131263 (2001)","journal-title":"Am. J . Hum. Genet."},{"issue":"3","key":"38_CR13","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1086\/378205","volume":"73","author":"S. Zhang","year":"2003","unstructured":"Zhang, S., et al.: Transmission\/ disequilibrium test based on haplotype sharing for tightly linked markers. Am. J. Hum. Genet.\u00a073(3), 556\u2013579 (2003)","journal-title":"Am. J. Hum. Genet."},{"key":"38_CR14","doi-asserted-by":"crossref","unstructured":"Li, J., Jiang, T.: An exact solution for finding minimum recombinant haplotype configurations on pedigrees with missing data by integer linear programming. In: Proc. RECOMB 2004, pp. 20\u201329 (2004)","DOI":"10.1145\/974614.974618"},{"issue":"suppl. 1","key":"38_CR15","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1002\/1098-2272(2000)19:1+<::AID-GEPI10>3.0.CO;2-G","volume":"19","author":"J.R. O\u2019Connell","year":"2000","unstructured":"O\u2019Connell, J.R.: Zero-recombinant haplotyping: applications to fine mapping using SNPs. Genet. Epidemiol.\u00a019(suppl. 1), S64\u2013S70 (2000)","journal-title":"Genet. Epidemiol."},{"issue":"6","key":"38_CR16","doi-asserted-by":"publisher","first-page":"1434","DOI":"10.1086\/340610","volume":"70","author":"D. Qian","year":"2002","unstructured":"Qian, D., Beckmann, L.: Minimum-recombinant haplotyping in pedigrees. Am. J. Hum. Genet.\u00a070(6), 1434\u20131445 (2002)","journal-title":"Am. J. Hum. Genet."},{"key":"38_CR17","doi-asserted-by":"crossref","unstructured":"The International HapMap Consortium: The International HapMap Project. Nature\u00a0426, 789\u2013796 (December 2003)","DOI":"10.1038\/nature02168"},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, Approximation, and Complexity Classes. J. Comp. System Sci., 425\u2013440 (1991)","DOI":"10.1016\/0022-0000(91)90023-X"},{"issue":"4","key":"38_CR19","doi-asserted-by":"publisher","first-page":"978","DOI":"10.1086\/319501","volume":"68","author":"M. Stephens","year":"2001","unstructured":"Stephens, M., Smith, N.J., Donnelly, P.: A new statistical method for haplotype reconstruction from population data. Am. J. Hum. Genet.\u00a068(4), 978\u2013989 (2001)","journal-title":"Am. J. Hum. Genet."},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. of the 10th STOC, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"38_CR21","doi-asserted-by":"crossref","unstructured":"Li, J., Jiang, T.: Computing the Minimum Recombinant Haplotype Configuration from incomplete genotype data on a pedigree by integer linear programming. In: Proc. RECOMB 2004, pp. 20\u201329 (2004)","DOI":"10.1145\/974614.974618"},{"key":"38_CR22","unstructured":"Available at, http:\/\/www.cs.ucr.edu\/~lliu\/App_MRHC.pdf"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11602613_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T14:23:20Z","timestamp":1683296600000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11602613_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309352","9783540324263"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11602613_38","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11602613","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}