Huo Hong-Wei, Stojkovic Vojislav, Xie Qiao-Luan
School of Computer Science and Technology, Xidian University, Xi'an 710071, China.
J Bioinform Comput Biol. 2010 Feb;8(1):59-75. doi: 10.1142/s0219720010004549.
Quantum parallelism arises from the ability of a quantum memory register to exist in a superposition of base states. Since the number of possible base states is 2(n), where n is the number of qubits in the quantum memory register, one operation on a quantum computer performs what an exponential number of operations on a classical computer performs. The power of quantum algorithms comes from taking advantages of quantum parallelism. Quantum algorithms are exponentially faster than classical algorithms. Genetic optimization algorithms are stochastic search algorithms which are used to search large, nonlinear spaces where expert knowledge is lacking or difficult to encode. QGMALIGN--a probabilistic coding based quantum-inspired genetic algorithm for multiple sequence alignment is presented. 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 experimental results show that QGMALIGN can compete with the popular methods, such as CLUSTALX and SAGA, and performs well on the presenting biological data. Moreover, the addition of genetic operators to the quantum-inspired algorithm lowers the cost of overall running time.
量子并行性源于量子存储寄存器能够以基态叠加的形式存在。由于可能的基态数量为2(n)，其中n是量子存储寄存器中的量子比特数，量子计算机上的一次操作相当于经典计算机上指数数量的操作所执行的任务。量子算法的强大之处在于利用了量子并行性。量子算法比经典算法快指数倍。遗传优化算法是一种随机搜索算法，用于在缺乏专家知识或难以编码的大型非线性空间中进行搜索。本文提出了QGMALIGN——一种基于概率编码的量子启发式遗传算法，用于多序列比对。使用量子旋转门作为变异算子来引导量子态演化。在编码基础上设计了六个遗传算子，以在进化过程中改进解。实验结果表明，QGMALIGN可以与CLUSTALX和SAGA等流行方法相媲美，并且在呈现的生物数据上表现良好。此外，在量子启发式算法中添加遗传算子降低了总体运行时间成本。
