自适应蚁群算法在DNA序列比对中应用研究

Application of Adaptive ant Colony Algorithm in DNA Sequence Alignment

研究基因DNA序列比对校准问题。由于DNA序列数据量较大,给序列比对造成了很大的复杂性,而传统的聚类算法在分析DNA序列比对数据时的低效性和分类精度低问题缺陷,提出了一种基于改进的自适应蚁群算法的DNA序列比对算法。首先给出一个计分函数和一个得分策略,再任意给出一对DNA序列,建立一个序列比对矩阵。根据蚂蚁所走过的方向和得分比例来计算序列,同时信息素的变化量采用矩阵来存储,经过有限次迭代,蚂蚁找到一条最优路径,最终一条就是与原来DNA最相似的DNA链。实验结果表明,改进的算法具有一定的时间和精度的优越性,更适于解决大规模DNA序列数据比对问题。

The application of ant colony algorithm in DNA sequence alignment was studied. A DNA sequence a- lignment algorithms based on modified ant colony algorithm was proposed. First, a scoring function and a score of strategy were given. Then one pair of DNA sequence was given discretionarily to build a sequence alignment matrix. According to the ants＇ advancing direction and the direction points, the percentage of sequence was calculated, and the changes in pheromone were stored to a matrix. After finite iterations, the ants found an optimal path, and the fi- nal one was most similar to the original DNA chain. Experiments show that the improved algorithm has the superiority in time and accuracy, and is more suitable for large - scale DNA sequence data alignment.