{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:50:27Z","timestamp":1742950227310,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642021572"},{"type":"electronic","value":"9783642021589"}],"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-02158-9_3","type":"book-chapter","created":{"date-parts":[[2009,6,17]],"date-time":"2009-06-17T11:36:06Z","timestamp":1245238566000},"page":"3-14","source":"Crossref","is-referenced-by-count":1,"title":["On the Approximability of Some Haplotyping Problems"],"prefix":"10.1007","author":[{"given":"John","family":"Abraham","sequence":"first","affiliation":[]},{"given":"Zhixiang","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Richard","family":"Fowler","sequence":"additional","affiliation":[]},{"given":"Bin","family":"Fu","sequence":"additional","affiliation":[]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2004.12.017","volume":"335","author":"V. Bafna","year":"2005","unstructured":"Bafna, V., Istrail, S., Lancia, G., Rizzi, R.: Polynomial and APX-hard cases of the individual haplotyping problem. Theoretical Computer Science\u00a0335, 109\u2013125 (2005)","journal-title":"Theoretical Computer Science"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res.\u00a04, 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1089\/cmb.2008.0003","volume":"15","author":"Z. Chen","year":"2008","unstructured":"Chen, Z., Fu, B., Sweller, R., Yang, B., Zhao, Z., Zhu, B.: Linear probabilistic algorithms for the singular haplotype reconstruction problem from SNP fragments. J. Computational Biology\u00a015, 535\u2013546 (2008)","journal-title":"J. Computational Biology"},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s00453-007-0029-z","volume":"49","author":"R. Cilibrasi","year":"2007","unstructured":"Cilibrasi, R., van Iersel, L., Kelk, S., Tromp, J.: The complexity of the single individual SNP haplotyping problem. Algorithmica\u00a049, 13\u201336 (2007)","journal-title":"Algorithmica"},{"key":"3_CR5","first-page":"111","volume":"7","author":"A. Clark","year":"1990","unstructured":"Clark, A.: Inference of haplotypes from PCR-amplified samples of diploid populations. Molecular Biology Evolution\u00a07, 111\u2013122 (1990)","journal-title":"Molecular Biology Evolution"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1038\/ng582","volume":"28","author":"J. Douglas","year":"2001","unstructured":"Douglas, J., Boehnke, M., Gillanders, E., Trent, J., Gruber, S.: Experimentally-driven haplotypes substantially increase the efficiency of linkage disequillibrium studies. Nat. Genetics\u00a028, 361\u2013364 (2001)","journal-title":"Nat. Genetics"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Duh, R.-c., F\u00fcrer, M.: Approximation of k-set cover by semi-local optimization. In: Proc. 29th ACM Symp. on Theory of Comput (STOC 1997), pp. 256\u2013264 (1997)","DOI":"10.1145\/258533.258599"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","first-page":"103","volume-title":"Automata, Languages, and Programming","author":"N. Garg","year":"1994","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in directed and node weighted graphs. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol.\u00a0820, pp. 103\u2013111. Springer, Heidelberg (1994)"},{"key":"3_CR9","unstructured":"Gusfield, D.: A practical algorithm for optimal inference of haplotype from diploid populations. In: ISMB 2000, pp. 183\u2013189 (2000)"},{"key":"3_CR10","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, 305\u2013323 (2001)","journal-title":"J. Computational Biology"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions. In: RECOMB 2002, pp. 166\u2013175 (2002)","DOI":"10.1145\/565196.565218"},{"key":"3_CR12","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":"3_CR13","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e4stad","year":"1999","unstructured":"H\u00e4stad, J.: Clique is hard to approximate within n\n                        1\u2009\u2212\u2009\u03b5\n                        . Acta Mathematica\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"key":"3_CR14","doi-asserted-by":"publisher","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.: An approximation algorithm for haplotype inference by maximum parsimony. J. Computational Biology\u00a012, 1261\u20131274 (2005)","journal-title":"J. Computational Biology"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. Johnson","year":"1974","unstructured":"Johnson, D.: Approximation algorithms for combinatorial problems. J. Comput. System Sci.\u00a09, 256\u2013278 (1974)","journal-title":"J. Comput. System Sci."},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1287\/ijoc.1040.0085","volume":"16","author":"G. Lancia","year":"2004","unstructured":"Lancia, G., Pinotti, M.C., Rizzi, R.: Haplotyping populations by pure parsimony: complexity and algorithms. INFORMS Journal on computing\u00a016, 348\u2013359 (2004)","journal-title":"INFORMS Journal on computing"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/3-540-44676-1_15","volume-title":"Algorithms - ESA 2001","author":"G. Lancia","year":"2001","unstructured":"Lancia, G., Bafna, V., Istrail, S., Lippert, R., Schwartz, R.: SNPs Problems, Complexity and Algorithms. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 182\u2013193. Springer, Heidelberg (2001)"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.orl.2005.05.007","volume":"34","author":"G. Lancia","year":"2006","unstructured":"Lancia, G., Rizzi, R.: A polynomial solution to a special case of the parsimony haplotyping problem. Operations Research letters\u00a034, 289\u2013295 (2006)","journal-title":"Operations Research letters"},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1093\/bib\/3.1.23","volume":"3","author":"R. Lippert","year":"2002","unstructured":"Lippert, R., Schwartz, R., Lancia, G., Istrail, S.: Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem. Briefings in bioinformatics\u00a03, 23\u201331 (2002)","journal-title":"Briefings in bioinformatics"},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. L\u00f3vasz","year":"1975","unstructured":"L\u00f3vasz, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics\u00a013, 383\u2013390 (1975)","journal-title":"Discrete Mathematics"},{"key":"3_CR21","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM\u00a041, 960\u2013981 (1994)","journal-title":"J. ACM"},{"key":"3_CR22","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-540-30219-3_23","volume-title":"Algorithms in Bioinformatics","author":"A. Panconesi","year":"2004","unstructured":"Panconesi, A., Sozio, M.: Fast Hare: A fast heuristic for single individual SNP haplotype reconstruction. In: Jonassen, I., Kim, J. (eds.) WABI 2004. LNCS (LNBI), vol.\u00a03240, pp. 266\u2013277. Springer, Heidelberg (2004)"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP. In: Proc. 29th ACM Symp. on Theory of Comput. (STOC 1997), pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"3_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/3-540-45784-4_3","volume-title":"Algorithms in Bioinformatics","author":"R. Rizzi","year":"2002","unstructured":"Rizzi, R., Bafna, V., Istrail, S., Lancia, G.: Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem. In: Guig\u00f3, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol.\u00a02452, pp. 29\u201343. Springer, Heidelberg (2002)"},{"key":"3_CR25","doi-asserted-by":"publisher","first-page":"2456","DOI":"10.1093\/bioinformatics\/bti352","volume":"21","author":"R.S. Wang","year":"2005","unstructured":"Wang, R.S., Wu, L.Y., Li, Z.P., Zhang, X.S.: Haplotype reconstruction from SNP fragments by minimum error correction. Bioinformatics\u00a021, 2456\u20132462 (2005)","journal-title":"Bioinformatics"},{"key":"3_CR26","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, 1773\u20131780 (2003)","journal-title":"Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02158-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T11:59:33Z","timestamp":1558267173000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02158-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642021572","9783642021589"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02158-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}