{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:28:48Z","timestamp":1773271728958,"version":"3.50.1"},"reference-count":25,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2003,4]]},"abstract":"<jats:p> We study haplotype reconstruction under the Mendelian law of inheritance and the minimum recombination principle on pedigree data. We prove that the problem of finding a minimum-recombinant haplotype configuration (MRHC) is in general NP-hard. This is the first complexity result concerning the problem to our knowledge. An iterative algorithm based on blocks of consecutive resolved marker loci (called block-extension) is proposed. It is very efficient and can be used for large pedigrees with a large number of markers, especially for those data sets requiring few recombinants (or recombination events). A polynomial-time exact algorithm for haplotype reconstruction without recombinants is also presented. This algorithm first identifies all the necessary constraints based on the Mendelian law and the zero recombinant assumption, and represents them using a system of linear equations over the cyclic group Z<jats:sub>2<\/jats:sub>. By using a simple method based on Gaussian elimination, we could obtain all possible feasible haplotype configurations. A C++ implementation of the block-extension algorithm, called PedPhase, has been tested on both simulated data and real data. The results show that the program performs very well on both types of data and will be useful for large scale haplotype inference projects. <\/jats:p>","DOI":"10.1142\/s0219720003000204","type":"journal-article","created":{"date-parts":[[2003,4,28]],"date-time":"2003-04-28T06:49:23Z","timestamp":1051512563000},"page":"41-69","source":"Crossref","is-referenced-by-count":61,"title":["EFFICIENT INFERENCE OF HAPLOTYPES FROM GENOTYPES ON A PEDIGREE"],"prefix":"10.1142","volume":"01","author":[{"given":"JING","family":"LI","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Riverside, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TAO","family":"JIANG","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Riverside, CA, USA"},{"name":"Shanghai Center for Bioinformatics Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,1,25]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-1809.1990.tb00390.x"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1038\/ng1001-229"},{"key":"rf5","author":"Doi K.","journal-title":"Private Communication"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1038\/ng582"},{"key":"rf7","first-page":"921","volume":"12","author":"Excoffier L.","journal-title":"Mol. Biol. Evol."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1126\/science.1069424"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1126\/science.293.5530.583b"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1086\/302756"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1997.4.535"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/3.1.23"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1101\/gr.194801"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1086\/338446"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2272(2000)19:1+<::AID-GEPI10>3.0.CO;2-G"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1086\/301904"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1086\/302663"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1086\/340610"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1086\/320110"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1086\/302398"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1145\/356502.356494"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1086\/319501"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1159\/000022890"},{"key":"rf27","first-page":"259","author":"Thomas A.","journal-title":"Stat. Comput."},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1086\/302954"},{"key":"rf29","first-page":"356","volume":"41","author":"Wijsman E. M.","journal-title":"Am. J. Hum. Genet."}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720003000204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:07:55Z","timestamp":1565118475000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720003000204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":25,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[2003,4]]}},"alternative-id":["10.1142\/S0219720003000204"],"URL":"https:\/\/doi.org\/10.1142\/s0219720003000204","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}