Comparison对比

Two old approaches — and why they fall short两条旧路——以及它们为何行不通

Before Siyuan Code, DNA-storage encodings fell into two families: manually designed codes and filtering-based codes. Both work, yet neither reaches DNA's density promise. Here is why.在思源码之前,DNA 存储编码分为两大家族:手工设计与筛选式。两者都能用,但都够不到 DNA 的密度承诺。下面讲清楚为什么。

1 · Manually designed codes1 · 手工设计的编码

Manually designed codes use hand-decided rules to avoid unsuitable sequences. Their advantage is that these rules are easy to implement and fast to execute. The price is paid in density, for three reasons.

手工设计的编码用人工决定的规则去避开不可用序列。其优点在于这些规则易于实现、执行快速。代价则是密度,原因有三。

They exclude suitable sequences by accident它们会误伤可用序列

The fixed rules usually preclude suitable sequences by accident, so the code cannot leverage all sequences suitable for DNA storage, resulting in low encoding density. A fixed rule is a blunt instrument: it keeps out the bad strands, but it also keeps out a large share of the good ones.

固定规则通常会误伤可用序列,因此无法利用所有适合 DNA 存储的序列,导致编码密度低下。固定规则是把钝刀:它挡掉了坏链,却也挡掉了一大批好链。

Examples — Church et al. map A/C→0 and G/T→1, storing only 1 bit/nt; Goldman et al.'s rotation code converts binary to ternary and is over-conservative, excluding many available patterns; Grass et al. use only 47 length-3 sequences to represent 46 integers.

例 — Church 等人把 A/C 映射为 0、G/T 映射为 1,只能存 1 bit/nt;Goldman 等人的旋转码把二进制转成三进制,过于保守,排除了许多可用模式;Grass 等人只用 47 条长度 3 的序列 表示 46 个整数。

Radical rules let unsuitable sequences in激进规则又会放进不可用序列

The mirror failure: the fixed rules sometimes include some unsuitable sequences by accident when the rules are based on radical strategies, which then demands more error correction and again lowers the density.

与之相反的另一面:当规则基于激进策略时,固定规则有时会误放进一些不可用序列,于是需要 更强的纠错,密度同样被拉低。

They cannot adapt它们无法随需调整

It is difficult, if not impossible, for these methods to adjust customized rules — for example, the allowed homopolymer length. Every new synthesis or sequencing technology, and every artificial nucleotide, means redesigning by hand. In short, all manually designed methods end up denser-worse than the filtering state of the art, Yin-yang code.

对这类方法来说,调整自定义规则——例如允许的同聚物长度——即使不是不可能,也非常困难。每一次新的合成/测序技术、每一种人工核苷酸,都意味着重新人工设计。简而言之,所有手工设计方法在密度上都比不过筛选式的代表——阴阳码。

Segment junctions go unguarded分段衔接处无人防护

Manual codes are built segment by segment, each segment enumerating its own allowed patterns. But suitability depends on adjacent segments, not on each segment alone — a forbidden pattern can straddle the boundary between two segments, where neither segment's own rules catch it. Longer segments would reduce the number of boundaries, yet enumerating a long segment is impractical, so the segments stay short and the boundaries stay frequent.

手工设计是分段进行的,每一段各自枚举允许的模式。但可用与否取决于相邻的两段、而非每一段自身——被禁模式可以横跨两段之间的边界,而每段自己的规则都发现不了。加长分段能减少边界数量,但枚举过长的分段又不现实,于是段长只能保持较短,边界也就一直很密集。

2 · Filtering-based codes2 · 筛选式编码

Filtering codecs take the opposite route: they randomly generate sequences and remove the unsuitable ones until the remaining ones can be decoded. Their virtue is flexibility — updating the filtering rules is usually trivial. Their weakness is that the filter and the random generation are in tension, and the tension only worsens as constraints tighten.

筛选式编码走相反的路:它们随机生成序列,再把不可用的去掉,直到剩下的足以解码。其优点是灵活——更新过滤规则通常很简单。缺点是过滤与随机生成之间存在张力,而且约束越严、张力越大。

Strict rules → endless generate-and-reject严格规则 → 无尽的生成—拒绝

Strict filtering rules reduce the single-strand error rate, but more sequences must be generated and fed to the filter, which significantly prolongs the encoding time. We measured this directly: at strand length 200, forbidding 3-homopolymers with GC(40–60%) takes an average of 3.8 × 10²² retries per strand; with the milder GC(20–80%) it is still 5.5 × 10⁶. In the worst case, nearly all the generated sequences are unsuitable and the regenerating becomes an endless loop or fails.

严格的过滤规则能降低单链错误率,但需要生成并送入过滤器的序列更多,从而显著拉长编码时间。我们的测量显示:链长 200、禁 3-同聚物且 GC(40–60%) 时,平均每条链要 3.8 × 10²² 次重试;即便放宽到 GC(20–80%),也仍需 5.5 × 10⁶ 次。最坏情况下,几乎所有生成的序列都不可用,重新生成要么陷入死循环、要么直接失败。

