龙源期刊网 http://www.qikan.com.cn
图论在生物学方面的有效应用
作者：孙 琪
来源：《电脑知识与技术·学术交流》2008年第05期
摘要：本文介绍了最大连通子图、最大团和完美匹配等图论知识在生物学尤其在研究蛋白质结构研究方面的应用。在现实生活中， 这具有十分重要的意义和广阔的应用。 关键词：最大连通子图；最大团；完美匹配
中图分类号：TP18；O157 文献标识码：A文章编号：1009-3044(2008)05-00ppp-0c 1 前言
图论是组合数学和计算机理论科学的重要学科之一，也是数学和理论计算机中近年来发展最快的学科之一，其主要应用除了在计算机领域外，还广泛的应用于其它学科，例如经济、生物、数学等等。这里我们主要介绍其在生物学中的有趣应用。
2 图论在生物学方面即研究蛋白质结构预测方面的有效应用
我们知道蛋白质结构预测问题就是如何从蛋白质的氨基酸序列出发预测它的功能、构象折叠等问题。这是一个人类破译生命奥秘的重大问题。这个问题一旦得到解决，科学家们就可以最终阐明遗传信息传递的全过程，从而大大有助于了解蛋白质空间结构与其功能之间的关系。近年来，“图”的概念已被应用于蛋白质结构预测的相关研究之中，如：寻找图的最大连通子图研究蛋白质的自折叠问题、图的连接矩阵的特征矢量分析研究蛋白质的活性位点和配体结合位点的问题、图的完美匹配方法预测二硫键的问题等，取得了一定的成果，本文主要对这些图论方法在蛋白质结构预测中取得的一些新的研究进展作以综述。 2.1 最大连通子图
若有图G（V，E），如果有另一图G’（V’，E’），且V’和E’分别是V和E的子集，且E’中的一条边e’（vi，vj）必须与E中的一条边e（vi，vj）相对应，称G’为G的子图。如果图G’的任意两个顶点之间均是连通的，则称G’是一个连通图。若G是不连通图，它的每个连通的部分G’称为G的一个连通子图。
龙源期刊网 http://www.qikan.com.cn
1997年我国学者彭征宇在‘蛋白质中的自折叠单元’一文中，把一个蛋白质的结构用一个数学上的“图”来表示。图上的每一个顶点表示一个二级结构，而每一条边则表示两个二级结构单元之间的相互作用。那么，这些相互作用的强度将通过每两个二级结构单元间有多少对重原子（指碳、氮、氧等）之间的距离在0.5nm（5埃）之内来决定。两个相邻的或平行的二级结构单元之间的相互作用将大于距离较远的或垂直的二级结构之间的相互作用。然后，简化“图”：只保留对于每一个顶点最强的相互作用及超过这个最大值60%的那些相互作用。对每一个顶点来说，它的邻点对它的相互作用密度定义为它与邻点的相互作用除以代表这个顶点的二级结构的长度。保留相互作用密度超过整个图中最强相互作用密度20%的那一部分，其余的相互作用所对应的那些边将被舍弃。这样所得到的图将是非对称的，即对某一顶点来说，它的邻点对它来说可能是重要的，而同时这个顶点对它的邻点来说却是不重要的，因为它的邻点与其他顶点有更强的相互作用。在经过简化的图中，寻找具有自折叠能力的部分相当于寻找这个图的最大连通子图。
他们通过对牛胰蛋白酶抑制蛋白（PDB5PTI 58amino acidsresidues）和嗜热菌蛋白酶（thermolysin）用图论的方法进行了预测，这个预测与实验结果相符合。他们认为，总体上，这种方法对于预测已知结构蛋白中的自折叠单元有大约70%的成功率。与以前的方法相比较，他们的方法的最大优点是所预测的自折叠单元不需要由连续的氨基酸序列所组成。强调了理论与实验的比较，以及尽可能少地引入能量参数等优势。 2.2 最大团
若简单图G（V，E）的子图S是完全图，即满足其任意两个顶点之间均有且只有一条边相连，则称S是G的团。1998年Samudrala R和Moult J，把一个蛋白质的同源模建中的3D结构预测问题成功地转换为一个图论中的寻找最大团的问题。
在同源模建中，主链构像的大部分可以从一个或多个相关的母板结构获得，仅仅是那些被认为与母板结构有明显不同的主链和侧链构像，才用于转换为寻找最大团的问题。
在氨基酸序列中的一个残基，它的每一个可能的构象代表图中的一个顶点。边连接两个顶点（残基）。顶点和边根据一些安排好的标准赋权。一旦这个图被构造出来，所有的团中的极大团就可用Bron & Kerbosch提出的CF（clique-finding）算法找到。那些权值最好的团被认为与天然结构最相似。
一个残基的每个可能的构象在图中表示一个顶点。顶点的权根据侧链的原子与局部主链原子之间的相互作用程度赋权。要一直考虑到在代表顶点的残基位置两侧的任意四个残基的主链的原子和这个残基的主链原子，被用来计算权值。边连接一对顶点，边的权根据代表顶点的残基之间的相互作用程度赋权。对于空间彼此碰撞的顶点之间不连边同一残基具有不同的构象之间不连边。顶点和边的权值通过一个全原子距离条件概率赋权。简单地说，要求的概率通过在一个265个高清晰的X-射线测出的非同源蛋白质结构数据库中，计算原子类型对的距离的频数而得到。计算公式如下：
龙源期刊网 http://www.qikan.com.cn
给定一个具有n个顶点和m个边的团，对应构像的分值用这个团上面的边和顶点的和来表示：
他们的方法与传统的方法相比，不合适的构像被提前舍弃，具有搜索适应性构像速度快的优点，团的方法克服了连续能量函数搜索方法遇到能量势垒和过早掉入局部能量最小的 势阱里的缺点。他们用这种图论的方法对同源蛋白质进行了预测取得了令人鼓舞的结果，同时证明，这种方法应用于同源模建的loop区域的预测具有较好的前景。 2.3 完美匹配
在无向图G（V，E）中，对边集E的任一子集MAE，如果M中任意两条边都不相邻，则称M为图G的一个匹配。若G的每个顶点都是M饱和点，则称M是G的完美匹配。2001年Piero Fariselli和Rita Casadio把预测二硫键连接问题等价为一个寻找图的最大权的完美匹配问题。
在蛋白质结构预测中，一个主要的问题是在富含半胱氨酸的蛋白质中准确确定二硫键的位置。在组成蛋白质的20个氨基酸中，半胱氨酸惟一的具有一种属性，即它们之间可以形成二硫键有助于蛋白质三维结构的稳定。它使多肽链的两个不同的区域之间能够紧密地靠拢起来。在蛋白质折叠预测中，确定二硫键可以大大地减少搜索构像空间。氨基酸序列中每一个半胱氨酸残基代表图中的一个顶点V，边E连接一对顶点（Cys-Cys），边依据相应规定赋权W，构成一个赋权的完全图G，应用Edmonds-Gabow的算法，找到G中具有
最大权的完美匹配。则这个完美匹配对应正确的二硫键的连接方式。权值的获得考虑一级结构中半胱氨酸残基位置前后的各5个残基赋权，数据来源于PDB蛋白质结构数据库中的726个高分辨率蛋白质中二硫键的连接模式的统计结果。他们利用这种方法对蛋白质折叠中的二硫键连接进行了预测研究，结果说明二硫键的形成与其序列模式有这重要的联系，通过研究半胱氨酸残基在序列中局部环境因素，可以预测二硫键的结构。对于具有4个二硫键的蛋白质结构，这种方法的预测正确率高于随机预测的17倍。
3 总结以及其他研究（other researches）
图论在生物学方面的有效应用
