生物信息学中的NP-完全问题研究综述

唐晓芬

(宁夏大学数学与计算机学院，宁夏 银川 750004)

0 引言

1971年，Stephen A.Cook给出了NP-完全问题的定义［1］。P类问题为多项式界的问题，而NP-完全问题是这样一类问题，如果其中的某个问题存在多项式界的算法，则NP类中的每一个问题都存在一个多项式界算法。NP-完全问题通常被认为是一些人们难以在有限的时间、空间内对问题求出最佳解的问题。目前为止已经证明属于NP-完全问题的有两千多个。

随着新一代基因测序技术广泛用于生物学研究，可获得的基因数据呈指数级增加，如何对这些海量数据进行快速、准确分析并从中找到有用信息是目前值得研究的一个新领域。生物信息学是把统计理论和计算机科学应用到分子生物学上，使用模式识别、数据挖掘和机器学习等原理和技术对海量的基因组测序数据进行高效快速的统计分析，了解相关实验的生物学意义并理解生物学过程的一门学科［2］。在解决基因识别、序列分析及序列比对等问题时需要用到一些先进的信息处理及分析技术，生物信息学中有些涉及计算的问题是NP-完全问题。

1 生物信息学中的NP-完全问题

1.1 构建系统发生树问题

系统发生分析研究物种间的进化关系，系统发生分析的目标是通过比较物种之间的特征，构建一棵系统发生树。通过对相关生物学数据进行分析，然后建模提取特征，进而比较这些特征，由此研究生物进化的历史。系统发生树根据物种之间的遗传历史描述它们的世袭关系。给定一个包含多条序列的物种集合，随着序列条数的增大，系统发生树数目呈指数形式增长。已经证明构建系统发生树是一个NP-完全问题［3］。但是只有一棵树代表了待分析基因或生物体之间的真实进化关系，为了找出这棵反映真实进化关系的树，对每种可能的进化树都进行穷举是不可能的。这就需要研究在适当的时间内，找到代表待分析基因或生物体之间的真实进化关系的系统发生树的最优近似解算法。

1.2 序列多重比对问题

目前，序列多重比对问题涉及的NP-完全问题有以下2个:

(1)利用SP模型寻找最优序列多重比对问题。

为了找到多条序列的共性必须进行序列多重比对。通过序列比对可以研究序列的同源性、序列始祖演化关系以及序列的保守性。同时对一组序列进行比对，能发现多个序列中与结构域和功能相关的保守序列片段。多序列比对对蛋白质二级、三级结构预测及推断各个序列的进化史来说都非常重要。用人工进行多序列比对是一项耗时且困难的工作，由算法或程序进行多重序列比对时，要对所得到的比对结果进行有效评价，以确定其优劣。大多数的多序列比对算法是启发式的并不是全局最优的。SP逐对加和模型是一种多重序列比对的评价模型，即将一个序列多重比对所有列的得分全部加起来，其和作为该多重比对的得分。多重序列比对的最终目标是得到一个得分最高的序列排列，从而分析各序列间的相似性和差异，通常用动态规划算法。SP逐对加和模型不是优化的方法，因为对于K条待比对序列动态规划算法的计算过程相当于依次访问在K维空间组成的超晶格的每个节点，随着待比对序列条数的增加，计算量和所要求的空间成指数增长。已经证明，利用SP模型寻找最优多重序列比对是一个NP-完全问题［4-6］。

(2)多序列的树形比对问题。

多序列树形比对的原理是对K条待比对的序列，建立一棵具有K个叶节点的树，其中每个叶节点对应一条待比对序列。如果将序列也赋予树的内部节点，则可以计算树中每个分支的权值。权值代表对应分支连接的两条序列之间的相似度，所有权值的和就是这多序列树形比对的得分。如何寻找一种树的内部节点序列排列方式，使得树的得分最大就是树形比对要解决的问题。树形比对实际上是多序列组合比对问题，是一个NP-完全问题。

1.3 基因表达数据中寻找最显著双聚类问题

聚类是分析基因表达数据最通用的方法，对基因和条件进行聚类的双聚类方法，可以发现基因子集在条件子集下表现出相似的表达模式，对于揭示仅仅在部分条件下活跃的生物过程是非常有用的，在给定的基因表达数据矩阵中，寻找满足缩放波动一致性约束的最大双聚类簇有助于研究基因的共调控网络，基因缩放模式双聚类是生物学家感兴趣的一种模式。基因缩放模式双聚类簇发现问题是一个NP-完全问题［7-8］

2 NP-完全问题的解决方法

目前对于生物信息学中的NP-完全问题，通常用一些近似的方法来求解具体问题。对于多重序列比对问题，盲目地搜索整个搜索空间的方法效率低下，用人工智能空间搜索策略的剪枝技术可以提高搜索效率，根据具体问题将搜索空间限定在一个较小的区域范围内。目前已有的系统发生树的构建方法根据建树算法在执行过程中采用的搜索方式可分为3类:(1)穷尽搜索法，对每种可能的树都进行搜索并判断是否能表示所分析物种的进化关系;(2)分枝约束法，即根据一定的约束条件将所搜索空间限制在一定范围内，产生可能的树，然后选择最优。这是人工智能技术中的一种空间搜索策略，这种搜索方式不需要搜索整个树空间，可以提高算法效率;(3)启发式方法或经验性方法，即根据先验知识或一定的指导性规则压缩搜索空间，提高计算速度。这种方法能处理大量的分类单元，虽然不能保证所构建的树是最优的，但实际结果往往接近于最优。

