求解三倍体个体单体型重建问题的遗传算法

针对最少错误更正(the minimum error correction,MEC)模型,对三倍体个体单体型重建问题进行研究,提出一种基于遗传算法的三倍体个体单体型重建算法GTIHR.该算法采用一种新颖的染色体编码方法和一种有效的爬山算子.这种较短的染色体编码方式能够构造较小的解空间,以便于算法快速收敛到较优解.此外,爬山算子通过为染色体编码注入随机信息来避免早熟现象,并充分利用SNP片段中的有效信息来逐步修正染色体编码取值.实验利用鸟枪法测序模拟片段生成器CELSIM生成片段数据.与以往求解算法的比较分析结果显示,GTIHR算法能够获得更高重建率的单体型,具有较强的实用价值.