Skip to main content

Genome

DNA sequence​

简短回答：
DNA 测序本质上读取的是单链 DNA。虽然我们提取的基因组 DNA 是双链的，但在测序前必须经过变性（denaturation），解开成单链，然后测序仪才能逐碱基地读取序列。

为什么是单链测序？​

DNA 双链之间通过氢键配对（A-T、C-G）。如果保持双链状态，碱基被配对“锁住”，测序化学反应或物理信号无法直接识别每个位置的碱基。因此，必须把双链分开，以单链为模板进行读取。

主流测序技术中的具体情况​

技术测序对象说明
Sanger 测序单链模板双链 DNA 变性后，引物结合到单链模板上，进行延伸反应。
Illumina（二代）单链模板双链 DNA 片段化、加接头后，变性成单链，附着到 flow cell 上，桥式扩增成簇。测序时每个簇都是单链模板，通过合成法读取。
PacBio SMRT单链模板构建 SMRTbell 结构（双链两端加发夹接头），但聚合酶读取的是其中的单链模板。
Oxford Nanopore单链 DNA双链 DNA 被解链，单链穿过纳米孔，通过电流变化识别碱基。也有研究尝试直接读取双链，但主流仍是单链。

常见误解澄清​

  • “双链测序” 这个说法通常不准确。如果指“同时测两条链”，那是在某些应用中对同一区域分别测正链和负链，以相互验证或提高准确性，但每次读取的仍然是单链。
  • 在基因组组装中，我们最终得到的是双链序列信息，因为测序得到一条链的序列后，根据碱基互补配对规则，可以推导出另一条链的序列。

总结​

DNA 测序是单链测序。
双链 DNA 必须先变性成单链，测序仪才能读取序列。测序结果可以还原出双链信息，但读取过程本身针对的是单链模板。

contig​

contig（常译为“重叠群”或“连续序列”）是基因组组装中的基本单位：把一批相互重叠的测序 reads 拼接起来，得到一段连续的 DNA 一致序列。它代表组装结果中一段“连续、没有组装间隙”的序列。

contig 的主要特征​

  1. 连续性
    contig 通常由 reads 的重叠关系拼接而成，内部不包含组装 gap。它不同于 scaffold：scaffold 是把多个 contig 用 gap（未知序列，常表示为 N）连接起来的更长结构。

  2. 有方向性
    DNA 是双链，contig 在图中通常作为有向节点处理，有正、负方向。在 GFA 等格式中，节点方向常用 + / - 表示。

  3. 长度不一
    contig 长度可以从几百 bp 到几 Mbp，取决于测序深度、重复序列、组装算法和基因组复杂度。常用 N50、L50、总长等指标评估组装连续性。

  4. 序列内容与质量不确定
    contig 由测序 reads 拼接，可能包含测序错误、未确定碱基 N、重复区塌缩或嵌合错误。它的序列是连续的，但不一定完全正确。

  5. 在图结构中的角色
    在组装图、scaffolding 图或 GFA 图中，contig 通常作为节点/segment。节点之间的边表示重叠、配对关系或连接；gap 表示两个 contig 之间已知有间隔但序列未知。
    在 GfaViz 论文中，scaffolding 图的 contig 用浅绿色多边形表示，由黑色边连接，gap 用绿色或红色虚线表示正、负长度。

  6. 可被分组和分类
    在宏基因组分析中，contig 可以通过 binning 按基因组来源分类。GFA 2 允许用无序组描述 bins，GfaViz 中就用彩色轮廓表示 contig 属于不同 bin。
    在变异图中，contig 或节点可组成不同路径，表示不同等位基因或变异组合。

  7. 在组装层级中的位置
    典型组装层级为：
    reads → contigs → scaffolds → chromosomes
    contig 是较可靠的连续片段，但它在染色体上的顺序、方向和位置可能仍未知；scaffold 则进一步确定 contig 的顺序和方向，但中间留有 gap。

