前    言

随着人类基因组计划的实施和科技的发展，生物学数据呈爆炸式增长，这些海量的生物学数据必须通过生物信息学手段进行收集、分析和整理后，才能成为有用的信息。而如何有效分析和处理这些大型序列数据(即序列分析)成为生物信息学的首要任务。序列比对是生物序列分析的主要方法，也是生物信息学中挑战性的问题之一。序列比对在序列装配、序列注释、基因和蛋白质的结构和功能预测以及系统发育和进化分析等方面均有广泛应用，因此对它的研究一直以来都是热点。

进化算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，主要包括遗传算法(genetic algorithm，GA)、遗传规划(genetic programming，GP)、进化策略(evolutionary strategies，ES)、进化规划(evolutionary programming，EP)、粒子群优化(particle swarm optimization，PSO)算法以及近年出现的量子粒子群优化(quantum- behaved particle swarm optimization，QPSO)算法，它们通过一系列的进化算子和进化方程，寻找问题的最优解。本书把上述的进化算法及其改进的进化算法，结合数学模型，用于解决生物多序列比对问题。

全书正文各章节结构如下图所示，共分为“多序列比对基础篇”“多序列比对模拟篇”和“多序列比对参数篇”三个模块。

“多序列比对基础篇”(第1章～第3章)介绍生物多序列比对的基础知识，包括多序列比对的基本概念、原理、方法、常用数据库、常用工具和应用等内容，并介绍进化算法和最优化理论的基础知识，以及遗传算法、粒子群优化算法和量子粒子群优化算法的优化过程及收敛性分析，为进行多序列比对的模拟提供理论基础。

“多序列比对模拟篇”(第4章～第7章)是本书的核心部分，主要内容概括如下：

(1) 应用基本遗传算法及其改进的遗传算法进行多序列比对。基本遗传算法(GA)是通过对进化过程中的种群反复进行选择、交叉、变异操作来模拟自然界中种群的演变过程，直到满足一定性能要求才结束计算，它本身的结构决定了它可以用在多序列比对上。遗传算法可以有效地解决生物多序列比对问题，但是遗传算法高度依赖于初始种群，好的初始种群方可以得到好的结果。为提高计算效率，提高比对质量，可从遗传算法最关键的组成部分入手，通过优化初始种群的质量，达到改进算法的目的。另外，又针对遗传算法最基本的交叉算子，设计了保优和选择混合的交叉操作后处理方法cross4to2。该方法不但服从保优原则，而且又再一次经过选择操作的精英保留过程，使得最优秀的个体进入下一代。这种处理将算法的整体搜索能力和局部搜索能力大大提高。通过与经典CLUSTAL算法的比较，验证了该算法的有效性。

(2) 使用二进制的PSO算法和二进制的QPSO算法进行多序列的比对。为了避免算法的早熟，在算法中还加入了变异算子。首先对群体中的个体进行编码，然后根据目标函数值(通常为序列的得分函数)找出空位的最优位置，使序列比对的结果最优，确定序列的相似性以至于同源性。

(3) 使用QPSO算法和改进的QPSO算法，结合隐马尔可夫模型(HMM)进行多序列的比对。这主要涉及两个过程：优化过程和比对过程。优化过程主要研究剖面HMM模型参数的训练过程，获得较优模型。前面已经提及现有的训练算法通常会陷入局部最优，因此研究全局优化算法对模型进行训练极其重要。用并行的群体智能优化算法优化剖面HMM时，优化的主要对象是转移概率和符号发出概率，优化对象的编码方式以及参数的个数将会影响比对的速度，优化过程中算法的全局收敛性将会影响到比对的准确度。比对过程主要研究比对算法的实现过程，获得比对结果。当使用HMM进行多序列比对时，每条序列从开始到结束通过这些状态穿越模型，在这些待比对序列中进行空位字符“－”的插入和删除操作，得到一个多序列比对结果的矩阵。但应确保在比对结果中有尽可能多的列由相同的非空字符组成，同时在由不同字符组成的列中某一个或某几个非空字符的数目尽可能多，以便发现不同序列之间的相似部分，进而推断它们在功能和结构上的相似性。

(4) 多序列比对的并行计算。随着计算机科学技术在第三代测序技术以及基因组拼接技术方面的不断发展，生物信息领域获得了越来越多的长基因组序列数据，长序列比对成为急需解决的问题。传统的算法对内存空间的庞大需求以及漫长的运行时间已经无法满足对这种大规模数据的处理，因此长序列比对的并行计算成为研究的一个热点问题。通常的并行模式有：基于“分而治之”策略，结合并行计算的长序列首尾分段并行比对算法；基于“粗细粒度”的并行数据并行算法。

多序列比对是生物信息学的一个重要研究内容，比对结果高度依赖于目标函数和比对工具的参数设置，包括空位罚分(GOP和GEP)以及替换矩阵。“多序列比对参数篇”(第8章)主要做了两方面的工作：

(1) 研究SP(sum-of-pair)目标函数，提出确定各参数最优值的理论依据，给出替换矩阵判断公式和最佳空位罚分取值公式，结合待测序列信息得出与之相符的一组最优参数，从而得到更好的比对结果。通过与精度较高的多序列比对工具MAFFT、CLUSTALW的比较，结合BAliBASE2.0数据库进行实例验证，结果表明，根据公式得出的参数可以得到比默认参数更优的比对结果，而且本书公式优化了多序列比对结果，具有可行性和高效性。

(2) 基于BAliBASE3.0数据库，应用MAFFT工具(MAFFT-7.220- WIN64 version)进行多序列比对，得出替换矩阵和空位罚分的最优参数组合，从而得到更好的比对结果。实验结果表明，通过与MAFFT (MAFFT-7.220-WIN64 version)、CLUSTALW (CLUSTALW-2.1-WIN)的默认参数比较，根据本研究得出的最优参数组合可以得到比默认参数更优的比对结果，而且研究结果给出的最优参数组合优化了多序列比对结果。

本书是由多人编撰完成的，编写分工如下：第5章、第6章和附录I～J由龙海侠编撰完成，共计9万字；第4章、第8章和附录A～H由李满枝编撰完成，共计9万字；第1章、第7章由王洪涛编撰完成，共计8.5万字；第2章和第3章由付海艳编撰完成，共计8.5万字。全书由龙海侠和李满枝统稿和修改。本书的出版获海南师范大学学术著作出版资助项目、海南省自然科学基金项目(20151003，614235)、国家自然科学基金(71461008)、海南师范大学数学与统计学院“计算数学”重点学科和信息科学技术学院“计算机科学与技术”一级学科的资助，特此表示感谢。

本书可作为生物信息学、计算生物学、计算机和计算数学等专业本科生或研究生的教材或学习参考书，也可作为相关研究人员的研究参考书。由于我们的专业知识与工作背景的限制，书中还有很多错误或不足之处，敬请希望读者批评指正。

龙海侠  李满枝

2017年1月于海南师范大学