枚举单体型组装问题多个最优解的遗传算法设计

Design of Genetic Algorithm to enumerate multiple optimal solutions to haplotype assembly problem

单体型组装问题就是根据个体基因组测序获得的DNA序列数据重构出该个体的一对单体型。目前单体型组装问题的各种优化计算模型已有相关的启发式算法和参数化精确算法,但是这些算法只能得出一个最优解,即一对单体型。可是生物问题的最优解往往不是唯一的,或者真实解可能只是接近最优的。该文设计了一个新的能枚举出最优的多个解的遗传算法。实验结果表明该算法具有较高的单体型重建精度,并为生物学家根据领域知识在算法获得的多个解的基础进一步选择提供了可能。

The haplotype assembly problem aims to reconstruct a pair of haplotype of an individual from its DNA sequencing fragment data.There are some heuristic algorithms and parameterized algorithms for the various computational optimal models.However,these algorithms work out with only one optimal solution,i.e.a pair of haplotypes.However,the optimal solution to a biological problem is usually not unique,or the real solution may be suboptimal.The paper proposes a new genetic algorithm to enumerate multiple optimal solutions to the haplotype assembly problem.Experimental results show that this algorithm is more accurate in haplotype reconstruction and provides the chance for the biologists to choose one from these multiple solutions based on some biological knowledge.