Department of Computer Science and Engineering, Southeast University, Nanjing 210096, China.
Comput Biol Med. 2013 Aug 1;43(7):922-32. doi: 10.1016/j.compbiomed.2013.04.008. Epub 2013 Apr 24.
It is one of the most important tasks in bioinformatics to identify the regulatory elements in gene sequences. Most of the existing algorithms for identifying regulatory elements are inclined to converge into a local optimum, and have high time complexity. Ant Colony Optimization (ACO) is a meta-heuristic method based on swarm intelligence and is derived from a model inspired by the collective foraging behavior of real ants. Taking advantage of the ACO in traits such as self-organization and robustness, this paper designs and implements an ACO based algorithm named ACRI (ant-colony-regulatory-identification) for identifying all possible binding sites of transcription factor from the upstream of co-expressed genes. To accelerate the ants' searching process, a strategy of local optimization is presented to adjust the ants' start positions on the searched sequences. By exploiting the powerful optimization ability of ACO, the algorithm ACRI can not only improve precision of the results, but also achieve a very high speed. Experimental results on real world datasets show that ACRI can outperform other traditional algorithms in the respects of speed and quality of solutions.
在生物信息学中，识别基因序列中的调控元件是一项非常重要的任务。大多数现有的识别调控元件的算法都倾向于收敛到局部最优解，并且时间复杂度较高。蚁群优化（Ant Colony Optimization，ACO）是一种基于群体智能的启发式方法，源于受真实蚂蚁集体觅食行为启发的模型。本文利用蚁群在自组织和鲁棒性等方面的特性，设计并实现了一种基于蚁群优化的算法 ACRI（ant-colony-regulatory-identification），用于从共表达基因的上游识别转录因子的所有可能结合位点。为了加速蚂蚁的搜索过程，提出了一种局部优化策略来调整蚂蚁在搜索序列上的起始位置。通过利用蚁群优化的强大优化能力，算法 ACRI 不仅可以提高结果的精度，而且可以实现非常高的速度。在真实数据集上的实验结果表明，ACRI 在速度和解决方案质量方面都优于其他传统算法。
