{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:34:01Z","timestamp":1773272041130,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2003,11,1]],"date-time":"2003-11-01T00:00:00Z","timestamp":1067644800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Comput. Sci. &amp; Technol."],"published-print":{"date-parts":[[2003,11]]},"DOI":"10.1007\/bf02945456","type":"journal-article","created":{"date-parts":[[2008,9,7]],"date-time":"2008-09-07T16:27:34Z","timestamp":1220804854000},"page":"675-688","source":"Crossref","is-referenced-by-count":92,"title":["The Haplotyping problem: An overview of computational models and solutions"],"prefix":"10.1007","volume":"18","author":[{"given":"Paola","family":"Bonizzoni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianluca","family":"Della Vedova","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jing","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02945456_CR1","doi-asserted-by":"crossref","unstructured":"International human genome sequencing consortium. Initial sequencing and analysis of the human genome.Nature, February 2001, 409(6822): 860\u2013921.","DOI":"10.1038\/35057062"},{"issue":"5507","key":"BF02945456_CR2","doi-asserted-by":"crossref","first-page":"1304","DOI":"10.1126\/science.1058040","volume":"291","author":"J C Venter","year":"2001","unstructured":"Venter J Cet al. The sequence of the human genome.Science, 2001, 291(5507): 1304\u20131351.","journal-title":"Science"},{"issue":"5547","key":"BF02945456_CR3","doi-asserted-by":"crossref","first-page":"1669","DOI":"10.1126\/science.1065573","volume":"294","author":"N Patil","year":"2001","unstructured":"Patil N, Berno A Jet al. Blocks of limited haplotype diversity revealed by high-resolution scanning of human chromosome 21.Science, 2001, 294(5547): 1669\u20131670.","journal-title":"Science"},{"key":"BF02945456_CR4","unstructured":"Daly M, Roux J, Schaffer Set al. Fine-Structure Haplotype Map of 5q31: Implications for Gene-Based Studies and Genomic Ld Mapping, 2001."},{"issue":"5576","key":"BF02945456_CR5","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 Het al. The structure of haplotype blocks in the human genome.Science, 2002, 296(5576): 2225\u20132229.","journal-title":"Science"},{"key":"BF02945456_CR6","doi-asserted-by":"crossref","unstructured":"Lancia G, Bafna V, Istrail Set al. SNPs problems, complexity and algorithms. InProc. 9th European Symp. Algorithms (ESA), 2001, pp. 182\u2013193.","DOI":"10.1007\/3-540-44676-1_15"},{"key":"BF02945456_CR7","doi-asserted-by":"crossref","unstructured":"Gusfield D. Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions. InProc. 6th Annual Conference on Research in Computational Molecular Biology (RECOMB), 2002, pp.166\u2013175.","DOI":"10.1145\/565196.565218"},{"key":"BF02945456_CR8","unstructured":"Halperin E, Eskin E, Karp R M. Efficient reconstruction of haplotype structure via perfect phylogeny.Journal of Bioinformatics and Computational Biology, to appear."},{"key":"BF02945456_CR9","doi-asserted-by":"crossref","unstructured":"Halperin E, Eskin E, Karp R M. Large scale reconstruction of haplotypes from genotype data. InProc. 7th Annual Conference on Research in Computational Molecular Biology (RECOMB), 2003, pp.104\u2013113.","DOI":"10.1145\/640075.640088"},{"key":"BF02945456_CR10","doi-asserted-by":"crossref","unstructured":"Zhang K, Deng M, Chen Tet al. A dynamic programming algorithm for haplotype block partitioning. InProc. The National Academy of Sciences, USA, 2002, 99(11): 7335\u20137339.","DOI":"10.1073\/pnas.102186799"},{"issue":"2","key":"BF02945456_CR11","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 and Evolution, 1990, 7(2): 111\u2013122.","journal-title":"Molecular Biology and Evolution"},{"issue":"3","key":"BF02945456_CR12","doi-asserted-by":"crossref","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.Journal of Computational Biology, 2001, 8(3): 305\u2013323.","journal-title":"Journal of Computational Biology"},{"key":"BF02945456_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge, 1997."},{"key":"BF02945456_CR14","doi-asserted-by":"crossref","unstructured":"Bafna V, Gusfield D, Lancia G, Yooseph S. Haplotyping as perfect phylogeny: A direct approach.Journal of Computational Biology, to appear.","DOI":"10.1089\/10665270360688048"},{"issue":"293","key":"BF02945456_CR15","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1126\/science.293.5530.583b","volume":"5530","author":"L Helmuth","year":"2001","unstructured":"Helmuth L. Genome research: Map of human genome 3.0.Science 2001, 5530(293): 583\u2013585.","journal-title":"Science"},{"issue":"Suppl.1","key":"BF02945456_CR16","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1002\/1098-2272(2000)19:1+<::AID-GEPI10>3.0.CO;2-G","volume":"19","author":"J R O\u2019Connel","year":"2000","unstructured":"O\u2019Connel J R. Zero-recombinant haplotyping: Applications to fine mapping using snps.Genet. Epidemiol., 2000, 19(Suppl.1): S64\u201370.","journal-title":"Genet. Epidemiol."},{"issue":"6","key":"BF02945456_CR17","doi-asserted-by":"crossref","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., 2002, 70(6): 1434\u20131445.","journal-title":"Am. J. Hum. Genet."},{"issue":"1","key":"BF02945456_CR18","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1159\/000022890","volume":"50","author":"P Tapadar","year":"2000","unstructured":"Tapadar P, Ghosh S, Majumder P P. Haplotyping in pedigrees via a genetic algorithm.Hum. Hered., 2000, 50(1): 43\u201356.","journal-title":"Hum. Hered."},{"key":"BF02945456_CR19","doi-asserted-by":"crossref","unstructured":"Li J, Jiang T. Efficient rule-based haplotyping algorithms for pedigree data. InProc. 7th Annual Conference on Research in Computational Molecular Biology (RECOMB), 2003, pp.197\u2013206.","DOI":"10.1145\/640075.640101"},{"key":"BF02945456_CR20","unstructured":"Garey M R, Johnson D S. Computer and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979."},{"key":"BF02945456_CR21","doi-asserted-by":"crossref","unstructured":"Doi K, Li J, Jiang T. Minimum recombinant haplotype configuration on tree pedigrees. Accepted bythe 3rd International Workshop on Algorithms in Bioinformatics (WABI), Hungary, 2003.","DOI":"10.1007\/978-3-540-39763-2_25"},{"key":"BF02945456_CR22","doi-asserted-by":"crossref","unstructured":"Rizzi R, Bafna V, Istrail S, Lancia G. Pratical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem. InProc. Algorithms in Bioinformatics, Second International Workshop (WABI 2002), 2003, pp.29\u201343.","DOI":"10.1007\/3-540-45784-4_3"},{"key":"BF02945456_CR23","first-page":"325","volume":"21","author":"M Gr\u00f6tschel","year":"1984","unstructured":"Gr\u00f6tschel M, Lovasz L, Schrijver, A. A polynomial algorithm for perfect graphs.Annals of Discrete Mathematics, 1984, 21: 325\u2013356.","journal-title":"Annals of Discrete Mathematics"},{"issue":"3","key":"BF02945456_CR24","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K S Booth","year":"1976","unstructured":"Booth K S, Lueker G S. Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms.Journal of Computer and System Sciences, 1976, 13(3): 335\u2013379.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF02945456_CR25","unstructured":"Orzack S, Gusfield D, Stanton V P. The absolute and relative accuracy of haplotype inferral methods and a consensus approach to haplotype inferral. In51st Annual Meeting of the American Society of Human Genetics, 2001."},{"issue":"5","key":"BF02945456_CR26","first-page":"921","volume":"12","author":"L Excoffier","year":"1995","unstructured":"Excoffier L, Slatkin M. Maximum-likelihood estimation of molecular haplotype frequencies in a diploid population.Molecular Biology and Evolution, 1995, 12(5): 921\u2013927.","journal-title":"Molecular Biology and Evolution"},{"key":"BF02945456_CR27","doi-asserted-by":"crossref","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.American Journal of Human Genetics, 2001, 68: 978\u2013989.","journal-title":"American Journal of Human Genetics"},{"key":"BF02945456_CR28","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1086\/338446","volume":"710","author":"T Niu","year":"2002","unstructured":"Niu T, Qin Z S, Xu X, Liu J S. Bayesian haplotype inference for multiple linked single-nucleotide polymorphisms.American Journal of Human Genetics, 2002, 710: 157\u2013169.","journal-title":"American Journal of Human Genetics"},{"key":"BF02945456_CR29","volume-title":"Machine Learning","author":"T M Mitchell","year":"1987","unstructured":"Mitchell T M. Machine Learning. McGraw Hill, New York, 1987."}],"container-title":["Journal of Computer Science and Technology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02945456.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02945456\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02945456","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T21:17:00Z","timestamp":1738358220000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02945456"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,11]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2003,11]]}},"alternative-id":["BF02945456"],"URL":"https:\/\/doi.org\/10.1007\/bf02945456","relation":{},"ISSN":["1000-9000","1860-4749"],"issn-type":[{"value":"1000-9000","type":"print"},{"value":"1860-4749","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,11]]}}}