利用随机扰动特性的集合覆盖蚁群算法识别tag SNPs

A Collection of Random-Perturbation Characteristics Covered Ant Colony Algorithm to Identify tag SNPs

序列中的标签SNPs-tag SNPs携带了SNPs数据集的绝大部分遗传信息,因此寻找tag SNPs意义重大.但从SNPs数据集中找出tag SNPs需要耗费巨大的计算量,传统的方法效率低且费用昂贵,对于复杂的集合覆盖问题,现有算法难以得到优化解.鉴于蚁群算法有较强的近优解搜索能力,提出具有随机扰动特性的集合覆盖蚁群算法(RCACO)用于tag SNPs搜索.模拟数据集上进行的算法实验结果表明,与近两年的PSO、GA两类算法相比,所提出的算法运行时间较短,搜索结果精确度更高.

Tag SNPs carries most of the genetic information of SNPs data set, which makes it significant to search tagSNPs. However, identifying tag SNPs from SNPs data set costs a huge amount of computation so that traditional methodsare inefficient and expensive, and it turns difficult to obtain optimal solutions in case of complicated set cover problems.Since ant colony algorithms（ACO） work well in searching near-optimal solution, a new algorithm is proposed in searchingtag SNPs, which combine setcovering with ACO based on random-perturbation（RCACO）. Experimental results on simu-lated data sets show that the proposed algorithms achieve higher accuracy with less time consumption than PSO and GAalgorithms adopted in recent years.