Natural comuting丨对存储在DNA中的数据进行并行成对操作：排序、异或、移位和搜索
大家好，今天分享的是2023年9月发表在natural comuting期刊上，被收录在sci中的一篇文献，标题为“Parallel pairwise operations on data stored in DNA:sorting,XOR,shifting,and searching”
1作者介绍
作者是明尼苏达大学电气与计算机工程系的阿纳夫·索兰基，其主要研究方向主要包括：Bioinformatics；Cancer Genomics；DNA computing；
Arnav Solanki
2研究背景
自从上世纪九十年代开始，DNA计算已经显现出来了大规模并行计算的好处，近些年来，人们对利用DNA存储产生了浓厚的兴趣，2019年和2020年通过使用PfAgo和CRISPR-Cas9等编辑酶“切口”DNA来编码数据。同时在2019年，一种将这种形式的数据存储与计算相结合的新范式“SIMD DNA”被提出。
本文的数据操作基于成对运算的SIMD DNA编码系统。关于此编码系统上的操作之前已经实现了三个新的应用，分别是二元冒泡排序、左移操作、并行搜索。同时又实现了一种新的操作异或操作。这四种操作对于DNA计算，分析，设计等都有至关重要的作用！
3研究内容
本篇文章所做研究主要分为两个部分。一部分是基础部分，包括SIMD DNA结构的介绍、使用SIMD范式进行并行分子计算，编码系统的设计以及在此编码系统上实现的特定序列识别位对和重写单元格。另一部分是这篇文章真正要介绍的核心操作部分，即冒泡排序、异或操作、左移操作、搜索算法。
3.1基础部分
3.1.1关于SIMD
SIMD是Single Instruction，Multiple Data（Flynn 1972）的计算机工程首字母缩写词，是一种计算形式，其中多个处理元素同时对多个数据点执行相同的操作。它与更通用的并行计算类别（MIMD，多指令，多数据）形成鲜明对比，其中多个处理元素可以同时对多个数据点执行完全不同的操作。虽然一般的MIMD并行性可能是可取的，但它通常不切实际。电子计算能力的现代进步很大程度上是通过图形处理单元（GPU）等平台扩展SIMD计算来实现的。
SIMD DNA计算基于数据的编码方案。从概念上讲，我们将双链DNA的片段划分为“结构域”，其中每个结构域是一些小指定长度（通常为5至20）的连续核苷酸序列。由几个（通常为5到7个）域组成的序列映射到存储一个二进制位的“单元”。细胞是否存储0或1取决于拓扑变化，特别是缺口的位置，即DNA骨架中的断裂。缺口总是出现在双链复合体的一条链上（在我们的示例中通常是顶部链）；另一个保持不变。
计算由一系列“指令”进行，其中每个指令在细胞上实现DNA链置换反应。指令由添加到解决方案中的单链“指令链”启动。链置换级联完成后，溶液中所有自由漂浮的碎片被冲走，原始链通过磁珠保持和分离。在一系列指令之后，数据将转换为其最终状态。读数可以通过荧光或使用牛津纳米孔装置进行。
计算方法总结为：（1）设计最适合算法的编码结构；（2）在特定位置对数据进行编码，使用酶对相应的靶标进行切口；（3）轻轻地使DNA变性，使相邻缺口之间的片段分离，露出脚趾；（4）执行指令，实现链置换操作；（5）最后，使用荧光或纳米孔读取数据。如图1所示为基于SIMD范式进行的操作步骤。
图1 基于SIMD范式的指令操作流程
3.1.2编码系统设计
本篇文章采用了一种新的编码方案，适用于由对位对的并行操作组成的广泛算法。运行这些算法的一个要求是，编码方案应允许算法读取彼此相邻的位。此规范的代价是某些算法的复杂性更高，即与自定义编码相比，每步的操作更多。
编码方案如图2所示。每个单元格存储一个二进制值（“位”）。每个单元格由7个域组成。为简单起见，我们这里没有指定结构域的实际核苷酸序列。在制备该细胞时，必须在结构域1之前和之后切开顶部DNA链。然后，这股链可以通过变性移位，从而形成暴露的脚趾。在此方案中，域1始终作为脚趾公开。涵盖域2到7。当存储位0时，我们将在域3和4之间的顶部链上切开；存储位1时，我们将在域5和6之间切开。两个相邻单元格有四种可能的配对。每个都将使用不同的域组合进行检测：对于位对（0，0）我们检测域1、2和3；对于位对（0，1）我们仅检测域1；对于位对（1，0）我们检测域6到3，在域7和1处换行；对于位对（1，1），我们检测域6、7和1。
图2 编码系统设计
3.1.2识别位对
我们算法中的一个常见任务是“识别”相邻位对，即识别感兴趣位置的特定单元对。我们将利用域1始终公开的事实来识别这些特定对。图3说明了我们识别字符串11001的方法，它包含所有4个可能的相邻对：00、01、10和11。
识别是通过三条指令执行的。在指令1中，链（67123）被发给所有对位。首先在每对之间结构域1的脚趾处结合。如果前面的位的值为1，则域5和6之间将有一个缺口。通过分支迁移，左侧（即（67）部分）将取代覆盖前位域6和7的原始链。如果以下位的值为0，则域3和4之间将有一个缺口。通过分支迁移，右侧（即（23）部分）将取代覆盖域2和3的原始链。仅当前一位为1且后一位为0时，才会替换这两条线。对于对（1，1），域2和3处于悬垂状态。对于对（0，0），域6和7处于悬垂状态。因为对（0，1）根本不会绑定，因为唯一暴露的脚趾是域1。这就是算法识别对（1，0）的方式。
图3 识别位对
在指令2中，使用互补链（6*7*1*2*3*），拉出附着在对（0，0）和（1，1）上的链。这是通过链上对（0，0）中的开放域2和3以及对（1，1）中的开放域6和7操作完成的。在此指令之后，链仅保留对（1，0）。
在指令3中，同时发出两条指令链：（671）和（123）。这里（6，7，1）将绑定到对（1，1），（1，2，3）将绑定到对（0，0）。它们不会与任何其他对结合，因为唯一暴露的脚趾是结构域1。
结果是相邻的位对（1，1）、（1，0）和（0，0）分别用链标记。对（0，1）在结构域1处用暴露的脚趾标记。这个脚趾可以用链（45671）或链（12345）代替。
3.1.3重写单元格
通过在单元格中跨域2到7暴露脚趾，我们可以用三条指令重写该单元格的内容——因此将1更改为0或0更改为1。这个想法是，由于存在暴露的域，我们可以用覆盖所有这些域的单链替换单元格的内容。然后，我们可以通过暴露的“标签”结构域使用互补链去除覆盖链（如图4）。细胞现在完全暴露在外。我们可以根据我们的编码方案杂交链，将域1留作脚趾并将缺口放置在所需位置，从而向它写入一个新位。
图4 重写单元格
3.2核心操作
3.2.1并行二元冒泡排序
排序在计算机中是一项非常基本的操作，这里我们利用排序进行0和1的权重确定。由于有四种临位情况，所以冒泡排序我们有四种操作，其中我们只对输入临对(10)修改为（01）就可以实现冒泡排序操作。具体操作：①标记（1,0）；②用保护盖覆盖这些对，在这些对中，将位1的域6和7以及位0的域2和3保持打开状态；③通过覆盖域2和3处的相应脚趾来保护这些对的位0；④将这些对中的位1翻转到0；⑤释放保护盖；将这些对中的位0翻转到1。
3.2.2异或操作
这里的异或操作用来检查多个输入位（单元格）中1的数量，和冒泡排序类似，这里的异或操作也包括了四种操作（如图5所示）。
图5 异或操作的四种操作
具体的迭代运算：①确定与上一次迭代的配对相比偏移1个单元格的配对。②检测（1,1）的所有非重叠对并将它们转换为（0,0）。③检测所有（1,0）对并将它们转换为（0,1）。对于此写入过程，对可以重叠。
运行结果：足够次数的迭代之后，链中的所有位都将是0，除了最后一位是不确定的，最后一位存储的是异或操作的结果，如果是1，则为奇数个1，反之则为偶数个1。注意：算法的执行过程要先进行偶数位为临位对碱基的左边碱基，再进行奇数位为临位对碱基的左边碱基进行逐步识别操作。
3.2.3并行左移操作
正常来讲，我们所说的二进制左移即为对应的数值乘以2，二进制右移即为对应的数值除2。这里的并行左移不同，N个二进制位向左移动一个位置，而最低有效位（LSB）保持不变，是属于平行左移。这里的每次左移需要十一条指令。操作分为四个步骤：①将所有位对进行标记，覆盖对（0，0）和（1，1）的立足点；②对于位对（1，0），将位1翻转为0；③对于位对（0，1），将位0翻转到1；④最后，暴露出（0，0）和（1，1）的所有立足点。我们以将11001移至10011的示例进行说明，如图6所示。
图6 并行左移示例
3.2.4并行搜索算法
所谓查找即找出目标序列是否在给定序列中存在，这里的查找我们将目标字符串和给定字符串中的原始字符中两个连续的比特位（单元格）替换为一个符号。然后利用符号进行查找。例子比如：对于A0这一目标字符串，我们可以将其替换为a0、a1、a2、a3，查找字符串为Q=1101，可以表示为Q=a3a1=b1。如图7所示
图7 并行搜索原理
4研究总结
本篇文章对基于SIMD DNA框架内基本并行操作的算法进行了研究和实现。这里的并行性主要分为两个方面①位级并行性：一次指令同时对多个单元格操作；②数据级并行性：相同的指令可以同时用于多个字符串。本文章的创新点体现在对DNA存储信息进行并行计算即实现其中存储信息的快速(增)(删)改查。但也有一定的局限性：①有一定的出错率；②DNA合成仍然非常昂贵。
原文链接
