基于多目标优化的进化算法研究

陈慧琴　燕斌　程涛　李生

摘要：自21世纪初，人类基因组序列图谱公开发表后，生命科学的研究中心已经从基因组学（Genomics）转变为蛋白质组学（Proteomics）。在生物信息学（Bioinformatics）领域，从蛋白质的一维氨基酸序列中预测蛋白质的三维结构及功能，已经成为该领域最重要、最活跃的课题之一。蛋白质结构与功能的研究已有相当长的历史，由于其复杂性，对其结构与功能的预测不论是基础理论还是方法方面难度均比较大。为了进一步提高蛋白质结构及功能的预测方法的可理解，揭示蛋白质结构与功能的深层次对应关系，从多目标优化角度，将该问题转化为多目标问题求解，研究基于多目标优化的蛋白质结构及功能预测的智能算法。

关键词：多目标优化；蛋白质结构及功能预测；进化算法

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）13-0171-02

1990年10月1日，美国国会正式批准并启动了人类历史上规模最大的科研工程“人类基因组计划”（Human Genome Project）。2001年2月，人类基因组序列图谱公开发表，这意味着后基因时代的到来，随后生命科学（life science）的研究重心从基因组学（Genomics）转变为蛋白质组学（Proteomics），及在大规模水平上研究蛋白质的特征，包括蛋白质的表达水平，翻译后的修饰，蛋白与蛋白相互作用等。生物信息学（Bioinformatics）作为生命科学的一个重要科学分支，它是以计算机为工具对生物信息进行储存、检索和分析的科学。具体而言，它是把基因组DNA序列信息分析作为源头，在获得蛋白质编码区的信息后进行蛋白质空间结构模拟和预测，然后依据特定蛋白质的功能进行必要的药物设计。其中，从蛋白质的一维氨基酸序列中预测蛋白质的三维结构及功能，已经成为该领域最重要、最活跃的课题之一。

蛋白质结构及功能预测问题的研究，对揭示蛋白质的表达规律和生物功能提供新的辅助手段，对解释遗传病及传染疾病的生理机制、制备高效安全的生物药剂等复杂的现实应用问题亦具有很高的理论价值和指导意义。如果弄清楚蛋白质的一级结构是如何决定其三级结构这个基本问题，将会使人们更系统和完整地理解具有生物活性蛋白质的传递全过程，使中心法则[2]得到更加完整的阐明，从而对生命过程中的各个现象有进一步的深刻认识，最终推动生命科学的快速发展。

蛋白质结构复杂，种类千变万化，虽然蛋白质结构及功能预测的研究已经取得了一定的成果，对于简单的蛋白质预测已经达到较高的水平，但是在实际较复杂的蛋白质预测上的应用还有很大的一段距离。需要解决的关键技术以及面临的困难还有很多，仍然有一些重要的理论和应用问题尚待解决。

为了进一步研究蛋白质结构及功能预测的研究，提高计算方法的有效性及可理解性，揭示蛋白质天然结构的生理机制，从多目标优化角度，同时结合进化算法，将其与多目标优化结合起来，研究基于多目标优化的进化算法，提高搜索效能从而为系统的研究蛋白质结构及功能提供了一定的理论基础和实验平台。

1 蛋白质结构及功能预测的研究分析

1.1 蛋白质结构及功能预测的现状分析

蛋白质结构复杂，种类千变万化，虽然蛋白质结构及功能预测的研究已经取得了一定的成果，对于简单的蛋白质预测已经达到较高的水平，但是在实际较复杂的蛋白质预测上的应用还有很大的一段距离。需要解决的关键技术以及面临的困难还有很多，仍然有一些重要的理论和应用问题尚待解决。

