英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
一个基于密度的重叠蛋白质复合物识别的聚类算法
摘要
背景：识别蛋白质复合物是一项理解细胞中蛋白质作用机制的必要任务。很多计算方法因此被用来识别蛋白质相互作用网络中的蛋白质复合物。关于可以被计算方法用来识别蛋白质复合物的信息，还有蛋白质相互作用网络中图表的拓扑结构，把蛋白质的功能信息考虑在内的方法最近变得很流行。相关的方法实现基于这样的思想：相同蛋白质复合物中的蛋白质可以与相似的功能信息联系在一起。然而，我们在过去的研究中发现对于大多数蛋白质复合物来说它们的蛋白质仅仅在一部分功能上而不是在全部的功能相似。因此，如果把每个功能类别的参数考虑在内的话，蛋白质复合物识别结果的精准性将得到提升。
结果：为了实现这个思想，当我们决定某个蛋白质属于哪个蛋白质复合物的时候，我们首先给每个蛋白质引入了一个参数矢量用来表示每一个功能类别参数。合并蛋白质的功能信息和蛋白质相互作用网络中的图表结构，我们把蛋白质复合物识别问题构想成一个条件最佳化问题，并且我们提出了一个DCAFP的方法来命名它。为了性能评估，我们做了大量的取自酿酒酵母菌和人类物种的蛋白质相互作用网络实验，并把DCAFP方法和目前识别蛋白质复合物最先进的方法进行比较。实验结果显示同时考虑功能参数和密度结构提高了识别蛋白质复合物的表现，DCAFP方法优于其他方法的原因在它的基于f-measure,准确性，最大适配率的评估。而且，大量的实验表明DCAFP方法与其他方法（比如PCIA方法，同样利用了功能信息）比较时能够识别出更多有意义的蛋白质。
结论：根据DCAFP方法极具潜力的表现，把功能参数和密度结构合并使得蛋白质复合物识别结果更精准和更有意义成为可能。
背景:
蛋白质复合物是包含执行不同细胞功能的蛋白质的生物分子。因此，在蛋白质相互作用网络中发现的蛋白质复合物有助于我们理解不同细胞系统中蛋白质的作用。正是因为这个原因，蛋白质复合物识别的问题在过去几十年一直很流行。为了处理它，人们提出了相当多的方法包括基于实验室的方法和计算方法。
基于实验室的方法已经发展到用实验室里的各种实验来识别蛋白质复合物，例如化学交联，亲和纯化，双杂交等方法。虽然很有潜力，但是基于实验室的方法在效率方面却不能令人满意。就拿亲和纯化法来说，识别不同的蛋白质复合物要求用很多使用不同引诱蛋白的实验。而且对于基于实验室的方法来说，能被它们识别的蛋白质复合物通常是不能完成的，因为有些蛋白质复合物在现有的实验设施下可能不会被发现。
为了避免基于实验室方法出现的问题，一些不同的计算方法被提议用来作为识别蛋白质复合物的互补工具。它们大多数都是基于使用各种不同图表的聚类算法。通常来说，为了把PPI网络表示成图表的形式，用图的顶点表示蛋白质，图的边则表示蛋白质之间的相互作用，因此而形成的簇被认为是识别出来的蛋白质复合物。纯粹依赖于蛋白质-蛋白质相互作用网络中的图表的拓扑结构的计算方法通过下列拓扑结构来识别簇:例如密度，k-紧密连接子网和边缘结构。
最近，由于蛋白质的功能信息变得更容易得到，因此提供了一种新的识别蛋白质复合物的方法。对于同样的蛋白质复合物中的蛋白质，它们或许有相似的蛋白质功能信息，所以现在有很多方法都是把蛋白质功能信息考虑在内来识别蛋白质复合物。特别地，Lubovac等人引入了两个可供选择的网络措施，结合了功能信息和拓扑属性来加权蛋白质然后根据数值较高的权值来识别蛋白质复合物；Wang等人根据功能信息的相似性评估了蛋白质相互作用网络的可靠性并提出了一个扩展的聚类算法来检测蛋白质复合物；Zhang等人通过合并功能信息在原有的蛋白质相互作用网络上提出了一种增强的网络；Hu等人基于功能信息的独立性给蛋白质相互作用网络加权，然后应用马尔可夫过程来识别蛋白质复合物；Zhang等人提出了一种通用的模型来结合功能信息和拓扑信息；Wu等人利用了多重资源的生物数据，例如基因本体，基因表现图谱和亲和纯化数据两个蛋白质之间的密切关系，并根据密切关系的数值来识别蛋白质复合物。
很明显，前述的方法通过设计不同的措施来使用蛋白质的功能信息从而从不同角度给蛋白质相互作用网络或者蛋白质加权，比如相似性，独立性，概率分布。虽然很有效，但是这些方法都有一个共同的显著的缺点：它们把所有功能信息合并到一起的同时忽略了单个功能信息的参数。对于功能信息，基因本体工程从蛋白质的不同角度把它描述为三个功能种类：生化进程，分子功能，细胞组成。根据我们之前的研究，我们发现对于大多数蛋白质复合物来说它们的蛋白质仅仅在部分功能上相似而不是在所有的功能上都相似。因此，当决定两个蛋白质是否应该被划分到同一个蛋白质复合物的时候，两个蛋白质之间相似的功能种类应该被优先考虑。由于目前的把功能信息考虑在内的方法并不能分辨这些区别，所以我们认为为了识别蛋白质复合物更为准确，充满潜力的蛋白质功能信息有待被挖掘。
在这点上，如果我们有一个方法通过强调相似的功能种类而忽略不相似的功能种类使得识别蛋白质复合物中的蛋白质成为可能，那么识别蛋白质复合物的表现将会大大提升。
为了这样做，我们提出了一个基于下列两个直观的属性可用来识别蛋白质复合物的DCAFP方法：
- 相同蛋白质复合物中的蛋白质从拓扑结构的角度来讲是紧密连接的。
- 相同蛋白质复合物中的蛋白质从功能信息的角度来讲至少在部分功能上相似。
可以看出第一个属性要求图聚类应该有一个被广泛应用于识别蛋白质复合物的基于密度的拓扑结构，第二个属性是为了强调考虑单个功能种类参数的必要性。
关于DCAFP方法的实现，我们引入了一个可能性矩阵来代表成对的蛋白质被识别为相同的蛋白质复合物的可能性。如果两个蛋白质之间的可能性值很高就说明它们很可能被识别到相同的蛋白质复合物。使用可能性矩阵的另一个好处是可以识别重叠的蛋白质复合物。为了表示形成蛋白质复合物过程中每个功能种类的参数，我们给每个蛋白质分配了一个相应的参数矢量，利用这个参数矢量，当识别对应的蛋白质属于哪个蛋白质复合物的时候，单个功能种类的参数可以定量地显示。根据前述的两个直观的属性，我们构想出了一个条件最佳化问题并基于可能性矩阵和蛋白质的参数矢量来识别蛋白质复合物。这个最佳化问题被命名为DCAFP，DCAFP采用通过反复的步骤使得可能性矩阵和参数矢量最佳化的策略。这个步骤开始与对所有蛋白质的可能性矩阵和参数矢量的随机猜测，然后反复提高聚类的质量知道集收敛。
DCAFP方法的性能已经通过使用取自酿酒酵母菌和人类两个物种的五个蛋白质相互作用网络和三个基因本体的功能种类被评估。大量实验结果不仅显示了DCAFP方法和目前最先进的方法比较时有极具潜力的表现还说明了DCAFP方法有能力识别重叠的蛋白质复合物。
方法
数学准备工作：
为了表示蛋白质相互作用网络，我们使用了一个三元组G={V,E, Lambda;},其中V = {vi} (1 le; i le; nV)表示蛋白质结点，E = { eij}表示蛋白质结点之间的相互作用关系，Lambda; = {Lambda;p, Lambda;f , Lambda;c}表示完整的一套三个功能种类，即生化进程，分子功能，细胞组成。任何一个E中的相互作用关系连接G中的两个蛋白质结点。为了表示G的拓扑结构，我们使用了一个邻接矩阵。对于任意一个功能种类Lambda;p isin; Lambda;,我们定义了一个域作为Lambda;p可能会取到的值的集合。在基因本体数据库中，域dom (Lambda;p)是Lambda;p中的一套基因本体条件。
我们使用了一个可能性矩阵W来表示G中所有成对的蛋白质被分组到相同的簇中的可能性大小。通过W的定义，我们使用了一组介于0到1之间的值来表示两个蛋白质结点被识别到相同的簇中的可能性大小。Wij值越高，则蛋白质结点
vi和vj被分组到相同的簇中的可能性就越大。
为了表示每个功能种类中蛋白质的相似性，我们使用了一组相似性矩阵A = {Ap, Af, Ac}，拿Ap来举例，我们用它来表示生化进程功能Lambda;p的相似性矩阵，ap ij表示就生化进程功能Lambda;p而言，两个蛋白质结点之间的相似性大小。
除了W和A矩阵外，我们还有另外一个矩阵D来表示从拓扑结构的角度来讲两个蛋白质之间的相似性。假设对于结点vi我们有Vi = {vk|eik isin; E}来表示跟vi有相互作用关系的结点，同理对于结点vj我们也有Vj，dij的值表示在vj和Vj都找到的相同蛋白质的百分比。显然，vi和vj之间相互作用的蛋白质越多，dij的值就越大。
为了表示聚类过程中单个功能种类的参数，我们给每个蛋白质赋予了一个功能种类参数矢量，这个矢量表示为rT i=（Rip,Rif,Ric）,在矢量ri中每个元素都是一个非负值并且我们有一个约束条件rip rif ric = 1.利用矢量ri我们能够确定当决定另一个蛋白质结点vj是否应该被分组到和vi同一个簇中的时候多少功能种类应该被优先考虑。换句话说，关于和vi有关系的聚类，如果rip被分配了一个较大的值那么Lambda;p将会起到更重要的作用。为了表示V中所有蛋白质的参数矢量，我们使用了一个参数矩阵R。识别蛋白质复合物的问题也就是识别G中的一组簇。每个C中的簇，它们的蛋白质都是紧密连接的并且在部分功能上相似。自从DCAFP有能力识别重叠的蛋白质复合物，我们可以找到这样的两个簇exist; Cp, Cq isin; C:Cp cap; Cq ne; empty;。
问题构想：
给定T,A,D矩阵，我们的目标是找出合适的W和R矩阵使得识别出来的簇能够满足前述的两个直观属性。跟随这个思想，我们构想了一个最佳化问题：
其中WT = T ∘ W，WD = D ∘ W，||w||^2是W的forbenius范数的平方形式，||R||^2是R的forbenius范数的平方形式，1是一个合适大小的表格矢量，它的每个元素都是1。是一个点乘点的矩阵。
这个最佳化问题就像（1）所描述的那样由三部分组成：聚类质量，正则化和约束条件。为了说明就满足前述的直观属性而言（1）中最佳化问题的合格性，我们给出了一个对（1）的详细分析来使得合格性提升。
为了证明簇识别中的拓扑结构，我们把我们的分析约束在（1）中并把它重新写成如下的形式：
根据D矩阵的定义，我们知道dij的值越高那么两个蛋白质结点vi和vj之间相同的蛋白质就越多。对于第三个蛋白质结点vk，wikwjk表示被分组到和vi、vj相同的簇中的程度，tiktjk用来确保如果vi和vj都在E中被找到的时候，vk有助于值
的生成。不难下结论如果两个蛋白质有很多共同的蛋白质，它们中的大多数很可能被分组到和我们之前提及的两个蛋白质相同的簇中，那么（1）中的值将会被最大化。因此，这个结论在某种程度上确保了相同簇中的蛋白质是紧密连接的。
对于(1)的第二个用处，我们用它来控制聚类过程中的功能信息使得簇是基于功能种类被识别的。为了证明它，我们把（1）重写成下面的形式：
根据（3）和（4），我们拿vi isin; V举个例子来解释为了使得（1）最大化rim和wij是怎么被决定的。在（3）中给定约束条件vi的参数矢量即ri，应该对那些蛋白质之间相似非常频繁的功能种类赋予更多的权值。（4）表明如果两个蛋白质相似程度很高的话那么wij也应该被赋予一个很大的值。总而言之，（3）和（4）允许我们从功能种类的子集中识别簇。
讨论完（1）作为聚类质量合格的措施后，（1）的另外两个方面和W和R各自的正则化有关。对于W，我们用来提高惩罚如果W中的所有元素都移到最大值中的话。则是用来对R中的每个参数矢量正则化。
解决方法：
为了使得W和R能够将（1）最大化，我们采取了可替换的最佳化W和R策略。也就是说，在每次重复过程中，DCAFP首先更新R同时保持W固定，然后用更新过的R来更新W。假设我们现在在第(l 1)个重复过程中，利用和，包含
和的信息便可以展示。
更新R：
为了帮助理解，我们现在使用来表示通过更新R和固定的W来使得最大化的过程。首先，我们构造一系列二次的子问题来接近最大化：
在（5）中，每个子问题都是就ri而言使得最大化。因此，更新R的问题被分成了几个子问题，每个子问题都是为了更新对应的ri作为(1)的部分解。
为了解决，我们使用对偶策略，对偶策略对条件最佳化问题寻求可行的提升方法是有效的。特别的，对于给定的，最佳化的移入应该使得最大化。因此，在一些基于KKT线性控制的代数操作后，可以这样得到：
其中是比ri更好的约束条件。是第(l 1)个重复过程中的约束条件。是的大小。是第（l 1）个重复过程中不活跃的约束条件。
在（6）中，因此，关于的子问题，我们能够在中包含（6）。如果不等于0，那么的更新将会不正常:。然而，可能会造成一些不活跃的约束条件被违反如果我们只考虑和ri有关的活跃的约束条件。为了避免这个问题，我们需要找到最大化的步骤，这样我们才能在的方向上更新。特别的，
控制条件必须被满足，这样才不会违反约束条件。对于，我们可以这样定义：
其中1是和（1）中ri等价的约束条件。现在可以通过（8）被决定。
一旦把（8）应用到R中所有的参数矢量，那么就被包含了。
更新W:
和更新R相似，我们使用来表示通过固定R就W而言的条件最佳化问题。观察（1）我们发现每个元素都是独立的，W中任意两个元素也是没有约束条件的。因此我们可以这样接近:
其中在（10）中被给出。
在（10）中的问题被转换成一系列的子问题。事实上，正如（10）所显示的那样，子问题是最大化问题的一项必要措施。因为，（10）是一个关于wij的凹函数。容易下结论当如果没有约束条件0 le;wij le; 1就会得到（10）的最大值。假设是满足等式的Wij的值，我们有
。因此，在第（l 1）个重复过程中，当考虑了约束条件子问题的解在（11）中被
全文共21538字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13994]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
