Based On Q Learning Biological Sequence Alignment Methods,

Sequence Alignment is one of the common problems and also one of the most important tools in bioinformatics research. As the base of bioinformatics research such as gene identification, molecule evolution and life origin, it compares the similarity of biology data to infer their functions, structures and evolution informations.Reinforcement learning is an unsupervised learning technology, by which the agent can find optimal behavior sequence and perform on-line learning. So reinforcement learning is recognized as an ideal technology to construct intelligent agent. Q-learning algorithm is the most popular reinforcement-learning algorithm, but the algorithm exist some problems. Firstly, Watkins Q-learning algorithm uses greed strategy to select the action. This strategy is a kind of shortsighted strategy. Secondly, when the state space and continuous action space are very large, the learning speed of Q-learning algorithm is very slow. In this thesis, we improve and extend Q-learning algorithm by k step and prior knowledge system. We prove a new a approach sequence alignment base on Q—learning. Give the formula approval of the time complexity and the space complexity, also prove the time complexity and the space complexity reduce to(O(kn))by experiment.The main work is as follows:1. We proved a new approach sequence alignment base on Q—learning (SAQL).Look on finding the optimal Sequence Alignment compare result as the progress of the Agent finding the optimal strategy. The state set is used as the expression of the nucleotide (Amino Acids) and the gaps inset into the alignment aimed to get the optimal Sequence Alignment. Give a score for every action of the Agent as the immediately rewards by gap penalties and score matrix, count all the immediately rewards of every strategy as the expected profits, select the strategy which has the largest expected profits to direct next action. The optimal strategy is the strategy has the largest expected profits, and the optimal sequence alignment is the state set of the optimal strategy. When we calculate the expected profits, we use a k step strategy. We just calculate from now to next step immediately profits as the expected profits. By this the Agent avoids either the shortsightedness of one step strategy of Watkins Q—learning or the speed problem of Q(λ) learning cause of the large number of SAPs(State Action Pairs). The system is designed on Windows XP platform with VC++6.0.2. We also proved a approach SAQL with prior knowledge system.Prior knowledge comes from the successful experiment of Agent learned before. When the Agent begin a new learning, the fuzzy integrated decision-making system supply prior knowledge for it. Finally, the analysis of instances shows that SAQL with prior knowledge system is much better than SAQL.