{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,22]],"date-time":"2024-06-22T15:50:38Z","timestamp":1719071438743},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2007,6]]},"abstract":"<jats:p> The individual haplotyping problem is a computing problem of reconstructing two haplotypes for an individual based on several optimal criteria from one's fragments sequencing data. This paper is based on the fact that the length of a fragment and the number of the fragments covering a SNP (single nucleotide polymorphism) site are both very small compared with the length of a sequenced region and the total number of the fragments and introduces the parameterized haplotyping problems. With m fragments whose maximum length is k<jats:sub>1<\/jats:sub>, n SNP sites and the number of the fragments covering a SNP site no more than k<jats:sub>2<\/jats:sub>, our algorithms can solve the gapless MSR (Minimum SNP Removal) and MFR (Minimum Fragment Removal) problems in the time complexity O(nk<jats:sub>1<\/jats:sub>k<jats:sub>2<\/jats:sub> + m log m + nk<jats:sub>2<\/jats:sub> + mk<jats:sub>1<\/jats:sub>) and [Formula: see text] respectively. Since, the value of k<jats:sub>1<\/jats:sub> and k<jats:sub>2<\/jats:sub> are both small (about 10) in practice, our algorithms are more efficient and applicable compared with the algorithms of V. Bafna et al. of time complexity O(mn<jats:sup>2<\/jats:sup>) and O(m<jats:sup>2<\/jats:sup>n + m<jats:sup>3<\/jats:sup>), respectively. <\/jats:p>","DOI":"10.1142\/s0219720007002710","type":"journal-article","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T00:32:00Z","timestamp":1186705920000},"page":"795-816","source":"Crossref","is-referenced-by-count":10,"title":["RESEARCH ON PARAMETERIZED ALGORITHMS OF THE INDIVIDUAL HAPLOTYPING PROBLEM"],"prefix":"10.1142","volume":"05","author":[{"given":"MINZHU","family":"XIE","sequence":"first","affiliation":[{"name":"School of Information Science and Engineering, Central South University, Changsha, Hunan Province 410083, China"},{"name":"College of Physics and Information Science, Hunan Normal University, Changsha, Hunan Province 410083, China"}]},{"given":"JIAN'ER","family":"CHEN","sequence":"additional","affiliation":[{"name":"School of Information Science and Engineering, Central South University, Changsha, Hunan Province 410083, China"}]},{"given":"JIANXIN","family":"WANG","sequence":"additional","affiliation":[{"name":"School of Information Science and Engineering, Central South University, Changsha, Hunan Province 410083, China"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1101\/gr.8.7.748","volume":"8","author":"Miller T. P.","journal-title":"Genome Res."},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1126\/science.1059431"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1038\/79876"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.017"},{"key":"rf7","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1038\/10290","volume":"22","author":"Cargill M.","journal-title":"Nat. Genet."},{"key":"rf8","doi-asserted-by":"crossref","first-page":"22","DOI":"10.2144\/jun0203","volume":"32","author":"Holden A. L.","journal-title":"BioTechniques"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1038\/35057149"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.74.12.5463"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1038\/35057062"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1126\/science.1105436"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1126\/science.1069424"},{"key":"rf14","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1101\/gr.7.5.401","volume":"7","author":"Weber J. L.","journal-title":"Genome Research"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720007002710","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T02:44:44Z","timestamp":1565145884000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720007002710"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6]]},"references-count":13,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2007,6]]}},"alternative-id":["10.1142\/S0219720007002710"],"URL":"https:\/\/doi.org\/10.1142\/s0219720007002710","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6]]}}}