简言之，contig 是“拼出来的一段连续序列”，是组装图、scaffolding 图、宏基因组分箱图和变异图中常见的节点单位。它的核心特征是：连续、有方向、长度不一、可能存在错误，并且可通过边、gap 或分组关系与其他 contig 连接。

在序列图里说 contig “作为有向节点处理，有正、负方向”，并不是说节点本身像有向边那样有箭头，而是说：同一个 contig 在被边、路径或比对引用时，可以有两种方向状态：正向 $+$ 和反向 $-$。

1. 正方向：按存储的序列方向​

每个 contig 在 FASTA/GFA 文件里都存了一条序列，例如：

>contigA
ATCG...

这条序列的书写方向就是它的正方向。通常约定为 DNA 的 5′→3′5'\to 3' 方向。也就是说，contigA+ 表示“按照文件里写的从第一个碱基到最后一个碱基来读”。

2. 负方向：反向互补​

contigA- 不是另一条独立的序列，而是同一条双链 DNA 的反向互补序列。
例如存储序列是：

ATCG

那么：

  • 正方向：ATCG
  • 负方向：反向 GCTA，再互补 CGAT

所以 contigA- 实际读作 CGAT。它对应的是双链中另一条链的 5′→3′5'\to 3' 方向。

3. 为什么需要正负方向？​

因为 DNA 是双链。两个 contig 连接时，它们可能以四种相对方向相连：

A+ 连 B+
A+ 连 B-
A- 连 B+
A- 连 B-

如果不记录方向，就不知道该如何拼接序列，也不知道重叠区域该按哪条链计算。例如 GFA 的 L 行会写成：

L  A  +  B  -  10M

这表示：A 的正方向末端与 B 的负方向末端有 10 bp 重叠。拼接时，B 需要先反向互补。

路径也是这样。GFA 的 P 行可能写成：

P  path1  A+,B-,C+

它表示路径依次经过：A 正向、B 反向、C 正向。对应的序列是：

seq(A) + revcomp(seq(B)) + seq(C)

4. 正负不是绝对“正链/负链”​

要注意：这里的 ++ 和 −- 是相对于该 contig 自身存储序列的，不是相对于某个全局参考基因组的正链/负链。不同 contig 的“正方向”可能来自不同物理链，除非有一个参考序列来统一定向。

5. 在 GfaViz 中的体现​

GfaViz 支持 GFA 2 的 fragment lines。补充材料 Fig. S2 中，reads 比对到 contig 时：

  • 绿色线表示 read 来自 forward strand
  • 红色线表示 read 来自 reverse strand

这就是方向在可视化中的直观表现：同一个 contig 作为参考，read 可以正方向匹配，也可以负方向匹配。

所以，contig 的“正负方向”可以理解为：
正方向 = 文件里存储的序列方向；负方向 = 该序列的反向互补方向。
在图中，节点本身定义一次，但在边和路径中被引用时，必须带上 ++ 或 −-，以说明它是以哪条链、哪个方向参与连接。

Ⅰ. SeGraM​

1. Genetic variations​

Genetic variations between two individuals are observed by comparing the differences between their two genomes. These differences, such as single-nucleotide polymorphisms (i.e., SNPs) , insertions and deletions (i.e., indels), and structural variations (i.e., SVs) , lead to genetic diversity between populations and within communities.

2. DP-based algorithm​

A DP-based algorithm operates on a table, where each column of the table corresponds to a reference character, and each row of the table corresponds to a query read character. Each cell of the table can be interpreted as the cost of a partial alignment between the subsequences of the reference and of the query read that have been traversed so far.

3. Software Tool Analysis​

  • end-to-end execution time
  • cache miss rate
  • random main memory accesses
  • scalability analysis

Ⅱ. GenDP​