1）理想的能量函数并不存在。根据C.B. Anfinsen的观点，蛋白质的活性结构像对应于体系能量最小的状态，在一定条件可以认为是能量最小的状态。该函数是一个重要的评价函数，用以区分天然结构和错误结构。在实际应用中，蛋白质机构复杂，可变参数过多，理想的能量函数并不存在。目前用于蛋白质机构预测的能量函数，不论是统计意义上的还是物理意义上的，都是在一定条件下的拟合，正确程度并不高。同时考虑到模型的复杂性，能量函数多忽略溶剂、氢键、疏水性等因素这对正确预测蛋白质结构及功能带来不利的影响。

2）二级机构预测准确度低。一般的预测方法，考虑到减少计算的复杂性，蛋白质的三级结构预测是根据二级结构的预测的结果、蛋白质的结构类型和折叠类型预测的结果以及空间结构的立体化学性质，搭建出最后的蛋白质空间结构。而二级结构预测基本是以总结已知蛋白质结构规律的基础上而建立的，总体来说准确度不超过65%，这已经成为蛋白质结构及功能预测的一个较严重的制约条件。

3）构象空间巨大。典型的蛋白质含有几百个氨基酸、上千个原子。所有可能的序列到空间结构的映射数目，随氨基酸残基个数而成指数级增长，即使使用简化后的contact maps模型或torsion angles模型，也是一个天文数字。使用常规的搜索算法，计算量特别大，搜索效率低。目前许多隐藏在蛋白质序列里的信息未被发掘和充分利用，即使使用智能算法如遗传算法、模拟退火、神经网络算法等，也造成了实际应用受到一些制约，导致计算效率和鲁棒性低下。

因此，要提高智能算法在解决蛋白质结构及功能预测问题时的效能，需要充分提高和创新智能算法在搜索机理上理论基础，继续挖掘隐含信息，构造和创建新的计算模型，开发出能解决实际应用问题的更加鲁棒和有效的工具。

1.2 蛋白质结构预测方法分析

目前蛋白质结构预测方法可以分为三大类：1）基于知识的比较建模法。这一方法主要指同源结构预测，根据同源结构中保守的部分搭建出未知蛋白质的结构骨架，在20世纪90年代由Blundell等人提出。我国学者丁达夫在同源建模方面有过较深入的研究，开发过PMODELINE蛋白质建模系统。2）反向折叠法。原理基于把未知蛋白质的序列和已知的这种结构进行匹配，找出一种或几种匹配最好的结构作为未知蛋白质的预测结构。1991年Bowie 使用一种称为三维剖面（3D-Profile）的方法，根据侧链的埋藏程度、极性原子覆盖率进行打分匹配搜索，并取得了较好的结果。同时期的Jones则开发出了到目前为止仍有较高研究活力的线串法（threading），通过先建立折叠子数据库，然后匹配搜索打分选取最合适的折叠结构。目前反向折叠法已经比较成熟，具有了一定的实际运用价值。3）从头预测法。其目标是从蛋白质的一维结构序列直接预测三级结构，是最理想的方法。目前这个方法主要受两方面的困扰。一是难以找到一个能严格区分蛋白质的天然构象和非天然的构象的能量函数，二是缺少一种有效的全局优化算法。目前在这种方法大类里，一种称为片段组装（fragment assembly）取得较大的成功，其原理是旋凿已知蛋白质结构数据库里的相似片段进行组装。David Baker 研究组开发出基于贝叶斯打分函数的ROSETTA系统是这一方法的典型代表。目前，美国密西根大学的Yang Zhang教授开发出的I-TASSER （Iterative Threading ASSEmbly Refinement）方法代表着从头预测方法的最高水平，其主要原理也是片段组装，在片段选择和组装上有了重大改进。由此可见，在蛋白质结构预测方面，尽管当前的研究比较活跃，已经取得了令人瞩目的成果，但是在面对实际蛋白质时，仍然显得理论和方法的欠缺。不过随着使用更高速的计算机、更有效的算法，解决这个问题是可能的。

1.3 蛋白质功能预测分析