Retry count of filtering methods grows exponentially
Supplementary Fig.The retry count of filtering-based methods grows roughly exponentially with strand length and constraint strictness.筛选法的重试次数随链长与约束严格程度近似指数增长。

Random seeds run out — instability随机种子会耗尽 —— 不稳定

Regenerating needs distinct random seeds. Our analysis gives the minimal seed length: under GC(20–80%) with 3-homopolymers forbidden, a strand needs more than 22.4 bases of seed to avoid repeats — yet Fountain code uses only 16, so it can fail to encode. Yin-yang code stores its seed implicitly in its two indices, so it cannot be lengthened at all. And Aeon code can be driven into an infinite loop by the tiny motif set {AA, AT, AC, AG}. The extra seed also costs density: up to 11–36% of a strand.

重新生成需要不重复的随机种子。我们的分析给出所需的最短种子长度:在 GC(20–80%)、禁 3-同聚物下,一条链需要 超过 22.4 个碱基 的种子才能避免重复——而喷泉码只用 16 个,于是可能编码失败。阴阳码把种子隐含在两个索引里,根本无法加长。而 Aeon 码会被极小的基序集 {AA, AT, AC, AG} 逼入死循环。多余的种子还要吃掉密度:最高可达链长的 11–36%。

Minimal random seed length
Supplementary Fig.Minimal random-seed length required to avoid repeats.为避免重复所需的最短随机种子长度。
Random seed overhead
Supplementary Fig.The density overhead of the random seed can reach 11–36%.随机种子的密度开销可达 11–36%。

Loose rules → high error → high copy number宽松规则 → 高错误率 → 高拷贝数

To escape the retry loop, filtering methods loosen the rules. But loose filtering incurs high single-strand error rates, so more copies of a sequence need to be synthesized, lowering the density, and a higher sequencing depth is required. That is why Yin-yang code, with its looser 5-homopolymer rule, still needs a sequencing depth of ≥ 100× to cope with single-strand errors.

为了逃出重试循环,筛选法只能放宽规则。但宽松过滤会带来高单链错误率,于是需要合成更多拷贝,密度随之降低,还要求更高的测序深度。这正是阴阳码虽然把规则放宽到 5-同聚物、却仍需 ≥ 100× 测序深度来应付单链错误的原因。

In short, filtering-based codes find it difficult to achieve high density with fast execution time, and they are unstable and high in single-strand error rates.

简而言之,筛法难以在快速执行的同时达到高密度,而且这类方法不稳定、单链错误率高。

3 · What Siyuan Code does instead3 · 思源码的不同做法

Siyuan Code abandons both compromises. Instead of hand-picking a few safe patterns, or randomly generating and discarding, it enumerates every suitable sequence and maps them one-to-one onto binary data. Nothing is excluded by accident, nothing is left unused, and nothing is randomly regenerated.

思源码同时放弃了两者的妥协。它不是人工挑选少数安全模式,也不是随机生成后丢弃,而是枚举每一条可用序列,并把它们一一对应地映射到二进制数据上。没有误伤、没有闲置、也没有随机重来。

01

Every suitable strand is used用尽每条可用链

The one-to-one mapping keeps all suitable sequences and excludes only the unsuitable ones — density reaches the theoretical limit by construction.

一对一映射保留全部可用序列、只排除不可用的——密度在构造上就达到理论极限。

02

Deterministic, no retries确定性,无重试

Encoding and decoding are pure counting — no randomness, no random seed, no generate-and-reject loop. It never fails, however strict the rules.

编码与解码是纯计数——无随机、无随机种子、无生成—拒绝循环。无论规则多严格,都永不失败。

03

Strict rules become affordable用得起最严的规则

Because the cost does not depend on constraint strictness, Siyuan Code can afford the strictest rules — lowering the single-strand error, the copy number, and finally raising the physical density to 41 EB/g.

因为成本不随约束严格程度而变,思源码用得起最严的规则——从而降低单链错误率、降低拷贝数,最终把物理密度推到 41 EB/g。

04

Exponential becomes linear从指数降到线性

Whole-strand coding was long assumed to require enumerating all 4n strands — exponential in length. Siyuan Code replaces the enumeration with dynamic-programming counting: the counting table is built in polynomial time, and each strand then encodes and decodes in time linear in its length. In practice that is 435× faster than Yin-yang code and 63× faster than Fountain code — about 1 MB/s on commodity hardware.

整链编码长期被认为需要枚举全部 4n 条链——随链长指数增长。思源码用动态规划计数取代了枚举:计数表在多项式时间内建成,之后每条链的编码与解码都只需与链长成线性的时间。实测比阴阳码快 435×、比喷泉码快 63×——约 1 MB/s(普通硬件)。

Continue reading:继续阅读: the mathematics →数学原理 → · the plain-language walkthrough →通俗讲解 →