@article{9e59bcf28f0b49d19c3005a0a599eccc, title = "Better ILP models for haplotype assembly", abstract = "Background: The haplotype assembly problem for diploid is to find a pair of haplotypes from a given set of aligned Single Nucleotide Polymorphism (SNP) fragments (reads). It has many applications in association studies, drug design, and genetic research. Since this problem is computationally hard, both heuristic and exact algorithms have been designed for it. Although exact algorithms are much slower, they are still of great interest because they usually output significantly better solutions than heuristic algorithms in terms of popular measures such as the Minimum Error Correction (MEC) score, the number of switch errors, and the QAN50 score. Exact algorithms are also valuable because they can be used to witness how good a heuristic algorithm is. The best known exact algorithm is based on integer linear programming (ILP) and it is known that ILP can also be used to improve the output quality of every heuristic algorithm with a little decline in speed. Therefore, faster ILP models for the problem are highly demanded. Results: As in previous studies, we consider not only the general case of the problem but also its all-heterozygous case where we assume that if a column of the input read matrix contains at least one 0 and one 1, then it corresponds to a heterozygous SNP site. For both cases, we design new ILP models for the haplotype assembly problem which aim at minimizing the MEC score. The new models are theoretically better because they contain significantly fewer constraints. More importantly, our experimental results show that for both simulated and real datasets, the new model for the all-heterozygous (respectively, general) case can usually be solved via CPLEX (an ILP solver) at least 5 times (respectively, twice) faster than the previous bests. Indeed, the running time can sometimes be 41 times better. Conclusions: This paper proposes a new ILP model for the haplotype assembly problem and its all-heterozygous case, respectively. Experiments with both real and simulated datasets show that the new models can be solved within much shorter time by CPLEX than the previous bests. We believe that the models can be used to improve heuristic algorithms as well.", keywords = "Diploid, Haplotype assembly, ILP model, Minimun error correction", author = "Maryam Etemadi and Mehri Bagherian and Zhi-Zhong Chen and Lusheng Wang", year = "2018", doi = "10.1186/s12859-018-2012-x", language = "English", volume = "19", pages = "11--21", journal = "BMC Bioinformatics", issn = "1471-2105", publisher = "BioMed Central Ltd.", number = "Supp 1", note = "28th International Conference on Genome Informatics, GIW/BIOINFO 2017 ; Conference date: 31-10-2017 Through 03-11-2017", url = "https://www.kobic.kr/giw-bioinfo2017/", }