论文部分内容阅读
SNPs(单核苷酸多态性)为研究人类个体间患病风险与药物反应的差异和研究多基因复杂疾病提供了新方法。为寻找变异区域,理论上应对全部SNPs位点进行基因分型。传统的方法效率低且费用昂贵。研究发现序列中的标签SNPs—tag SNPs携带了 SNPs数据集的绝大部分遗传信息,因此寻找tag SNPs意义重大。但从SNPs数据集中找出tag SNPs需要耗费巨大的计算量,机器学习方法是解决这一问题的有效途径。对tag SNPs的寻找是一种组合优化问题。有文献提出应用集合覆盖方法成功地解决了小数据集上tag SNPs寻找的组合优化问题。但对于复杂的集合覆盖问题,现有算法难以得到优化解。鉴于蚁群算法有较强的近优解搜索能力,本文提出了基于罚函数的集合覆盖蚁群算法(PCACO)和具有随机扰动特性的集合覆盖蚁群算法(RCACO)用于tag SNPs搜索。但标准ACO算法易陷入局部最优,且全局搜索时间长,本文进行了以下改进:(1)在PCACO算法中,通过设定信息素浓度范围来避免信息素的过分集中或分散,从而改善全局搜索能力。(2)引入罚函数,在迭代过程加入与高斯曲线相吻合的惩罚因子来避免算法陷入局部最优,并提高了针对tag SNPs搜索的收敛速度。(3)采用了随机扰动的转移策略,实现了基于随机扰动ACO算法(即RCACO)用于tag SNPs搜索。算法的主要改进有:一是针对tag SNPs搜索问题设计了相应的随机选择策略和扰动策略;二是提出符合倒指数曲线的扰动因子。与PCACO算法相比RCACO算法进一步提高了 tag SNPs搜索的精确度。(4)根据SNPs位点间的连锁不平衡特性,对高维小样本数据进行K-means聚类处理,降低了搜索空间,从而提高海量SNPs数据关联分析的工作效率。上述工作对基于ACO算法的tag SNPs获取方法进行了尽可能深入的研究,提出了将ACO算法应用于集合覆盖的两种不同策略,并实现了对高维小样本数据的聚类。在模拟数据集上进行的算法实验结果表明,与近两年的PSO、GA两类算法相比,所提出的算法运行时间较短,且搜索结果精确度更高。