| Multiple Sequence Alignment (MSA) is one of the most important and the most challenge work in bioinformatics. Although many aligning methods have been proposed, they are not perfect very much in precision and efficiency. So, it is necessary to improve the existing methods and to explore new methods. In this paper we proposed two methods to solve the multiple sequence alignment using Adaptive Genetic Algorithm and Quantum Evolution Algorithm separately after studying these existing methods.Two methods, AGAMS and QEAMSA were proposed in this paper. AGAMS is one of the methods using Genetic Algorithm to solving MSA. For the problem of MSA it reduced the memory by coding only for spaces, and designed 5 new genetic operators decreasing the complexity of operation compared to SAGA algorithm with 22 genetic operators, at the same time decreasing the convergence time. It also imports Adaptive strategy, which balances between the convergence speed and the global optimization. QEAMSA is a new proposed aligning method. It altered the basic QEA: represented the MSA problem with Q-bit, designed one method adapting to MSA updating Q-bit individual. For avoiding the disadvantage, that QEA has a little stronger randomicity, we imported an optimizing operator which make the QEA better adapt to solving MSA problem. At last we tested 5 cases sets, Ref1~Ref5 with deferent characteristic, in Balibase benchmark, using AGAMSA and QEAMSA separately. The results of them compared to that of CLUSTAL X and SAGA published. The comparing result show that the result of testing is worse than that of CLUSTAL X and SAGA for Ref1 and Ref5, but better than that of CLUSTAL X and SAGA for Ref2~Ref4. For all the five testing sets, QEAMSA is better than AGAMSA. The result of testing shows that AGAMSA and QEAMSA are both valid aligning methods, and adapt to alignment sequences including orphan sequence and sequence included N/C terminal extensions. |
PDF Full Text Request