论文摘要
序列比对是生物信息学中最常见的问题之一,也是一种重要的生物信息处理技术。它通过对生物序列数据进相似性比较,来发现生物序列中的功能、结构和进化等信息,是基因识别、分子进化、生命起源等生物信息学研究的基础。强化学习是一种无监督的机器学习技术,能够利用不确定的环境奖赏发现最优的行为序列,实现动态环境下的在线学习,因此被广泛用于Agent的智能决策。目前主流的强化学习算法是Q学习算法,它是在强化学习基础之上发展起来的一种新的机器学习方法,因其自身特点已经成为人工智能领域的研究热点。但Q学习本身存在一些问题。首先,Watkins提出的Q学习原型,采用贪婪策略选择当前动作,这种策略是一种一步策略,使得当前动作对于将来影响估计不足;其次,当状态空间很大时,Q学习算法的存储空间比较大而且学习速度较慢。本文针对生物序列比对中的具体问题,对Q学习算法进行了一些扩充和改进,提出一种基于Q学习的生物序列比对方法。本文的主要工作为:1.提出一种基于Q学习的生物序列比对方法用Q学习的方法解决序列排列的问题的思想:把寻找两条序列最佳排列的过程视为一个Agent自主学习,寻找最有策略的过程。在该过程中把待比对序列和为了获得最佳排列而插入序列的空格视为一组状态,把直达下一个核苷酸（氨基酸）还是插入空格看作是将要采取的行动,采用空位罚分或者打分矩阵计作为评价函数,计算Agent每一次采取不同行动的立即受益,计算每种策略的累积预期收益,选择累积预期收益最大的策略指导下一步的行动,将获得最大收益的序列作为最终的最佳序列排列。在计算累积预期收益的过程中引入多步Q学习机制,选择当前状态直至将来k步的最优策略指导下一步的行动。这样既避免了Watkins Q学习采用贪婪策略选择当前最优策略的一步策略短视问题,又避免了Q（λ）学习的状态行动对数量过于庞大,引起的收敛速度慢的问题。给出了时间复杂度和空间复杂度的公式证明,通过实验证明该方法有效地降低了时间复杂度和空间复杂度（O（kn））。利用VC++6.0在Windows XP平台上开发完成SAQL模型。取得了令人满意的效果。2.基于Q学习的生物序列比对方法的基础之上提出一种具有先验知识的基于Q学习的生物序列比对方法。先验知识建立于Agent以往成功的学习经验基础之上,当Agent每次进行新的学习任务时,由模糊综合决策专家系统为其提供先验知识。通过实验比较发现具有先验知识的SAQL较单纯的SAQL有改善。