1. Scoring methods​

  • Linear Gap Penalty（线性空位罚分） 这是最早、最简单的打分模型，其核心思想是空位罚分与空位长度成正比。
  • Affine Gap Penalty（仿射空位罚分） 仿射模型是对线性模型的改进，它区分了“打开空位”和“延伸空位”的代价，更符合生物学中插入/缺失事件的发生规律。(identifying short insertions and deletions in pairwise alignments.)
  • Convex Gap Penalty（凸空位罚分） 凸模型认为，随着空位长度的增加，每个额外空位字符的罚分应该递减，这能更好地模拟生物学中的“滑链错配”等现象。

这三种打分方式是一个逐步演进的过程，旨在用更复杂的数学模型去逼近真实的生物学过程。从线性到仿射再到凸模型，对空位代价的刻画越来越精细，但计算复杂度也随之增加。其中，仿射模型因其在精度和效率上的良好平衡，成为了目前绝大多数比对工具的默认选择。

In sequence alignment, a scoring system is generally used for evaluating and optimizing the quality of different alignments.

2. Systolic array​

The systolic array helps exploit the wavefront parallelism in the DP table and provides better spatial locality for DP dataflow.

The accelerator: provide flexible interconnections between processing elements (PEs) in the systolic array.

3. Common Genomics pipelines​

2 important analysis pipeline:

1). referemce-guided assembly

  • Read alignment can be abstracted to an approximate string matching problem, where dynamic programming algorithms are used to estimate the pairwise similarity between the read and the reference sequence.
  • After the alignment, small variants (mutations) still exist. A Hidden Markov Model (HMM) or machine learning model is then applied to detect such mutations, in a step known as

2). "de novo" assembly (without using a reference genome)

  • Reads with overlapping regions can be chained to build an overlap graph and are then further extended into larger contiguous regions.
  • Assembly errors are corrected in a graph-based dynamic programming polishing step.

other analysis pipelines:

  • metagenomics classification
    • aligns input microbial reads to a reference pan-genome (consisting of different species).
    • estimates the proportion of different microbes in the sample.

Ⅲ. TALCO​

1. Long read alignment​

With improved cost, accuracy, and throughput of long-read genome sequencing technologies, coupled with the widespread availability of complete whole-genome assemblies for a large number of species and individual organisms, the ability to align long genomic sequences has gained significant importance in recent years. In genomic medicine, it helped achieve the fastest genetic diagnosis of newborn patients. It has been used to better characterize structural variations and complex regions in the human genome. Long alignments are also essential in comparative genomics to gain new insights into the evolution of gene families and other genomic features by comparing whole genomes of different species.

2. tiling-based hardware accelerators​

Pairwise sequence alignment is one of the most fundamental and computationally intensive steps in genome analysis. The high memory demands of long alignments create significant obstacles to hardware acceleration.

Tiling-based hardware accelerators have made remarkable strides in accelerating sequence alignment.

Based on Amdahl's law, there is diminishing return to accelerate this step further over the three to four orders of magnitude speedup already achievable with tiling-based accelerators. Instead, for wider adoption, future hardware accelerators should commensurately focus on improving and guaranteeing alignment quality.

The first accelerator based on the WFA-Adapt algorithm

3. banded sequence alignment algorithms​

widely-used banded sequence alignment algorithms, X-Drop and WFA-Adapt.

4. accuracy importance​

the genomic diagnosis of patients: accuracy is a critical concern.

5. scoring strategy​

Alignments can be scored in many different ways with the typical objective of maximizing the number of matching characters in the alignment while minimizing the number of mismatches and gaps that need to be inserted in each sequence to achieve the alignment.

1). minimizing the Levenshtein distance: each mismatch or gap in the alignment increments the distance by one.

2). Gotoh's affine gap strategy: assigns different scores for the opening and extension of gaps, providing a more accurate model for how gaps appear in biological sequences.

6. 启发式算法特征​

启发式算法（heuristic algorithm） 的核心特征是：

