{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:28Z","timestamp":1759638568781},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,2,14]],"date-time":"2009-02-14T00:00:00Z","timestamp":1234569600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,3]]},"DOI":"10.1007\/s00453-009-9288-1","type":"journal-article","created":{"date-parts":[[2009,2,16]],"date-time":"2009-02-16T04:56:01Z","timestamp":1234760161000},"page":"283-296","source":"Crossref","is-referenced-by-count":11,"title":["A Practical Exact Algorithm for the Individual Haplotyping Problem MEC\/GI"],"prefix":"10.1007","volume":"56","author":[{"given":"Jianxin","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minzhu","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianer","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,2,14]]},"reference":[{"issue":"5366","key":"9288_CR1","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1126\/science.280.5366.1077","volume":"280","author":"D.G. Wang","year":"1998","unstructured":"Wang, D.G., Fan, J.B., Siao, C.J., : Large-scale identification, mapping, and genotyping of single-nucleotide polymorphisms in the human genome. Science 280(5366), 1077\u20131082 (1998)","journal-title":"Science"},{"issue":"5529","key":"9288_CR2","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1126\/science.1059431","volume":"293","author":"J.C. Stephens","year":"2001","unstructured":"Stephens, J.C., Schneider, J.A., Tanguay, D.A., : Haplotype variation and linkage disequilibrium in 313 human genes. Science 293(5529), 489\u2013493 (2001)","journal-title":"Science"},{"issue":"1","key":"9288_CR3","doi-asserted-by":"crossref","first-page":"105","DOI":"10.2174\/157489306775330570","volume":"1","author":"X.S. Zhang","year":"2006","unstructured":"Zhang, X.S., Wang, R.S., Wu, L.Y., Chen, L.: Models and algorithms for haplotyping problem. Curr. Bioinform. 1(1), 105\u2013114 (2006)","journal-title":"Curr. Bioinform."},{"key":"9288_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/3-540-44676-1_15","volume-title":"Proc. Ann. European Symp. on Algorithms (ESA)","author":"G. Lancia","year":"2001","unstructured":"Lancia, G., Bafna, V., Istrail, S., Lippert, R., Schwartz, R.: SNPs problems, complexity and algorithms. In: Meyer, F. (ed.) Proc. Ann. European Symp. on Algorithms (ESA). Lecture Notes in Computer Science, vol. 2191, pp. 182\u2013193. Springer, Berlin (2001)"},{"key":"9288_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/978-3-540-24719-7_2","volume-title":"The 1st RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotype Inference","author":"D. Gusfield","year":"2004","unstructured":"Gusfield, D.: An overview of combinatorial methods for haplotype inference. In: Istrail, S., Waterman, M.S., Clark, A.G. (eds.) The 1st RECOMB Satellite Workshop on Computational Methods for SNPs and Haplotype Inference. Lecture Notes in Computer Science, vol. 2983, pp. 9\u201325. Springer, Berlin (2004)"},{"issue":"3","key":"9288_CR6","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1142\/S0219720007002710","volume":"5","author":"M. Xie","year":"2007","unstructured":"Xie, M., Chen, J., Wang, J.: Research on parameterized algorithms of the individual haplotyping problem. J. Bioinform. Comput. Biol. 5(3), 795\u2013816 (2007)","journal-title":"J. Bioinform. Comput. Biol."},{"issue":"2","key":"9288_CR7","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1007\/s00453-007-9150-2","volume":"52","author":"M. Xie","year":"2008","unstructured":"Xie, M., Wang, J.: An improved (and practical) parameterized algorithm for the individual haplotyping problem MFR with mate-pairs. Algorithmica 52(2), 250\u2013266 (2008)","journal-title":"Algorithmica"},{"issue":"1","key":"9288_CR8","doi-asserted-by":"crossref","first-page":"1","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), 1\u20139 (2002)","journal-title":"Brief. Bioinform."},{"issue":"10","key":"9288_CR9","doi-asserted-by":"crossref","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 21(10), 2456\u20132462 (2005)","journal-title":"Bioinformatics"},{"key":"9288_CR10","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1177\/117693430600200032","volume":"2","author":"X. Zhang","year":"2006","unstructured":"Zhang, X., Wang, R., Wu, L., Zhang, W.: Minimum conflict individual haplotyping from SNP fragments and related genotype. Evol. Bioinform. 2, 271\u2013280 (2006)","journal-title":"Evol. Bioinform."},{"key":"9288_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"1","key":"9288_CR12","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/s11390-005-0003-7","volume":"20","author":"J. Chen","year":"2005","unstructured":"Chen, J.: Parameterized computation and complexity: a new approach dealing with NP-hardness. J.\u00a0Comput. Sci. Technol. 20(1), 18\u201337 (2005)","journal-title":"J.\u00a0Comput. Sci. Technol."},{"issue":"6822","key":"9288_CR13","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1038\/35057149","volume":"409","author":"The International SNP Map Working Group","year":"2001","unstructured":"The International SNP Map Working Group: A map of human genome sequence variation containing 1.42 million single nucleotide polymorphisms. Nature 409(6822), 928\u2013933 (2001)","journal-title":"Nature"},{"issue":"12","key":"9288_CR14","doi-asserted-by":"crossref","first-page":"5463","DOI":"10.1073\/pnas.74.12.5463","volume":"74","author":"F. Sanger","year":"1977","unstructured":"Sanger, F., Nicklen, S., Coulson, A.R.: DNA sequencing with chain-terminating inhibitors. Proc. Natl. Acad. Sci. 74(12), 5463\u20135467 (1977)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"5576","key":"9288_CR15","doi-asserted-by":"crossref","first-page":"2225","DOI":"10.1126\/science.1069424","volume":"296","author":"S.B. Gabriel","year":"2002","unstructured":"Gabriel, S.B., Schaffner, S.F., Nguyen, H., : The structure of haplotype blocks in the human genome. Science 296(5576), 2225\u20132229 (2002)","journal-title":"Science"},{"issue":"5712","key":"9288_CR16","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1126\/science.1105436","volume":"307","author":"D.A. Hinds","year":"2005","unstructured":"Hinds, D.A., Stuve, L.L., Nilsen, G.B., : Whole-genome patterns of common DNA variation in three human populations. Science 307(5712), 1072\u20131079 (2005)","journal-title":"Science"},{"issue":"7063","key":"9288_CR17","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1038\/nature04226","volume":"437","author":"The International HapMap Consortium","year":"2005","unstructured":"The International HapMap Consortium: A haplotype map of the human genome. Nature 437(7063), 1299\u20131320 (2005)","journal-title":"Nature"},{"key":"9288_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/11427186_22","volume-title":"Proc. WEA","author":"F. H\u00fcffner","year":"2005","unstructured":"H\u00fcffner, F.: Algorithm engineering for optimal graph bipartization. In: Nikoletseas, S.E. (ed.) Proc. WEA. Lecture Notes in Computer Science, vol. 3503, pp. 240\u2013252. Springer, Berlin (2005)"},{"key":"9288_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/978-3-540-30219-3_23","volume-title":"Proc. WABI","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.) Proc. WABI. Lecture Notes in Computer Science, vol. 3240, pp.\u00a0266\u2013277. Springer, Berlin (2004)"},{"key":"9288_CR20","first-page":"202","volume-title":"Proc. ISMB","author":"G. Myers","year":"1999","unstructured":"Myers, G.: A dataset generator for whole genome shotgun sequencing. In: Lengauer, T., Schneider, R., Bork, P., (eds.) Proc. ISMB, pp. 202\u2013210. AAAI Press, Menlo Park (1999)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9288-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9288-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9288-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:03Z","timestamp":1559123103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9288-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,14]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["9288"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9288-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,14]]}}}