{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,4]],"date-time":"2024-08-04T18:38:39Z","timestamp":1722796719402},"reference-count":39,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1051\/ro\/2015037","type":"journal-article","created":{"date-parts":[[2015,10,2]],"date-time":"2015-10-02T06:40:41Z","timestamp":1443768041000},"page":"331-340","source":"Crossref","is-referenced-by-count":8,"title":["Algorithmic approaches for the single individual haplotyping problem"],"prefix":"10.1051","volume":"50","author":[{"given":"Giuseppe","family":"Lancia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2016,3,24]]},"reference":[{"key":"R1","unstructured":"Aguiar D. and Istrail S., HapCompass: A fast cycle basis algorithm for accurate haplotype assembly of sequence data.J. Comput. Biol.19(2012) 577\u2013590."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Aguiar D. and Istrail S., Haplotype assembly in polyploid genomes and identical by descent shared tracts.Bioinformatics29(2013) 352\u2013360.","DOI":"10.1093\/bioinformatics\/btt213"},{"key":"R3","unstructured":"Bafna V., Istrail S., Lancia G. and Rizzi R., Polynomial and APX-hard cases of the individual haplotyping problem.Theoret. Comput. Sci.335(2005) 109\u2013125."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Bansal V. and Bafna V., HapCUT: an efficient and accurate algorithm for the haplotype assembly problem.Bioinformatics24(2008) i153\u2013i159.","DOI":"10.1093\/bioinformatics\/btn298"},{"key":"R5","unstructured":"Bayzid S., Alam M., Mueen A. and Rahman S., A fast and accurate algorithm for diploid individual haplotype reconstruction.J. Bioinform. Comput. Biol.11(2013) 1\u201312."},{"key":"R6","unstructured":"Bayzid S., Alam M., Mueen A. and Rahman S., Hmec: A heuristic algorithm for individual haplotyping with minimum error correction.ISRN Bioinformatics2013(2013) 1\u201310."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Booth K. and Lueker G., Testing for the consecutive ones property, interval graphs and graph planarity using pq-tree algorithms.J. Comput. System Sci.13(1976) 335\u2013379.","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"R8","unstructured":"Bansal V., Halpern A., Axelrod N. and Bafna V., An MCMC algorithm for haplotype assembly from whole-genome sequence data.Genome Res.18(2008) 1336\u20131346."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Chen Z., Fu B., Schweller R., Yang B., Zhao Z. and Zhu B., Linear time probabilistic algorithms for the singular haplotype reconstruction problem from SNP fragments.J. Comput. Biolo.15(2008) 535\u2013546.","DOI":"10.1089\/cmb.2008.0003"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Chen Z., Deng F. and Wang L., Exact algorithms for haplotype assembly from whole-genome sequence data.Bioinformatics29(2013) 1938\u20131945.","DOI":"10.1093\/bioinformatics\/btt349"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"R. Cilibrasi, L. V. Iersel, S. Kelk and J. Tromp, On the complexity of several haplotyping problems.Proc. of Annual Workshop on Algorithms in Bioinformatics (WABI). Vol. 3692 ofLect. Notes Comput. Sci.Springer (2005) 128\u2013139.","DOI":"10.1007\/11557067_11"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Consortium I.H., The international hapmap project.Nature426(2003) 789\u2013796.","DOI":"10.1038\/nature02168"},{"key":"R13","unstructured":"Collins F.S., Morgan M. and Patrinos A., The human genome project: Lessons from large-scale biology.Science300(2003) 286\u2013290."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Deng F., Cui W. and Wang L., A highy accurate heuristic algorithm for the haplotype assembly problem.BMC Genomics14(2013) 1\u201310.","DOI":"10.1186\/1471-2164-14-S2-S2"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Douglas J., Boehnke M., Gillanders E., Trent J. and Gruber S., Experimentally-derived haplotypes substantially increase the efficiency of linkage disequilibrium studies.Nature Genetics28(2001) 361\u2013364.","DOI":"10.1038\/ng582"},{"key":"R16","unstructured":"J. Duitama, T. Huebsch, G. McEwen, E. Suk and M. Hoehe, Refhap: a reliable and fast algorithm for single individual haplotyping, InProc. of the 1st ACM International conference on Bioinformatics and Computational Biology, DMTCS\u201903. ACM. New York (2010) 160\u2013169."},{"key":"R17","unstructured":"M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Edited by W.H. Freeman (1979)."},{"key":"R18","unstructured":"Genovese L., Geraci F. and Pellegrini M., Speedhap: an accurate heuristic for the single individual SNP haplotyping problem with many gaps, high reading error rate and low coverage.IEEE\/ACM Trans Comput Biol Bioinform.5(2008) 492\u2013502."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Geraci F., A comparison of several algorithms for the single individual SNP haplotyping reconstruction problem.Bioinformatics26(2010) 2217\u20132225.","DOI":"10.1093\/bioinformatics\/btq411"},{"key":"R20","unstructured":"F. Geraci and M. Pellegrini, Rehap: an integrated system for the haplotype assembly problem from shotgun sequencing data. InBIOINFORMATICS 2010\u2212Proc. of the First International Conference on Bioinformatics, edited by A.L. N. Fred, J. Filipe and H. Gamboa. INSTICC Press (2010) 15\u201325."},{"key":"R21","unstructured":"Greenberg H., Hart W. and Lancia G., Opportunities for combinatorial optimization in computational biology.INFORMS J. Comput.16(2004) 1\u201322."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"D. Gusfield and S.H. Orzack, Haplotype inference. InHandbook of Computational Molecular Biology. Champman and Hall\/CRC-press (2005) 1\u201328.","DOI":"10.1201\/9781420036275.ch18"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"He D., Choi A., Pipatsrisawat K., Darwiche A. and Eskin E., Optimal algorithms for haplotype assembly from whole-genome sequence data.Bioinformatics26(2010) i83\u2013i190.","DOI":"10.1093\/bioinformatics\/btq215"},{"key":"R24","unstructured":"Kargar M., Poormohammadi H., Pirhaji L., Sadeghi M., Pezeshk H. and Eslahchi C., Enhanced evolutionary and heuristic algorithms for haplotype reconstruction problem using minimum error correction model.MATCH Commun. Math. Comput. Chem.62(2009) 261\u2013274."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"G. Lancia, V. Bafna, S. Istrail, R. Lippert and R. Schwartz, SNPs problems, complexity and algorithms. InProc. of the Annual European Symposium on Algorithms (ESA). Vol. 2161 ofLect. Notes Comput. Sci.Springer (2001) 182\u2013193.","DOI":"10.1007\/3-540-44676-1_15"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Levy S., et al. The diploid genome sequence of an individual human.PLoS Biol.5(2007) e254.","DOI":"10.1371\/journal.pbio.0050254"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Li L., Kim J. and Waterman M., Haplotype reconstruction from SNP alignment.J. Comput. Biology11(2004) 507\u2013518.","DOI":"10.1089\/1066527041410454"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Lippert R., Schwartz R., Lancia G. and Istrail S., Algorithmic strategies for the SNPs haplotype assembly problem.Briefings in Bioinformatics3(2002) 23\u201331.","DOI":"10.1093\/bib\/3.1.23"},{"key":"R29","unstructured":"A. Panconesi and M. Sozio, Fast hare: A fast heuristic for single individual SNP haplotype reconstruction. InProc. of Annual Workshop on Algorithms in Bioinformatics (WABI). Vol. 3240 ofAlgorithms in Bioinformatics. Springer (2004) 266\u2013277."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"R. Rizzi, V. Bafna, S. Istrail and G. Lancia, Practical algorithms and fixed-parameter tractability for the single individual SNP haplotyping problem, inProc. of Annual Workshop on Algorithms in Bioinformatics (WABI). Edited by R. Guigo and D. Gusfield. Vol. 2452 ofLect. Notes Comput. Sci.Springer (2002) 29\u201343.","DOI":"10.1007\/3-540-45784-4_3"},{"key":"R31","unstructured":"Venter J., et al.. The sequence of the human genome.Science291(2001) 1304\u20131351."},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Wang R., Wu L., Li Z. and Zhang X., Haplotype reconstruction from SNP fragments by minimum error correction.Bioinformatics21(2005) 2456\u20132462.","DOI":"10.1093\/bioinformatics\/bti352"},{"key":"R33","unstructured":"Wang R., Wu L., Zhang X. and Chen L., A markov chain model for haplotype assembly from SNP fragments.Genome Inform17(2006) 162\u2013171."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Wu J., Wang J. and Chen J., A heuristic algorithm for haplotype reconstruction from aligned weighted SNP fragments.Int. J. Bioinform. Res. Appl.9(2013) 13\u201324.","DOI":"10.1504\/IJBRA.2013.050743"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"Xie M. and Wang J., An improved (and practical) parametrized algorithm for the individual haplotyping problem MFR with mate pairs.Algorithmica52(2008) 250\u2013266.","DOI":"10.1007\/s00453-007-9150-2"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"Xie M., Wang J. and Chen J., A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments and genotype with errors.Bioinformatics24(2008) i105\u2013i113.","DOI":"10.1093\/bioinformatics\/btn147"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"Xie M., Wang J. and Jiang T., A fast and accurate algorithm for single individual haplotyping.BMC Systems Biology6(2012) 1\u201310.","DOI":"10.1186\/1752-0509-6-S2-S8"},{"key":"R38","unstructured":"Zhao Y., Wu L., Zhang J., Wang R. and Zhang X., Haplotype assembly from aligned weighted SNP fragments.Comput Biol. Chem.29(2005) 281\u2013287."},{"key":"R39","doi-asserted-by":"crossref","unstructured":"Zhang X., Wang R., Wu A. and Zhang W., Minimum conflict individual haplotyping from SNP fragments and related genotype.Evolutionary Bioinformatics Online2(2006) 271\u2013280.","DOI":"10.1177\/117693430600200032"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2015037\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,22]],"date-time":"2022-05-22T15:39:47Z","timestamp":1653233987000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2015037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,24]]},"references-count":39,"journal-issue":{"issue":"2"},"alternative-id":["ro150037-s"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2015037","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,24]]}}}