用经验规则或近似策略，在可接受的时间内找到一个“足够好”的解，但不保证一定是最优解，也不保证对所有输入都成立。

下面从几个方面展开。

1. 主要特征​

① 不保证最优性​

这是最根本的特征。
启发式算法可能找到最优解，也可能找到次优解，甚至在某些输入下表现很差。
它通常没有严格的数学证明来保证结果质量。

② 以效率换质量​

精确算法（如完整动态规划）能保证最优，但时间和内存可能无法接受。
启发式算法主动牺牲一部分质量，换取：

  • 更低的计算复杂度；
  • 更小的内存占用；
  • 更好的并行性；
  • 更短的运行时间。
③ 依赖问题特定的经验规则​

启发式规则通常来自对问题结构的观察。
例如：

  • “最优路径不会偏离主对角线太远” → banding；
  • “分数落后太多的格子可以丢掉” → X-Drop；
  • “外侧对角线落后太多就剪掉” → WFA-Adapt；
  • “边界最高分格子最可能接上最优路径” → GACT 贪心。

这些规则不是严格推导出来的，而是基于经验或直觉。

④ 通常有可调参数​

启发式算法往往有参数控制“激进程度”：

  • X-Drop 的 XX；
  • WFA-Adapt 的 WdiffW_{diff}；
  • GACT 的 TT 和 OO。

参数越大，越安全但越慢；参数越小，越快但越可能丢最优。

⑤ 对输入敏感​

启发式算法的表现可能随输入变化很大：

  • 序列相似时，banding 很安全，速度极快；
  • 序列差异大、错误率高时，剪枝可能丢掉真正的最优路径，质量下降。

精确算法通常没有这种不稳定性。

⑥ 实现相对简单，易于结合精确算法​

启发式常作为精确算法的“外围”优化：

  • 先用启发式缩小搜索空间；
  • 再在缩小的空间内用精确 DP 计算。

例如 banding 就是先剪枝，再在带内做 DP。

⑦ 可能没有误差界限​

近似算法（approximation algorithm）通常有理论保证，比如“结果不超过最优解的 2 倍”。
启发式算法通常没有这种保证，甚至无法给出误差上界。

2. 与精确算法、近似算法的对比​

类型是否保证最优是否有误差界限典型用途
精确算法是无误差小规模问题、质量关键场景
近似算法否有理论保证NP 难问题，需要质量保证
启发式算法否通常没有大规模问题，追求速度/内存

3. 在 TALCO 论文中的体现​

论文里提到的多种技术都是启发式的：

  • X-Drop：按分数落后阈值剪枝，不保证最优；
  • WFA-Adapt：丢弃落后对角线，不保证最优；
  • GACT / GACT-X：贪心选择 tile 边界点，不保证最优；
  • Scrooge：固定 tile 和 banding 参数，也是启发式。

它们共同的特点是：

能大幅加速，但不能保证与不剪枝/不 tiling 的完整算法结果一致。

TALCO 则不同：

  • TALCO 本身不是启发式；
  • 它在 banding 约束下，利用 traceback 收敛，保证 tiling 后结果与完整 banded 算法等价；
  • 所以论文强调 TALCO 解决了“启发式 tiling 导致质量下降”的问题。

4. 启发式算法的优缺点​

优点：

  • 速度快，内存省；
  • 能处理精确算法无法处理的大规模问题；
  • 实现灵活，容易调参；
  • 常能给出实际可用的好解。

缺点：

  • 不保证最优；
  • 质量不稳定，对输入和参数敏感；
  • 难以理论分析；
  • 在关键应用（如临床诊断）中可能不可接受。

5. 一句话总结​

启发式算法就是用经验规则换取效率的算法：它不保证最优，但通常能在合理时间内给出足够好的解。X-Drop、WFA-Adapt、GACT 都是典型的启发式；TALCO 的目标则是在 banding 约束下消除这种启发式带来的质量不确定性。