受限稠密子图及其在基因注释图中的应用

# 受限稠密子图及其在基因注释图中的应用 ## 1 引言 生物知识越来越多地用图来表示，如蛋白质相互作用、代谢途径、基因调控和基因注释等。寻找图中的高密度区域在理论和实践上都具有重要意义。密度是衡量子图连通性的一个定量指标，定义为子图中诱导边的数量与顶点数量的比值。尽管子图的数量是指数级的，但可以在多项式时间内找到最大密度的子图。相比之下，寻找具有所有可能边的最大规模子图的最大团问题是 NP 难的，甚至难以获得任何非平凡的近似解。寻找具有额外大小约束的稠密子图也是 NP 难的，但它们比最大团问题更容易近似。此外，仅检测团可能会有一定的局限性，因为一些缺少几条边的有趣子图会被忽略。 我们将稠密子图问题应用于在基因注释图中寻找复杂模式的任务，该图使用受控词汇表（CV）或本体中的术语来表示基因的注释。为了增加子图的生物学意义，我们通过定义节点对之间的距离度量 \(d_H\)，来倾向于包含在本体结构中有意义关系的节点对。目标是返回子图中顶点满足距离阈值的稠密子图。 我们引入了一种新的稠密子图问题变体，即距离受限稠密子图问题。给定一个图 \(G = (V, E)\) 以及定义在顶点对 \(u, v \in V\) 上的距离度量 \(d_H\)，目标是返回一个最大密度子图 \(S \subseteq V(G)\)，使得在 \(S\) 中，任何顶点对根据 \(d_H\) 的距离都在阈值 \(\tau\) 之内。 此外，研究人员可能对包含预定义节点的模式感兴趣，我们将其称为子集最大密度问题。只找到一个稠密子图可能不够，因为研究人员可能希望找到许多复杂的注释模式。因此，我们还将解决具有距离/子集限制的所有最大和接近最大密度子图的问题。 在计算生物学中，有很多与检测稠密子图密切相关的工作。大多数论文集中在蛋白质 - 蛋白质相互作用网络上，目标是对网络进行聚类以检测紧密连接的分子模块，这些模块可能识别蛋白质家族和分子复合物，甚至识别缺失的相互作用和注释。Newman 的工作研究了代谢和调控网络中的社区检测，社区的特点是内部连接紧密而外部连接稀疏。许多这些社区检测工作可以从距离受限稠密子图问题及其扩展的应用中受益。 一些工作考虑使用聚类系数来衡量每个节点邻域的密度，它定义为邻居之间的边数与最大可能边数的比值。因此，另一种密度度量方法是计算整个子图的聚类系数，但这种方法往往会找到非常小的子图，效果不佳。 ### 1.1 基因注释数据 关于基因的知识被捕获在公共可用的文献资源中，如 PubMed 和 PubMed Central，通用资源如 Entrez Gene，以及更有针对性的模式生物或特定领域的集合，如拟南芥信息资源（TAIR）。为了提高互操作性，各个社区创建了许多本体，如基因本体（GO）、植物本体（PO）和统一医学语言系统（UMLS）。资源中的数据条目通常用这些本体中的概念或受控词汇表（CV）术语进行注释，形成了丰富的注释知识网络。 我们关注 TAIR，科学家通常可以访问一个提供 TAIR 基因丰富概要的页面，然后通过链接访问基因型和表型注释数据、出版物、生物体特定数据、表达序列标签（ESTs）、途径数据等。TAIR 中的注释与反映注释背后方法的解释或证据代码相关联。虽然 TAIR 是一个有价值且访问量很大的门户，推动了科学研究的进展，但它也要求科学家花费大量时间手动点击网页和跟随链接，以创建用于模式发现的注释知识子集。科学家经常使用电子表格等简单工具来维护这个子集。 越来越需要更复杂的工具来帮助科学家整合、分析和可视化这些知识。例如，LSLink 系统可以用于指定一个协议，以创建一个超链接数据记录及其注释的背景 LSLink 数据集。该协议从每个 TAIR 基因开始跟随超链接，并整合相应的 GO 注释、PO 注释以及支持注释的 PubMed 出版物。 考虑基因 GA3OX1 和一个简单的模式，由 GO CV 术语“赤霉素介导的信号传导”和 PO CV 术语“萌发”组成，这是有意义的，因为 GA3OX1 调节幼苗生长。虽然这些简单模式有点有趣，但为了捕获生物学知识，科学家会对找到更复杂的模式感兴趣。对于像 CRY1 这样有许多注释的基因，识别单个基因注释中的复杂模式可能并不容易，因为科学家必须考虑许多注释对和许多 CV 术语组。然而，真正的挑战更加困难。虽然一组 GO 和 PO 术语注释单个基因的模式可能对应于一个有意义的生物学现象，但这可能不是一个有趣的发现，因为它只注释了一个基因，而且知识可能是已知的。一个真正有趣的未知知识发现通常需要科学家解决更大的挑战，即找到一组注释多个基因的 PO 术语和 GO 术语的模式。识别一组尚未相关的基因的共现模式可以导致一个有趣的发现，从而产生可操作的假设，例如进行实验来验证该模式。 另一个挑战是，形成模式的 GO 和 PO 术语不是独立的，它们存在于一个（分层）本体结构中。在层次结构中彼此更接近的受控词汇表（CV）术语在意义上可能更相关。例如，“对赤霉素刺激的反应”和“赤霉素介导的信号传导”这两个术语比“对红光的反应”和“赤霉素生物合成过程”这对术语更相关。包含第一对术语的复杂模式比包含第二对术语的复杂模式更有可能有意义。在本体图中，最短路径距离较小的两个节点被认为比结构中距离较远的一对节点更相关，因此更具生物学意义。 ### 1.2 基因注释图和密度概念 我们可以将问题形式化如下：给定两个本体，GO 和 PO，以及一组基因 \(G\)，每个基因与这两个本体中的一些 CV 术语子集相关联。换句话说，每个基因都与一组 GO 和 PO 节点相关联，