基于线性自组装的DNA减法模运算

摘要

使用线性自组装方法,提出了两个非负二进制整数减法模运算的DNA算法.对于两个表示为n位的二进制数A与B,算法给出A-B在模2n情况下的运算结果.算法中包含反应被减数与减数大小关系的扩展借位信息,从而在计算前不必对A与B的大小关系进行预分类.结果反应链中包含运算结果、每一步借位信息、参与运算的数值、判断被减数与减数大小的标志位等信息.算法充分利用DNA反应的并行特性,在给定两个被减数集与减数集时,可进行两个集合的减法模运算的并行计算.算法的可行性基于已知的DNA算法实验.算法具有良好的自发反应特性,避免了人工操作随运算数值位数增长的情况,对于计算位数n,在本算法中参与反应的单链库规模为O(n),生物操作复杂度为常数。