Department of Applied Mathematics, Faculty of Mathematical Sciences, University of Guilan, Rasht, 41938-33697, Iran.
Division of Information System Design, Tokyo Denki University, Saitama, 350-0394, Japan.
BMC Bioinformatics. 2018 Feb 19;19(Suppl 1):52. doi: 10.1186/s12859-018-2012-x.
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.
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.
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.
对于二倍体，单体型组装问题是指从给定的对齐单核苷酸多态性（SNP）片段（reads）中找到一对单体型。它在关联研究、药物设计和遗传研究中有许多应用。由于这个问题在计算上很难，因此已经设计了启发式和精确算法来解决它。虽然精确算法要慢得多，但它们仍然很有意义，因为它们通常在流行的度量标准（如最小纠错分数（MEC）、开关错误数和 QAN50 分数）方面输出明显更好的解决方案，而启发式算法则不能。精确算法也很有价值，因为它们可以用来证明启发式算法有多好。最著名的精确算法是基于整数线性规划（ILP）的，并且已知 ILP 也可以用于提高每个启发式算法的输出质量，而速度略有下降。因此，对于该问题，更快的 ILP 模型是非常需要的。
与以前的研究一样，我们不仅考虑了问题的一般情况，还考虑了其全杂合情况，即我们假设如果输入读矩阵的某一列至少包含一个 0 和一个 1，则它对应于杂合 SNP 位点。对于这两种情况，我们为单体型组装问题设计了新的 ILP 模型，旨在最小化 MEC 分数。新模型在理论上更好，因为它们包含的约束明显更少。更重要的是，我们的实验结果表明，对于模拟和真实数据集，全杂合（分别为一般）情况下的新模型通常可以通过 CPLEX（ILP 求解器）求解，速度至少快 5 倍（分别为 2 倍）。实际上，运行时间有时可以快 41 倍。
本文分别为单体型组装问题及其全杂合情况提出了一个新的 ILP 模型。使用真实和模拟数据集的实验表明，新模型可以通过 CPLEX 在更短的时间内解决，比以前的最佳模型快得多。我们相信这些模型也可以用于改进启发式算法。
