HapCUT swMATH ID: 35352 Software Authors: Bansal, Vikas; Bafna, Vineet Description: HapCUT: an efficient and accurate algorithm for the haplotype assembly problem. Motivation: The goal of the haplotype assembly problem is to reconstruct the two haplotypes (chromosomes) for an individual using a mix of sequenced fragments from the two chromosomes. This problem has been shown to be computationally intractable for various optimization criteria. Polynomial time algorithms have been proposed for restricted versions of the problem. In this article, we consider the haplotype assembly problem in the most general setting, i.e. fragments of any length and with an arbitrary number of gaps. Results: We describe a novel combinatorial approach for the haplotype assembly problem based on computing max-cuts in certain graphs derived from the sequenced fragments. Levy et al. have sequenced the complete genome of a human individual and used a greedy heuristic to assemble the haplotypes for this individual. We have applied our method HapCUTto infer haplotypes from this data and demonstrate that the haplotypes inferred using HapCUT are significantly more accurate (20–25 Homepage: https://academic.oup.com/bioinformatics/article/24/16/i153/201665 Related Software: ReFHap; SpeedHap; Eclat; iSNO-PseAAC; iRSpot-PseDNC; iCDI-PseFpt; Signal-CF; iEzy-drug; iNuc-PhysChem; iSNO-AAPair; iRSpot-TNCPseAAC; Wenxiang; iNuc-PseKNC; UBCSAT; ReHap; MiniMaxSat Cited in: 6 Documents all top 5 Cited by 13 Authors 2 Mousavi, Sayyed Rasoul 1 Baneres, David 1 Falsafain, Hossein 1 Ghadiri, Nasser 1 Han, Libin 1 Hermelin, Danny 1 Khodadadi, Ilnaz 1 Lancia, Giuseppe G. 1 Nadimi, Reza 1 Peng, Qinke 1 Rozenberg, Liat 1 Xu, Tao 1 Zhong, Tao Cited in 4 Serials 3 Journal of Theoretical Biology 1 Theoretical Computer Science 1 RAIRO. Operations Research 1 Optimization Letters Cited in 4 Fields 4 Biology and other natural sciences (92-XX) 2 Computer science (68-XX) 1 Combinatorics (05-XX) 1 Operations research, mathematical programming (90-XX) Citations by Year