一种基于概率编码的用于多序列比对的量子遗传算法。

A probabilistic coding based quantum genetic algorithm for multiple sequence alignment.

作者信息

Huo Hongwei, Xie Qiaoluan, Shen Xubang, Stojkovic Vojislav

机构信息

School of Computer Science and Technology, Xidian University, Xi'an, Shaanxi 710071, P.R. China.

出版信息

Comput Syst Bioinformatics Conf. 2008;7:15-26.

PMID:19642265

Abstract

This paper presents an original Quantum Genetic algorithm for Multiple sequence ALIGNment (QGMALIGN) that combines a genetic algorithm and a quantum algorithm. A quantum probabilistic coding is designed for representing the multiple sequence alignment. A quantum rotation gate as a mutation operator is used to guide the quantum state evolution. Six genetic operators are designed on the coding basis to improve the solution during the evolutionary process. The features of implicit parallelism and state superposition in quantum mechanics and the global search capability of the genetic algorithm are exploited to get efficient computation. A set of well known test cases from BAliBASE2.0 is used as reference to evaluate the efficiency of the QGMALIGN optimization. The QGMALIGN results have been compared with the most popular methods (CLUSTALX, SAGA, DIALIGN, SB_PIMA, and QGMALIGN) results. The QGMALIGN results show that QGMALIGN performs well on the presenting biological data. The addition of genetic operators to the quantum algorithm lowers the cost of overall running time.

摘要

本文提出了一种用于多序列比对的原创量子遗传算法（QGMALIGN），它结合了遗传算法和量子算法。设计了一种量子概率编码来表示多序列比对。使用量子旋转门作为变异算子来引导量子态演化。在编码基础上设计了六个遗传算子，以在进化过程中改进解。利用量子力学中的隐含并行性和态叠加特性以及遗传算法的全局搜索能力来实现高效计算。使用一组来自BAliBASE2.0的著名测试用例作为参考来评估QGMALIGN优化的效率。将QGMALIGN的结果与最流行的方法（CLUSTALX、SAGA、DIALIGN、SB_PIMA和QGMALIGN）的结果进行了比较。QGMALIGN的结果表明，QGMALIGN在呈现的生物学数据上表现良好。在量子算法中添加遗传算子降低了总体运行时间成本。