基于图的基因组数据分析表示与工具

### 基于图的基因组数据分析表示与工具 #### 1. DNA 分析问题 在基因组研究中，有几个关键的 DNA 分析问题，这些问题构成了后续研究的基础。 - **基因组组装**：测序机器（包括基于桑格法和采用下一代测序技术的机器）会产生大量重叠的读段，这些读段是所需染色体碱基序列的子序列。桑格法产生的读段相对较长，而下一代测序技术产生的读段则短得多，甚至可达 50bp。此外，下一代测序机器会同时从 DNA 的两条链产生读段，这增加了将每个读段归到正确链的复杂性。为了重建整个基因组，第一步是将所有读段组合成一个单一序列，这个过程称为组装。组装问题有两种变体： - **从头组装**：当首次对某一物种的 DNA 进行测序时，只能使用从读段中获得的信息。 - **重测序**：有同一物种的参考基因组可用，用于指导测序算法的选择。重测序的一个子任务是将读段与一个或多个参考基因组进行匹配，这称为映射。许多从头组装和重测序方案都基于某种图表示。 - **序列比对**：给定两个序列，序列比对是找到它们位置之间的对应关系，以最小化消除两个序列之间差异所需的编辑操作数量的过程。将其推广到多个序列则称为多序列比对（MSA）。虽然存在精确比对算法（如 Smith 和 Waterman 算法），但其复杂度为 O(NM)（N 和 M 是两个序列的长度），因此不适用于大型基因组数据。可以通过对查询或目标序列集进行索引来找到次优解，以有效地获得精确匹配的模式。基于此原理的著名比对算法有 FASTA 和 BLAST。在最近的方法中，特别是对于 MSA 问题，基于图的数据结构（如 De Bruijn 图和 Cactus 图）已被成功应用。 - **变异检测和泛基因组分析**：同一物种的个体群体，其基因组存在细微差异。变异检测是确定每个个体相对于参考基因组的变异集的过程。由于相关项目的推动，基于各种原理的变异检测算法得到了发展。对整个群体（泛基因组）的有效表示是进行更复杂分析的起点，这些分析涉及群体或整个物种，形成了泛基因组学的领域。最近的一些方法提倡使用图来表示一组基因组。 #### 2. 基于图的 DNA 序列表示 为了解决上述 DNA 分析问题，有多种基于图的表示方法。 - **重叠图**：定义重叠图的起点是一组片段 S = {s1, ..., sn}，每个片段包含通过读段获得的一串核苷酸。这些片段的长度通常不同。给定两个片段 s 和 t，最大适当重叠 ov(s, t) 定义为最长的字符串 y，使得 s = x|y 且 t = y|z，其中 | 是字符串连接运算符，x 和 y 必须是非空字符串。可以定义一个容错版本以考虑少量读取错误，该函数可以使用动态规划轻松计算。重叠图是一个有向图 G = (V, E)，有 n 个节点 v1, ..., vn ∈ V，每个节点用一个片段 l(vi) = si 标记。两个节点 vi 和 vj 之间有边 eij ∈ E 当且仅当 |ov(si, sj)| > τ，其中 τ 是一个适当定义的阈值，边标记为 l(eij) = k。重叠图曾用于最早的基于图的测序方法之一，即重叠 - 布局 - 共识（OLC）方法，它是采用桑格测序法项目的标准测序算法。在 OLC 中，测序假设是通过寻找重叠图中的最大哈密顿路径生成的，但哈密顿路径问题是 NP 难问题，因此需要使用启发式算法来在可接受的时间内找到解决方案。 - **字符串图**：重叠图适用于第一代测序仪的信息表示，但在下一代测序方法中有一些问题。首先，下一代测序仪从 DNA 的两条链获取样本，每个片段必须被视为与其反向互补序列等效。其次，片段长度较短，对于重复序列的表示存在问题。字符串图由 Myers 在 2005 年引入，试图修改重叠图以解决这些问题。在字符串图中，每个片段有两个节点，代表片段的端点。节点通过有向边连接，边与核苷酸序列相关联，边也可以反向遍历，此时代表反向互补序列。片段之间的重叠由连接其端点的额外边表示。每条边还关联有一个多重性信息，通过对每个片段观察频率的分析与序列重复的概率模型比较在预处理步骤中推断得出。字符串图可以明确表示从下一代测序仪获得的所有信息，组装通过寻找图中修改形式的欧拉路径来完成，该问题可以在多项式时间内解决。此外，字符串图的每个路径都是读段连贯的，而其他类型的图（如 De Bruijn 图）缺乏此属性，需要额外的计算步骤来过滤掉不连贯的路径。 - **De Bruijn 图**：De Bruijn 图最初是为解决在给定字母表上找到包含所有长度为 k 的可能子字符串的最短字符串这一数学问题而引入的。由于该问题与测序问题有相似之处，其修改版本在 20 世纪 90 年代末被引入用于 DNA 数据。De Bruijn 图基于 k - 元组，即读段的长度为 k 的子字符串。将读段