{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:27:24Z","timestamp":1773275244315,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540442110","type":"print"},{"value":"9783540457848","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45784-4_3","type":"book-chapter","created":{"date-parts":[[2007,10,16]],"date-time":"2007-10-16T14:33:38Z","timestamp":1192545218000},"page":"29-43","source":"Crossref","is-referenced-by-count":47,"title":["Practical Algorithms and Fixed-Parameter Tractability for the Single Individual SNP Haplotyping Problem"],"prefix":"10.1007","author":[{"given":"Romeo","family":"Rizzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vineet","family":"Bafna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sorin","family":"Istrail","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Lancia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,10,10]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, intervals graphs and graph planarity testing using PQ-tree algorithms. J. Comput. System Sci., 13:335\u2013379, 1976.","journal-title":"J. Comput. System Sci."},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1038\/885","volume":"19","author":"A. Chakravarti","year":"1998","unstructured":"A. Chakravarti. It\u2019s raining SNP, hallelujah? Nature Genetics, 19:216\u2013217, 1998.","journal-title":"Nature Genetics"},{"key":"3_CR3","first-page":"111","volume":"7","author":"A. Clark","year":"1990","unstructured":"A. Clark. Inference of haplotypes from PCR-amplified samples of diploid populations. Molecular Biology Evolution, 7:111\u2013122, 1990.","journal-title":"Molecular Biology Evolution"},{"key":"3_CR4","unstructured":"D. Gusfield. A practical algorithm for optimal inference of haplotypes from diploid populations. In R. Altman, T.L. Bailey, P. Bourne, M. Gribskov, T. Lengauer, I.N. Shindyalov, L.F. Ten Eyck, and H. Weissig, editors, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, pages 183\u2013189, Menlo Park, CA, 2000. AAAI Press."},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"D. Gusfield. Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions. In G. Myers, S. Hannenhalli, S. Istrail, P. Pevzner, and M. Watermand, editors, Proceedings of the Sixth Annual International Conference on Computational Biology, pages 166\u2013175, New York, NY, 2002. ACM Press.","DOI":"10.1145\/565196.565218"},{"issue":"5530","key":"3_CR6","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1126\/science.293.5530.583b","volume":"293","author":"L. Helmuth","year":"2001","unstructured":"L. Helmuth. Genome research: Map of the human genome 3.0. Science, 293(5530):583\u2013585, 2001.","journal-title":"Science"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1038\/35057062","volume":"409","author":"International Human Genome Sequencing Consortium","year":"2001","unstructured":"International Human Genome Sequencing Consortium. Initial sequencing and analysis of the human genome. Nature, 409:860\u2013921, 2001.","journal-title":"Nature"},{"key":"3_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/3-540-44676-1_15","volume-title":"SNPs problems, complexity and algorithms","author":"G. Lancia","year":"2001","unstructured":"G. Lancia, V. Bafna, S. Istrail, R. Lippert, and R. Schwartz. SNPs problems, complexity and algorithms. In Proceedings of Annual European Symposium on Algorithms (ESA), volume 2161 of Lecture Notes in Computer Science, pages 182\u2013193. Springer, 2001."},{"issue":"1","key":"3_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1093\/bib\/3.1.23","volume":"3","author":"R. Lippert","year":"2002","unstructured":"R. Lippert, R. Schwartz, G. Lancia, and S. Istrail. Algorithmic strategies for the SNPs haplotype assembly problem. Briefings in Bioinformatics, 3(1):23\u201331, 2002.","journal-title":"Briefings in Bioinformatics"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis. The approximation of maximum subgraph problems. In Proceedings of 20th Int. Colloqium on Automata, Languages and Programming, pages 40\u201351. Springer-Verlag, 1994.","DOI":"10.1007\/3-540-56939-1_60"},{"issue":"5413","key":"3_CR11","first-page":"406","volume":"284","author":"E. Marshall","year":"1999","unstructured":"E. Marshall. Drug firms to create public database of genetic mutations. Science Magazine, 284(5413):406\u2013407, 1999.","journal-title":"Science Magazine"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"1304","DOI":"10.1126\/science.1058040","volume":"291","author":"J.C. Venter","year":"2001","unstructured":"J.C. Venter et al. The sequence of the human genome. Science, 291:1304\u20131351, 2001.","journal-title":"Science"},{"key":"3_CR13","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1101\/gr.7.5.401","volume":"7","author":"J. Weber","year":"1997","unstructured":"J. Weber and E. Myers. Human whole genome shotgun sequencing. Genome Research, 7:401\u2013409, 1997.","journal-title":"Genome Research"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45784-4_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T20:24:07Z","timestamp":1556915047000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45784-4_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540442110","9783540457848"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-45784-4_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}