{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:09:31Z","timestamp":1675296571287},"reference-count":24,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2010,10,27]],"date-time":"2010-10-27T00:00:00Z","timestamp":1288137600000},"content-version":"unspecified","delay-in-days":26,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2010,10]]},"abstract":"<jats:p>Haplotypes are more useful in complex disease gene mapping than single-nucleotide polymorphisms (SNPs). However, haplotypes are difficult to obtain directly using biological experiments, which has prompted research into efficient computational methods for determining haplotypes. The individual haplotyping problem called Minimum Letter Flip (MLF) is a computational problem that, given a set of aligned DNA sequence fragment data of an individual, induces the corresponding haplotypes by flipping minimum SNPs. There has been no practical exact algorithm for solving the problem. Due to technical limits in DNA sequencing experiments, the maximum length of a fragment sequenced directly is about 1kb. In consequence, with a genome-average SNP density of 1.84 SNPs per 1 kb of DNA sequence, the maximum number <jats:italic>k<\/jats:italic><jats:sub>1<\/jats:sub> of SNP sites that a fragment covers is usually small. Moreover, in order to save time and money, the maximum number <jats:italic>k<\/jats:italic><jats:sub>2<\/jats:sub> of fragments that cover an SNP site is usually no more than 19. Building on these fragment data properties, the current paper introduces a new parameterised algorithm with running time <jats:italic>O<\/jats:italic>(<jats:italic>nk<\/jats:italic><jats:sub>2<\/jats:sub>2<jats:sup><jats:italic>k<\/jats:italic><jats:sub>2<\/jats:sub><\/jats:sup> + <jats:italic>mlogm<\/jats:italic> + <jats:italic>mk<\/jats:italic><jats:sub>1<\/jats:sub>), where <jats:italic>m<\/jats:italic> is the number of fragments and <jats:italic>n<\/jats:italic> is the number of SNP sites. In practical biological applications, the algorithm solves the MLF problem efficiently even if <jats:italic>m<\/jats:italic> and <jats:italic>n<\/jats:italic> are large.<\/jats:p>","DOI":"10.1017\/s096012951000023x","type":"journal-article","created":{"date-parts":[[2010,10,27]],"date-time":"2010-10-27T07:48:27Z","timestamp":1288165707000},"page":"851-863","source":"Crossref","is-referenced-by-count":4,"title":["A practical parameterised algorithm for the individual haplotyping problem MLF"],"prefix":"10.1017","volume":"20","author":[{"given":"MINZHU","family":"XIE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JIANXIN","family":"WANG","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JIANER","family":"CHEN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,10,27]]},"reference":[{"key":"S096012951000023X_ref4","doi-asserted-by":"publisher","DOI":"10.1126\/science.1069424"},{"key":"S096012951000023X_ref23","doi-asserted-by":"publisher","DOI":"10.2174\/157489306775330570"},{"key":"S096012951000023X_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02945456"},{"key":"S096012951000023X_ref17","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pgen.0030111"},{"key":"S096012951000023X_ref19","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti352"},{"key":"S096012951000023X_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44696-6_23"},{"key":"S096012951000023X_ref3","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2008.0003"},{"key":"S096012951000023X_ref2","doi-asserted-by":"publisher","DOI":"10.1086\/513149"},{"key":"S096012951000023X_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_15"},{"key":"S096012951000023X_ref18","doi-asserted-by":"publisher","DOI":"10.1126\/science.1058040"},{"key":"S096012951000023X_ref5","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1040.0073"},{"key":"S096012951000023X_ref6","doi-asserted-by":"publisher","DOI":"10.1126\/science.1105436"},{"key":"S096012951000023X_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_22"},{"key":"S096012951000023X_ref9","doi-asserted-by":"publisher","DOI":"10.1038\/nature02168"},{"key":"S096012951000023X_ref10","doi-asserted-by":"publisher","DOI":"10.1038\/nature04226"},{"key":"S096012951000023X_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30219-3_23"},{"key":"S096012951000023X_ref21","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720007002710"},{"key":"S096012951000023X_ref11","doi-asserted-by":"publisher","DOI":"10.1038\/35057062"},{"key":"S096012951000023X_ref13","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pbio.0050254"},{"key":"S096012951000023X_ref14","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/3.1.23"},{"key":"S096012951000023X_ref15","first-page":"202","volume-title":"Proceedings of the 7th International Conference on Intelligent Systems for Molecular Biology, ISMB","author":"Myers","year":"1999"},{"key":"S096012951000023X_ref20","unstructured":"Wernicke S. (2003) On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems, Ph.D. Thesis, University T\u00fcbingen."},{"key":"S096012951000023X_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9150-2"},{"key":"S096012951000023X_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.compbiolchem.2005.05.001"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096012951000023X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T21:23:44Z","timestamp":1556400224000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096012951000023X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["S096012951000023X"],"URL":"https:\/\/doi.org\/10.1017\/s096012951000023x","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10]]}}}