蛋白质功能预测也是当今生物信息学的一个研究重点，是后基因时代最具挑战性的问题之一。所预测的蛋白质功能主要指疏水性、基因调节、对生化反应的催化性。 最流行的方法是基于氨基酸序列， 因为序列是一个蛋白质最基本，最易获得的信息。BLAST使用近似序列比对算法，通过测量目标序列和数据库已知之间的相似之处发现同源关系预测功能。然而，一些研究表明，序列同源性并和功能不总是相关的。另外，直接根据结构预测功能也是一种方法，但是这种方法过于依赖结构预测，描述也过于复杂，常常作为一种辅助手段。近些年，在 high-throughput 生物技术领域，产生了大量的类似基因表达和蛋白质的相互作用的生物数据，这些数据作可以作为蛋白质功能预测的一个数据分析平台，研究人员已经在这方面做了大量的研究工作。由此可见，蛋白质功能预测正逐渐形成一个科研热点，由于蛋白质功能的复杂性以及预测方法的发展和变化，蛋白质功能预测的研究存在很多机遇和挑战。一方面，其理论基础还不够完善，尤其是怎样识别一个蛋白质功能还需要较多研究工作。另一方面，新的预测方法的效能还有待提高，特别如何实现不同算法模型之间的融合、协同计算问题。

2 多目标优化问题研究分析

多目标优化在具体问题上的应用研究也是当今学术界的一个研究方向和趋势。多目标优化在实际问题上的应用，最早是被Knowles等人在处理如何将一个单目标问题转换成多目标优化问题时被重新提出来的。一般认为，更多的目标函数数量意味着更困难的优化问题，但也意味着更有效的优化过程可以实现，目前多目标优化已经运用到很多应用领域。如旅行商问题、车间调度问题、装箱问题、最短路径和最小生成树问题，并且取得了显著的实验结果。在生物信息学领域，多目标优化也有较多应用，Thomas 成功将其应用到基因调控网络。在蛋白质结构及功能预测上，也有较多应用。Becerra 将之用于蛋白质的从头预测问题。将多目标优化与进化计算结合起来，用两个目标函数进行了蛋白质的三级结构预测。Olson 将多目标与随机搜索算法结合起来，在平衡局部和全局搜索上做了改进，取得了较好的预测结果。尽管目前的多目标优化在具体问题上的研究已经取得巨大成功，并逐步发展成为研究热点和技术前沿之一，将多目标优化应用到蛋白质结构及功能预测这个问题上，有研究价值和意义。

3结束语

综上所述，目前基于多目标优化的蛋白质结构及功能预测的研究基本还处于前期探索阶段，最终形成成熟的理论和实际应用，还需要更多具有创新性的基础研究，以及大量细致的完善工作。在国内外对蛋白质结构及功能研究十分重视的背景下，适时启动基于多目标优化的蛋白质结构及功能预测的研究是必要且迫切的。因此，通过本项目，将建立起面向各种类蛋白质的结构及功能预测平台，为进一步系统地研究蛋白质结构及功能，揭示蛋白质折叠的生理机制，优化多目标计算模型，同时为生物技术、药物设计等应用领域提供理论研究基础。

参考文献：

[1] Luscombe N M， Greenbaum D， Gerstein M. What is bioinformatics？ An introduction and overview[J]. Yearbook of Medical Informatics， 2001（1）： 83-99.

[2] Anfinsen CB ."Principles that govern the folding of protein chains[J]. Science， 1973， 181 （4096）： 223-230.

[3] Becerra D， Sandoval A， Restrepo-Montoya D， et al. A parallel multi-objective ab initio approach for protein structure prediction[C]//Bioinformatics and Biomedicine （BIBM）， 2010 IEEE International Conference on. IEEE， 2010： 137-141.

[4] Cutello V， Narzisi G， Nicosia G. A multi-objective evolutionary approach to the protein structure prediction problem[J]. Journal of The Royal Society Interface， 2006， 3（6）： 139-151.

[5] Olson B， Shehu A. Multi-objective stochastic search for sampling local minima in the protein energy surface[C]//Proceedings of the International Conference on Bioinformatics， Computational Biology and Biomedical Informatics. ACM， 2013： 430.