{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T08:15:19Z","timestamp":1777104919083,"version":"3.51.4"},"reference-count":16,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":772,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Understanding exact structure of an individual\u2019s haplotype plays a significant role in various fields of human genetics. Despite tremendous research effort in recent years, fast and accurate haplotype reconstruction remains as an active research topic, mainly owing to the computational challenges involved. Existing haplotype assembly algorithms focus primarily on improving accuracy of the assembly, making them computationally challenging for applications on large high-throughput sequence data. Therefore, there is a need to develop haplotype reconstruction algorithms that are not only accurate but also highly scalable.<\/jats:p>\n               <jats:p>Results: In this article, we introduce FastHap, a fast and accurate haplotype reconstruction approach, which is up to one order of magnitude faster than the state-of-the-art haplotype inference algorithms while also delivering higher accuracy than these algorithms. FastHap leverages a new similarity metric that allows us to precisely measure distances between pairs of fragments. The distance is then used in building the fuzzy conflict graphs of fragments. Given that optimal haplotype reconstruction based on minimum error correction is known to be NP-hard, we use our fuzzy conflict graphs to develop a fast heuristic for fragment partitioning and haplotype reconstruction.<\/jats:p>\n               <jats:p>Availability: An implementation of FastHap is available for sharing on request.<\/jats:p>\n               <jats:p>Contact: sepideh@cs.ucla.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu442","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T11:23:57Z","timestamp":1409052237000},"page":"i371-i378","source":"Crossref","is-referenced-by-count":27,"title":["FastHap: fast and accurate single individual haplotype reconstruction using fuzzy conflict graphs"],"prefix":"10.1093","volume":"30","author":[{"given":"Sepideh","family":"Mazrouee","sequence":"first","affiliation":[{"name":"Computer Science Department, University of California Los Angeles (UCLA), 3551 Boelter Hall, Los Angeles, CA 90095-1596, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of California Los Angeles (UCLA), 3551 Boelter Hall, Los Angeles, CA 90095-1596, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2014,8,22]]},"reference":[{"key":"2023012711531378700_btu442-B1","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1089\/cmb.2012.0084","article-title":"Hapcompass: a fast cycle basis algorithm for accurate haplotype assembly of sequence data","volume":"19","author":"Aguiar","year":"2012","journal-title":"J. Comput. Biol."},{"key":"2023012711531378700_btu442-B2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximability Properties: Combinatorial Optimization Problems and Their Approximability Properties","author":"Ausiello","year":"1999"},{"key":"2023012711531378700_btu442-B3","doi-asserted-by":"crossref","first-page":"i153","DOI":"10.1093\/bioinformatics\/btn298","article-title":"Hapcut: an efficient and accurate algorithm for the haplotype assembly problem","volume":"24","author":"Bansal","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012711531378700_btu442-B4","doi-asserted-by":"crossref","first-page":"1336","DOI":"10.1101\/gr.077065.108","article-title":"An mcmc algorithm for haplotype assembly from whole-genome sequence data","volume":"18","author":"Bansal","year":"2008","journal-title":"Genome Res."},{"key":"2023012711531378700_btu442-B5","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/11557067_11","article-title":"On the complexity of several haplotyping problems","volume-title":"Algorithms in Bioinformatics","author":"Cilibrasi","year":"2005"},{"key":"2023012711531378700_btu442-B6","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1126\/science.1162986","article-title":"Real-time DNA sequencing from single polymerase molecules","volume":"323","author":"Eid","year":"2009","journal-title":"Science"},{"key":"2023012711531378700_btu442-B7","author":"Garey"},{"key":"2023012711531378700_btu442-B8","doi-asserted-by":"crossref","first-page":"i183","DOI":"10.1093\/bioinformatics\/btq215","article-title":"Optimal algorithms for haplotype assembly from whole-genome sequence data","volume":"26","author":"He","year":"2010","journal-title":"Bioinformatics"},{"key":"2023012711531378700_btu442-B9","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1101\/gr.168450.113","article-title":"Reconstructing complex regions of genomes using long-read sequencing technology","volume":"24","author":"Huddleston","year":"2014","journal-title":"Genome Res."},{"key":"2023012711531378700_btu442-B10","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/3-540-44676-1_15","article-title":"SNPs problems, complexity, and algorithms","volume-title":"AlgorithmsESA 2001","author":"Lancia","year":"2001"},{"key":"2023012711531378700_btu442-B11","doi-asserted-by":"crossref","first-page":"e254","DOI":"10.1371\/journal.pbio.0050254","article-title":"The diploid genome sequence of an individual human","volume":"5","author":"Levy","year":"2007","journal-title":"PLoS Biol."},{"key":"2023012711531378700_btu442-B12","article-title":"Human 54x dataset","author":"PacificBiosciences,P","year":"2014"},{"key":"2023012711531378700_btu442-B13","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1007\/978-3-540-30219-3_23","article-title":"Fast hare: a fast heuristic for single individual SNP haplotype reconstruction","volume-title":"Algorithms in Bioinformatics","author":"Panconesi","year":"2004"},{"key":"2023012711531378700_btu442-B14","doi-asserted-by":"crossref","DOI":"10.1109\/SWAT.1974.22","article-title":"P-complete problems and approximate solutions","volume-title":"Proceedings of the 15th Annual Symposium on Switching and Automata Theory (Swat 1974)","author":"Sahni","year":"1974"},{"key":"2023012711531378700_btu442-B15","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1038\/nbt0308-256b","article-title":"1000 genomes project","volume":"26","author":"Siva","year":"2008","journal-title":"Nat. Biotechnol."},{"key":"2023012711531378700_btu442-B16","author":"VenterInst (2014)"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/17\/i371\/48927691\/bioinformatics_30_17_i371.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/30\/17\/i371\/48927691\/bioinformatics_30_17_i371.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T12:19:08Z","timestamp":1674821948000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/30\/17\/i371\/199678"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,22]]},"references-count":16,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2014,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu442","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2014,9,1]]},"published":{"date-parts":[[2014,8,22]]}}}