目前对于NP-完全问题的解法可总结为以下几种。

(1)只求解规模比较小的问题。

(2)利用动态规划、分枝约束等技术减小搜索空间，加快问题的求解速度。

(3)针对具体问题的特点，根据问题的实际输入，涉及实用求解算法，这样的算法虽然在最坏情况下其时间复杂度是非多项式的，但是算法执行的平均效率和复杂度与多项式的算法相当。

(4)采用近似算法或启发式方法，寻找相应问题比较接近最优解的最优解，或利用常规的求解技术求解。比如，利用神经网络、遗传算法、粒子群优化等计算智能方法。

计算智能作为人工智能的一个分支，是以自适应的机制研究和模拟自然智能并建立模型，以实现对复杂问题的求解。随着技术的进步，在科学研究和工程实践中遇到的问题变得越来越复杂，采用传统的计算方法来解决这些问题面临着计算复杂度高、计算时间长等问题，特别是对于一些NP难问题，传统算法根本无法在可以忍受的时间内求出精确的解。因此，为了在求解时间和求解精度上取得平衡，计算机科学家提出了很多具有启发式特征的计算智能算法。目前已有的计算智能的主要方法有神经网络、遗传算法、免疫算法、模拟退火算法、蚁群算法、粒子群算法、遗传编程等。目前，有学者研究利用计算智能的方法解决生物信息学中的NP-完全问题并取得了比较好的效果［9-14］。

随着计算智能研究的深入和应用的日益广泛，利用计算智能算法解决生物学中NP-完全问题的研究方向为:在研究和改进现有算法的基础上，在各学科不断交叉发展的大背景下，将新的智能模拟算法以及各种智能算法的综合集成用于可进行多目标优化的生物信息学问题，构成一个优势互补、复合协同的综合集成系统。

目前将计算智能方法用于解决生物信息学问题的文献很多，但是它们普遍存在这样的问题，侧重于算法设计，较少提供生物学家易用的程序或工具，对所提出方法的生物学意义验证较少，大多不具实用性。因此，今后将计算智能算法应用于生物信息学领域的研究应该注重针对所研究问题提出的任一解决方法，对该方法的合理性和可靠性进行统计分析，通过多种不同分析方法进行验证，并能开发相应工具或软件，使所提出的算法具有较高的可信度和实际的生物学意义。

3 结束语

如何从海量生物数据中挖掘信息，帮助人们改善其生存环境和提高生活质量，促成了结合数据挖掘和模式识别等理论的新兴交叉科学——生物信息学的发展。目前生物信息学研究的热点包括:海量生物数据的有效分析、整理;基因组组分信息分析与数据处理，揭示生物信息编码系统的规律、演化和关系;利用基因芯片进行全基因组转录分析，在此基础上研究疾病发病机制、疾病分型和识别疾病;通过对蛋白质进行结构和功能分析获取隐含其中的有用生物学信息。这些研究能够为人们理解生命和进化、发现新药物和新疗法提供帮助。在急剧增长的数据面前，如果仅仅依靠传统生物试验方法由人工验证组分信息、确定疾病发生的机理以及测定蛋白质功能结构，完成这些工作所需设备价格昂贵而且非常耗时，在这种情况下急需依靠模式识别、数据挖掘和计算智能等技术建立自动识别方法，以提高试验效率，降低试验代价。

［1］Stephen A Cook.The complexity of theorem-proving procedures［C］//Proceedings of the Third Annual ACM Symposium on Thoery of Computing.1971:151-158.

［2］Hogeweg P，Hesper B.Interactive instruction on population interactions［J］.Comput.Biol.Med，1978，8(4):319-327.

［3］Yue F，Tang J.A divide-and-conquer implementation of three sequence alignment and ancestor inference［C］//Proc.1st IEEE International Conference on Bioinformatics and Biomedicine(BIBM).2007:143-150.

［4］Allocco D J，Kohane I S，Butte A J.Quantifying the relationship between co-expression，co-regulation and gene function［J］.BMC Bioinformatics，2004，5(1):18.

［5］Yang Z.Inference of selection from multiple species alignments［J］.Curr.Opin.Genet.Dev.，2002，12(6):688-694.

［6］Hein J.An algorithm combining DNA and protein alignment［J］.J.Theor.Biol.，1994，167(2):169-174.

［7］Cheng Y，Church G M.Biclustering of expression data［C］//Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology.2000:93-103.

［8］Cano C，Adarve L，López J.et al.Possibilistic approach for biclustering microarray data［J］.Comput Biol.Med.，2007，37(10):1426-1436.

［9］Handl J，Kell D B，Knowles J.Multiobjective optimization in bioinformaties and computational biology［J］.IEEE/ACM Transaetionson Computational Biology and Bioinformaties(TCBB)，2007，4(2):279-292.

［10］Mitra Sushmita.Computational intelligence in bioinformaties［J］.Lecture Notes in Computer Science，2005，3400:134-152.

［11］Queiroz A，Donoghue M，Kim J.Separate versus combined analysis of phylogenetic evidence［J］.Annual Review of E-cology and Systematics，1995，26(1):657-681.

［12］Andries P Engelbrecht.计算智能导论［M］.谭营译.北京:清华大学出版社，2010.

［13］李伍举.计算机辅助分子生物学试验设计与分析［M］.北京:军事医学科技出版社，2009.

［14］［英］杨子恒.计算分子进化［M］.钟扬，张文娟译.上海:复旦大学出版社，2008.