间隙光谱字典及其应用

# 间隙光谱字典及其应用 ## 1 引言 在质谱分析中，传统的肽序列标签生成方法存在一些局限性，如无法为每个光谱选择合适数量的标签，且未为标签赋予严格的概率。间隙光谱字典的出现为解决这些问题提供了新的思路，它可以生成具有概率的传统肽序列标签，并且通过生成代表质量间隙序列的间隙标签，提高基于标签的串联质谱（MS/MS）数据库搜索的过滤效率。 ## 2 方法 ### 2.1 路径字典问题 大多数从头肽测序算法通过分析光谱图中的路径来解释光谱。我们先讨论在任意图中寻找次优路径的问题，然后描述它与在光谱图中寻找路径的关系。 设 $G(V, E, score, probability)$ 是一个有向无环图，其中 $V$ 是顶点集，$E$ 是边集，$score$ 和 $probability$ 是定义在边上的函数。给定图 $G$ 中的一条路径，该路径的得分定义为其边得分之和，路径的概率定义为其边概率之积。 给定一个图 $G$，选定顶点 $s$（源点）和 $t$（汇点），以及一个阈值 $MinScore$，路径字典 $PD(G, MinScore)$ 定义为从 $s$ 到 $t$ 得分超过 $MinScore$ 的所有路径的集合（及其概率）。路径字典问题可以使用标准的寻找次优路径的算法来解决。 - **路径字典问题**：给定一个有向无环图 $G$ 和一个阈值 $MinScore$，构建 $PD(G, MinScore)$。 定义 $p(x)$ 为图 $G$ 中从源点 $s$ 到汇点 $t$ 得分 $x$ 的所有路径的总概率。生成函数 $x \to p(x)$ 可以通过动态规划图中节点 $(t, x)$ 的概率高效计算。$PD(G, MinLength)$ 可以通过动态规划图中的标准回溯来构建。 对于串联质谱（MS/MS）的光谱图，路径字典问题对应于从头肽测序问题，当生成多个（次优）从头重建结果时。通过固定光谱概率阈值 $Threshold$，并选择 $MinScore$ 使得光谱概率不超过 $Threshold$，可以生成光谱字典。然而，这种光谱字典方法对于长肽（15 个氨基酸及以上）和大字典来说并不实用，因此我们引入间隙路径字典问题来解决这个问题。 ### 2.2 间隙路径字典问题 设 $H$ 是图 $G$ 中包含源点 $s$ 和汇点 $t$ 的顶点子集（$H$ 中的顶点称为枢纽）。图 $G$ 中的每条路径都会通过保留原始路径中 $H$ 中的顶点，诱导出 $H$ 中的一条枢纽路径。间隙路径字典 $GPD(G, H, MinScore)$ 定义为 $PD(G, MinScore)$ 中路径诱导的所有枢纽路径的集合（及其概率）。 - **间隙路径字典问题**：给定一个有向无环图 $G$、其顶点的一个子集 $H$ 和一个阈值 $MinScore$，构建间隙路径字典 $GPD(G, H, MinScore)$。 暴力构建 $GPD(G, H, MinScore)$ 的算法对于大的 $PD(G, MinScore)$ 不实用。我们描述了一种高效的算法，无需构建 $PD(G, MinScore)$ 来解决间隙路径字典问题。 给定枢纽 $h$ 和 $h'$，定义 $Path(h, h')$ 为图 $G$ 中 $h$ 和 $h'$ 之间不经过其他枢纽的所有路径的集合。每个路径由其得分和概率表征。定义枢纽图 $G_H$ 为顶点集 $H$ 上的多重图，对于每个 $x \in X(h, h')$，在 $h$ 和 $h'$ 之间存在一条得分 $x$ 且概率为 $Prob(h, h', x)$ 的边。 由于 $G$ 中的枢纽路径由 $G$ 中的路径诱导，$GPD(G, H, MinScore)$ 与 $PD(G_H, MinScore)$ 相同。因此，$G$ 中的间隙路径字典问题本质上是枢纽图 $G_H$ 中的路径字典问题，我们只需计算 $G_H$ 中边的得分和概率即可解决间隙路径字典问题。 #