{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:37:39Z","timestamp":1742913459071,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319199283"},{"type":"electronic","value":"9783319199290"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19929-0_9","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T13:09:49Z","timestamp":1434373789000},"page":"100-113","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem"],"prefix":"10.1007","author":[{"given":"Paola","family":"Bonizzoni","sequence":"first","affiliation":[]},{"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[]},{"given":"Gunnar W.","family":"Klau","sequence":"additional","affiliation":[]},{"given":"Yuri","family":"Pirola","sequence":"additional","affiliation":[]},{"given":"Nadia","family":"Pisanti","sequence":"additional","affiliation":[]},{"given":"Simone","family":"Zaccaria","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"issue":"6","key":"9_CR1","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1089\/cmb.2012.0084","volume":"19","author":"D Aguiar","year":"2012","unstructured":"Aguiar, D., Istrail, S.: HapCompass: a fast cycle basis algorithm for accurate haplotype assembly of sequence data. J. Comput. Biol. 19(6), 577\u2013590 (2012)","journal-title":"J. Comput. Biol."},{"issue":"16","key":"9_CR2","doi-asserted-by":"publisher","first-page":"i153","DOI":"10.1093\/bioinformatics\/btn298","volume":"24","author":"V Bansal","year":"2008","unstructured":"Bansal, V., Bafna, V.: HapCUT: an efficient and accurate algorithm for the haplotype assembly problem. Bioinformatics 24(16), i153\u2013i159 (2008)","journal-title":"Bioinformatics"},{"issue":"6","key":"9_CR3","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/BF02945456","volume":"18","author":"P Bonizzoni","year":"2003","unstructured":"Bonizzoni, P., Della Vedova, G., Dondi, R., Li, J.: The haplotyping problem: an overview of computational models and solutions. J. Comput. Sci. Techol. 18(6), 675\u2013688 (2003)","journal-title":"J. Comput. Sci. Techol."},{"issue":"3","key":"9_CR4","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/s00439-008-0472-1","volume":"123","author":"B Browning","year":"2008","unstructured":"Browning, B., Browning, S.: Haplotypic analysis of Wellcome Trust case control consortium data. Hum. Genet. 123(3), 273\u2013280 (2008)","journal-title":"Hum. Genet."},{"issue":"16","key":"9_CR5","doi-asserted-by":"publisher","first-page":"1938","DOI":"10.1093\/bioinformatics\/btt349","volume":"29","author":"ZZ Chen","year":"2013","unstructured":"Chen, Z.Z., Deng, F., Wang, L.: Exact algorithms for haplotype assembly from whole-genome sequence data. Bioinformatics 29(16), 1938\u201345 (2013)","journal-title":"Bioinformatics"},{"issue":"1","key":"9_CR6","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 49(1), 13\u201336 (2007)","journal-title":"Algorithmica"},{"issue":"9","key":"9_CR7","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1016\/j.dam.2011.10.014","volume":"160","author":"R Dondi","year":"2012","unstructured":"Dondi, R.: New results for the Longest Haplotype Reconstruction problem. Discrete Appl. Math. 160(9), 1299\u20131310 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9_CR8","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1007\/s10589-010-9355-1","volume":"51","author":"P Fouilhoux","year":"2012","unstructured":"Fouilhoux, P., Mahjoub, A.: Solving VLSI design and DNA sequencing problems using bipartization of graphs. Comput. Optim. Appl. 51(2), 749\u2013781 (2012)","journal-title":"Comput. Optim. Appl."},{"key":"9_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"2","key":"9_CR10","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi) cut theorems and their applications. SIAM J. Comput. 25(2), 235\u2013251 (1996)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"9_CR11","doi-asserted-by":"publisher","first-page":"1386","DOI":"10.1016\/j.jcss.2006.02.001","volume":"72","author":"J Guo","year":"2006","unstructured":"Guo, J., et al.: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8), 1386\u20131396 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, B.V., Aguiar, D., Istrail, S.: Haplotype phasing by multi-assembly of shared haplotypes: phase-dependent interactions between rare variants. In: PSB, pp. 88\u201399. World Scientific Publishing (2011)","DOI":"10.1142\/9789814335058_0010"},{"issue":"12","key":"9_CR13","doi-asserted-by":"publisher","first-page":"i183","DOI":"10.1093\/bioinformatics\/btq215","volume":"26","author":"D He","year":"2010","unstructured":"He, D., et al.: Optimal algorithms for haplotype assembly from whole-genome sequence data. Bioinformatics 26(12), i183\u2013i190 (2010)","journal-title":"Bioinformatics"},{"key":"9_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/978-3-540-27801-6_10","volume-title":"Combinatorial Pattern Matching","author":"Y Jiao","year":"2004","unstructured":"Jiao, Y., Xu, J., Li, M.: On the k-closest substring and k-consensus pattern problems. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, pp. 130\u2013144. Springer, Heidelberg (2004)"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: STOC, pp. 767\u2013775. ACM (2002)","DOI":"10.1145\/509907.510017"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Papadimitriou, C., Raghavan, P.: Segmentation problems. In: STOC, pp. 473\u2013482. ACM (1998)","DOI":"10.1145\/276698.276860"},{"key":"9_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. 2161, pp. 182\u2013193. Springer, Heidelberg (2001)"},{"issue":"1","key":"9_CR18","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. Brief. Bioinform. 3(1), 23\u201331 (2002)","journal-title":"Brief. Bioinform."},{"issue":"2","key":"9_CR19","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/506147.506149","volume":"49","author":"R Ostrovsky","year":"2002","unstructured":"Ostrovsky, R., Rabani, Y.: Polynomial-time approximation schemes for geometric min-sum median clustering. J. ACM 49(2), 139\u2013156 (2002)","journal-title":"J. ACM"},{"key":"9_CR20","series-title":"Lecture Notes in Computer Science (Lecture Notes in Bioinformatics)","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-319-05269-4_19","volume-title":"Research in Computational Molecular Biology","author":"M Patterson","year":"2014","unstructured":"Patterson, M., Marschall, T., Pisanti, N., van Iersel, L., Stougie, L., Klau, G.W., Sch\u00f6nhuth, A.: WhatsHap: haplotype assembly for future-generation sequencing reads. In: Sharan, R. (ed.) RECOMB 2014. LNCS (LNBI), vol. 8394, pp. 237\u2013249. Springer, Heidelberg (2014)"},{"issue":"1","key":"9_CR21","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1109\/TCBB.2011.51","volume":"9","author":"Y Pirola","year":"2012","unstructured":"Pirola, Y., Bonizzoni, P., Jiang, T.: An efficient algorithm for haplotype inference on pedigrees with recombinations and mutations. IEEE\/ACM Trans. Comput. Biol. Bioinform. 9(1), 12\u201325 (2012)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Pirola, Y., et al.: Haplotype-based prediction of gene alleles using pedigrees and SNP genotypes. In: BCB, pp. 33\u201341. ACM (2013)","DOI":"10.1145\/2506583.2506592"},{"issue":"4","key":"9_CR23","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19929-0_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T21:50:46Z","timestamp":1676584246000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19929-0_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319199283","9783319199290"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19929-0_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}