（运筹学与控制论专业论文）代数运算的dna实现.pdf

摘要 1 9 9 6 年，f r a n k 发表在s c i e n c e 上的“d n a 加法”一文开创了利用d n a 解决 数值运算的先河，同时，文中提出的“全列举与自装配”成为d n a 代数运算工作 的基础思想。在这一基础思想的指导下，又先后出现了其他解决代数运算的算法 模式。 电子计算机只是用串行思路解决问题，d n a 计算机( 现在还只是处于理论研 究中) 则是以并行的思路解决问题。我们的思想就是以并行代替串行，先从理论 上来验证d n a 计算机的优越性。 本文是对应用d n a 计算机解决代数运算中的减法、除法问题进行了研究，主 要给出了三种算法分别解决减法、除法。减法的d n a 算法理论主要是来源于串 行思路中的算法，它是将每一位上的两个减数对的所有可能进行全列举，同时考 虑每一位上的两种借位信息，使得运算进行自动选择，一步即可褥到最终结果的 算法；除法中一位数除多位数的算法还是从我们平时所进行的串行运算中得到启 发而设计的算法；而除法的多位计算思路则来源于史丰收速算法。将算法中的口 诀及技巧应用到d n a 链当中，使得传统中的代数运算能够并行的得到最终的结 果，这三种算法的设计都使得计算步骤减少，从根本上改变了算法的运算机制。 本文同时还计算了各种算法的复杂度，从理论上验证了d n a 计算在并行计算 上的优越性；同时也进行了编程的处理，编码方式十分简单、直观，编码具有规 律性，易于实现，在实践中验证了算法的正确性。 关键词：d n a 计算；代数运算问题；d n a 芯片 a b s t r a c t a b s t r a c t i t i st h e u s eo fh o r i z o n t a lc h a i nr e a c t i o nf o rd n a b a s e da d d i t i o n ”i nt h e m a g a z i n e s c i e n c e ”p r o n o u n c e db yf r a n ki n1 9 9 6 ，s t a r t i n gt h ew o r ko fa l g e b r a d n a - b a s e dc o m p u t a t i o n a tt h es a m et i m e ，“e n t i r e l ye n u m e r a t i o na n da u t o m a t i c s e l e c t i o n ”i nt h i sp a p e rb e c a m et h eb a s i ci d e ao fa l g e b r ad n a b a s e dc o m p u t a t i o n ， d i r e c t e db yt h i si d e a ，s e v e r a lm o d e l so fr e s o l v i n ga l g e b r ad n a b a s e da r eb r o u g h t f o r w a r d t h ee l e c t r o n i cc o m p u t e ri so fs e r i a lt os o l v et h ep r o b l e mw h i l et h ed n a b a s e d c o m p u t a t i o nt h a ti ss t i l li nt h et h e o r yi so fp a r a l l e lt os o l v et h ep r o b l e m w ea r en o w w i t ht h ep a r a l l e l r e p l a c et h es e r i a l t o p r o v et h es u p e r i o r i t yo ft h ed n a b a s e d c o m p u t a t i o n i nt h i sc o n t e x tw ea r em a i n l ys o l v et h es u b t r a c t i o na n dd i v i s i o nw i t ht h e d n a - b a s e dc o m p u t a t i o n i tg i v e st h r e ea r i t h m e t i cm e t h o d st or e s p e c t i v e l ys o l v et h e s u b t r a c t i o na n dd i v i s i o n n i ea r i t h m e t i co ft h es u b l ：f a c t i o ni sb a s e do nt h es e r i a l a r i t h m e t i c i tc a ne n t i r e l ye n u m e r a t ee v e r yp a i ro fs u b t r a h e n do nab i t ，a n di ta l s o c a l c u l a t e st w op o s s i b l el o a n i n gc a r r yv a l u e so ne a c hb i t s ot h es u b t r a c t i o nc a nb e o p e r a t e dt h r o u g ha u t o m a t i cs e l e c t i o n ，a n dc o m p l e t ec o l l a t e r a ls u b t r a c t i o na n dc a r r y o p e r a t i o n t h em e t h o do fs i n g l ed i v i s i o ni s s a m et oi t w i t ht h es t e n o g r a p h yo f s h i f e n g s h o uw e c a ns o l v et h ec o m p l e xd i v i s i o n w ep u tt h ef o r m u l aa n dt h et e c h n i q u e i n t ot h ed n am o d e lt og e tt h er e s u l t t h em e t h o d sa l lm a k et h es t e pd e c r e a s ea n d c h a n g et h ec o n v e n t i o n a la r i t h m e t i c t h ea l g o r i t h m si nt h i sp a p e rh a v eg o o dc o m p l e x i t y w h i c hr e f l e c tt h es u p e r i o r i t y o fp a r a l l e ld n a b a s e dc o m p u t a t i o ni nt h e o r y t h ec o d i n gi nt h i sp a p e ri ss i m p l ea n d d i r e c t ，a n di tc a ne a s i l yb er e a l i z e dw h i c hr e f l e c tt h es u p e r i o r i t yi np r a c t i c e k e yw o r d s ：d n ac o m p u t i n g ；d n a b a s e dp a r a l l e la r i t h m e t i c ；d n ac h i p 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 入已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：高差螭一导师签名： 第1 章绪论 1 1d n a 代数运算的发展现状 1 9 9 4 年美国南加州大学的a d l e m a n 在实验室里成功的用d n a 分子解决了一 个七顶点的有向哈密尔顿问题。开创了d n a 计算研究的新纪元。最初科学家大 部分研究致力于n p 问题的解决，直到1 9 9 6 年科学家才注意到要想说明d n a 计算 具有通用性，除了n p 问题以外，代数问题也应当受到重视。 研究d n a 解决代数运算的计算横式，主要是为了开发将来的d n a 计算机在 代数运算问题上的计算模型，改变代数运算的串行逻辑，实现并行逻辑。 现在利用d n a 解决代数问题已经有了一些初步的研究成果： 夺1 9 9 6 年，f r a n kg u a r n i e r i 发表在s c i e n c e 上的“m a k i n gd n a a d d ”一文首 先开创了利用d n a 解决数值运算的先河【2 】： 夺1 9 9 8 年z f r a n kq i ua n dm il u 提出了解决符号行列式的展开的d n a 表面 基计算模式 夺1 9 9 9 年的d i s c r e t em a t h e m a t i c sa n dt h e o r e t i c a lc o m p u t e rs c i e n c e 上又发 表了：j o h n s o l i l v e r 的矩阵乘法的d n a 计算模式1 4 ，t h o m a sh l e e t e 的 符号行列式展开的d n a 并行计算吼f r a n kg u a m i e r ia n dc a r t e rb a n c r o r 的水平链式反应的d n a j j i i 法【6 】： 夺2 0 0 0 年l a b e a n 等人用自装配方法也能实现累加异或巴 夺2 0 0 3 年r a n ab a r u aa n dj a n a r d a nm i s r a 发表在d n a s 上的“b i n a r y a r i t h m e t i cf o r d n ac o m p u t e r s ”i s 实现了在溶液中进行二进制数的加 法。 1 2 基本文献简介 1 9 9 6 z f r a n kg u a m i e r i 发表在s c i e n c e _ h l 拘l ( m a k i n gd n a a d d ) 【2 一文中首次 实现了n 位的两个二进制数加法运算的进位。这个算法的重要特征就是用d n a 单 链来编码输入值，对一个延伸引物反应的操作导致了一个称为“平层链反应的 过程。在这个过程中输入的d n a 序列作为一个新合成的d n a 序列不断延伸的连 续模板，从而结果链编码了一个序列的数，这些数以正确的顺序表示了两个输入 的二进制数值相加的结果。 d n a 链实现具体算法是2 0 位上的f i r s td i g i t 与s e c o n dd i g i t 先选择互补的粘头 链接形成双链，鳃开后其进位信息粘头s l 再与2 位的s e c o n dd i g i t 囊选择互扑粘 头链接形成双链，再次解开后s 2 与2 t 位的f i r s td i g i t 链接形成s 3 ，依次进行下去 得到最终的结果值，晟后用p c r 反应技术得到结果链。结果链是一种p o s i t i o n t r a n s f e r ( 进位信息) 和该位结果值交替出现的模式。虽然这种算法已经实现了 d n a 做加法，但是没有从本质上实现d n a 的并行逻辑运算，还处于串行逻辑思 维。 t h o m a sh 。l e e t e 的符号行列式展开的d n a 并行计算嘲主要是在溶液中利用 p c r 技术实现符号行列式的展开。他的算法主要包括三部分：编码数据、展开行 列式、读出数据。 ( 1 ) 编码数据： 矩阵中的每一个元素都被编码成了d n a 单链，被定义且被存放在一个容器 中：0 元素不编码，这样就准备了n 个容器来盛放矩阵中的每一个元素。 ( 2 ) 展开行列式： 算法一： 每一行的元素与它下一行的元素退火得到包含两个不在同一列的2 元素聚 合体的d n a 链。 方法是首先连接每一行与它下一行的元素得到包含两个元素的d n a 链，然 后加入引物得到不在同- - 3 i u 的两个元素的连接，并加入聚合酶形成完全双链，去 掉非双链，得到正确的d n a 链。 连接相邻的2 元素的d n a 单链形成3 个不在同一列的元素的d n a 链。 继续执行上述的步骤，直到得到最终的任一个”h 矩阵的包含全部元素长 度的结果链，并且所有的链都具有相同的初始元素，亦即按第一行元素展开。 算法二： 该算法与算法一相似，只是在每一步的连接形成多元素的过程中，聚合体是 2 从第一行与最后一行同时产生的，这样在形成一个2 元聚合体的时候即可得到一 个第二行元素与所有第三行元素的聚合、也有可能得到一个第三行元素与所有第 二行元素的聚合。 1 9 9 8 年z 。f r a n kq i ua n dm il u 发表的as u r f a c e - b a s e dd n a a l g o r i t h mf o r t h e e x p a n s i o no f s y m b o l i cd e t e r m i n a n t s ) ) 【3 】主要解决了在表面基上用d n a 链实现扩展 的符号行列式( a 。) ( i ( 1 ，玎) ；，( 1 ，n ) ) 的展开。这里假设展开时有许多零项的 存在。 本篇文章的算法及基于生化反应的操作如下： n 重排( s ) ：亦称为初始化。 2 ) 附着化学反应( x ，s ) ：使得在表面基上会包含第一行的某一个元素。 3 1 重复步骤2 ，这里f 每次都增加1 ，一直到 。现在我们得到的每个串 都应该具有r t 个不同行的，f 个单位。 4 1 标记( x ，s ) ： 5 1 删除( u m ) ：删除那些未被标记的串。 6 ) 当f ( 1 ：”) 时根据不同的沁重复步骤4 、步骤5 的操作”次，这能保证 每一个串中都将含有每一行的某一项。 7 ) 当j ( 1 ：”) 时根据不同的口，s 执行步骤4 、5 、6 。 8 ) 读出( s ) ：读出表面基上所有的串这就是行列式展开的每一项。每 个串都包括不同行不同列的每一项。 z f r a n kq i ua n dm il u 的这篇文章虽然在表面基上实现了符号行列式的展开 的并行算法，降低了实验的出错率，并且算法的复杂度由在溶液中实现算法时的 o ( m ) 降低为o ( 哟，其中n 为行列式的阶数，但仍没有解决行列式展开时每一项 的符号问题。 在f r a n kg u a m i e r ia n dc a r t e rb a n c r o f t 的( u s eo fah o r i z o n t a lc a b i nr e a c t i o n f o rd n a - b a s e da d d i t i o n ) ) 6 1 i 袁篇文章中，它主要是实现了两个n 进制数的相加。 这篇文章的算法原理及编码与f m n kg u a m i e r i f f j “d n a 的加法”。1 相似，只是将 二进制推广到n 进制。也是利用d n a 链表示每一位上的两个加数，让加数从低位 向高位依次相加，每一次只加一个加数。零位上的第一加数与第二加数相加是选 择互补的粘头发生链接，形成一条双链，然后解开成为单链，其进位信息粘头与 第一位上的第二加数选择互补粘头发生链接，形成双链，解成单链以后再与第一 位上的第一加数选择互补粘头发生链接，依次进行下去。同样的还是处于串行逻 辑思维。 2 0 0 0 年t h o m a sh l a b e a n 在n a t u r e 上发表的( l o g i c a lc o m p u t a t i o nu s i n g a l g o r i t h m i cs e l f - a s s e m b l yo fd n at r i p l e c r o s s o v e rm o l e c u l e s ) ) 1 7 谰自装配方法实现 了两层累加异或问题。在这篇文章里主要是用一个两层结构：一个输入层、一个 输出层，解决累加异或问题，同时亦可解决一个二进制的加法。 文章的算法： ( 1 ) 当输入的两个数值相同时输出0 ，当输入的两个数值不同时输出1 。 ( 2 ) 若设输入值为a i 、a 2 、a 3 ，输出值为b 1 、b 2 、b 。则b r = a 1 ； b i = b 。一i x o ra i ( i 1 ) 。 d n a 片的设计及反应过程如下图所示： 厘莺垦嚣莺嚣 图1 1t x 三螺旋自装配模型 f i g1 - 1t xt r i - c r o s s i n gs e l f - a s s e m b l ym o d e l 4 d n a 链的编码设计为三层结构称为“t i l e s ”。“xt i l e s ”的数值( o 或1 ) 被表示在片的中间部分，左上角的粘头编码了这个数值；右上角与左下角的粘头 使得该片能够顺次链接“x t i l e s ”。“y t i l e s ”的数值( 0 或1 ) 被表示在片的中 间部分，左上角的粘头编码了这个数值；下面的两个粘头分别代表了两个输入值： y mx 。由于此次操作中当输入的两个值不相等时输出1 ，则“yt i l e s ”的数 值为0 时相应的输入值可能都是0 或者都是1 ，则相应的片需要编码出两种情况； 同样的“y t i l e s ”的数值为1 时亦需要编码出两种情况。“c o r n e r t i l e s ”cm 与c 2 是用来初始化数值x 。与y 的，并且链接输入值与输出值。 d n a 编码的计算片的编码的碱基分布的不均匀性使得自己的粘头不能互 补，但是可以互补于其它必要的片。自装配计算从左下角开始，先是x l 、c l 、 c 2 三类片链接成最初始的结构，这时自装配会把相应的y l 找出并链接在初结构 上：第二步链接x 2 片，同样的自装配找出y 2 链接在结构上，依次下去，累加异或 的所有计算过程都在自装配形成的结构中了。图右下方深颜色的报道链经过了所 有的x 、c l 、c 2 、y ，并记录了它们的值，。 李慧在2 0 0 3 年的毕业论文算术运算的d n a 自装配模型【9 】里用d n a 链解 决了代数运算中的加法，她的这篇文章较好的利用了d n a 运算的并行算法。文 中把两个n 进制数相加的算法称作两个加数的线形单链l a b e a n 加法( 见文献【7 】) 。 这种并行加法的运行过程是； 第一步：两个加数中的每一位分别相加。各位的运算并行，每一位产生的结 果是至多两位数的n 进制数，此两位数结果中，其一为本位结果值( i ) ( 未加入 低位进位值) ，另一个为进位值。 第二步：每位的本位结果值( i ) 与低位的进位值相加。各位的运算并行，此 次加法产生每一位的本位结果值( i i ) ( 最终的本位结果值) 。 d n a 代数运算器的实现方法： i ) 设计输入生成库 该库按照位标分为若干子库：o 位，1 位，位，。每一子库编码加 数对( a ，、b i ) a i = o 、1 n - 1 ，b i = o 、1 n 1 。该库的每一条链设计为d n a 单链， 包括位标及该位的两个加数值。并且应用基于固体表面的d n a 反应技术将库中 的所有单链d 州a 分子的5 号端固定于固体表面的硫化基上。 编码方式如图示： 3 厂 一 位d ，b 图i - 2 输入生成库中的d n a 单链 f i gi 一2d n as i n g l e s t r a n di ni n p u t - c r e a t i n gw a r e h o u s e 2 1l a b e a n 加法库： 按照位标分为若干子库，每一个子库中存储该位上所有可能的两个加数对， 所有加数对被编码在d n a 链上，称为加数分子链。 ( 1 ) o 子库： 在相加过程中不接受前一位的进位，加数分子链结构如下图所示： 5 3 ( 0 ，6 0 ) q r 。q ( o ，& ) 图1 - 3n o 子库中的加数分子链 f i gi - 3a d d e n d m o l e c u l es i n g e - s n a n di nn o s u b - w a r e h o u s e ( 2 ) n 子库： ( i = l ，2 ，m ) 位上的加数在相加过程中需要接受前一位进位( 进位值 为0 或者1 ) ，所以每种加数对的相加都需要设计两种可能，接受进位值 ( t - i , s 。) 为0 和接受进位值( “，置一) 为1 ，编码如下图所示： 3 图1 - 4 1 位加数对的初始化 f i g1 - 4i n i t i a l i z a t i o no f a d d e n d0 1 1n b i t 3 ) 具体操作：当将初始化的单链( 分别编码位标、各位的加数) 加入输入生 6 第1 革绪论 成库时，这些单链将与表面基上的d n a 单链发生链接反应生成双链。将得到的 完全双链解链后投入到l a b e a n 加法库中，这些单链将与库中的加法分子链选择互 补粘头反应生成完全双链，利用外切酶切出进位粘头，互补的进位粘头互相链接， 最后从试管中提取带有n o 位结果值的d n a 双链就是最终的结果链。 1 3 问题引入及论文结构 到现在虽然已经有了大量的文献来解决代数运算的d n a 实现，但实现的算 法还是有许多缺陷，并且只是局限于解决算法中的加法，而且有些算法还处于串 行的运算过程，还没有解决好四则算法中的减法、除法以及其他代数运算。总之 代数运算的d n a 实现还是处于一个探索的阶段，还需要大量的研究、试验，来 建立一个通用的d n a 代数运算模式。 本文的第2 章及第3 章依次给出了减法、除法的d n a 计算模式。首先由算 法理论分析得到d n a 的算法模式，给出了具体的例子来演示算法的实现，并分 析了算法的时间复杂度与空间复杂度。论文的第4 章给出了计算机的模拟实验， 验证了算法的可行性。 1 4 本章小结 这一章综述了d n ac o m p u t i n g 在代数运算领域的发展现状，简单的介绍了 d n ac o m p u t i n g 代数运算中的加法、矩阵和行列式的d n a 运算模式的研究成果。 在最后给h 了本文的研究问题及文章的主要结构。 7 第2 章十进制减法的d n a 运算模型 2 1 减法算法理论 首先假定减数大于被减数，并且如果被减数的位数小于减数，左边画0 补齐。 不妨设减数： 日。d h 口g 1 口。， 被减数： b b b t b o ， 其中 a 。= 1 , 2 ，9 ；a ，= 0 , 1 ，9 ( i 0 1 i ) ；6 = 0 , 1 ，一，9 ，( f o ) 在计算中注意：任一减数在借出时即借给低位时只减少l ，而在借进时即 从高位借出时增加1 0 。 最高位相减不存在减数向高一级借位问题( s 。= o ) 算法如卜： 1 ) 各位并行相减：q b ，= s ，r i 。其中暑代表借位信息，可为0 或1 ；一代 表差值，可为0 , 1 ，9 。 2 ) 每一位所得的差值。与该位上一位的借位值j 。并行相减得到该位的最 终差值( 最低位除外) ：一s ，。= 。因为一e o ，9 】，s 。= o 或1 ，所以若 = o ，s h = l ，贝u = 1 0 一s h ，+ l = t 1 一s ，一1 3 ) 最终的结果值是0 一- r o 第一步： a 。一b 。 a 。一j b ，卜l 口2 一b 2口l b 】口。一b o s h rs n _ 1 0 1 s 2 r 2s t r js o r o 结果 3 幽 扛 吼 屯 州 州 m “ 2 2d n a 运算的模型 2 2 1d n a 编码设计 1 ) 设计生成数据库 在生成数据库中反应生成编码硬个l o 进制减数的d n a 分子链，即输入 两个减数对。输入的元素被设计成d n a 单链的形式，功能段依次包括位标及该 位上的两个减数值( o ，b ，) ( 有先后次序：前面编码减数，后面编码被减数) 。编 码方式如图示： ， 广一， 31 0 a b 5 图2 - 1 输入生成库中的d n a 单链 f i g2 - 1d n as i n g l e s t r a n di ni n p u t - c r e a t i n gw a r e h o u s e 2 ) l a b e a n 减法库 首先根据位标从右到左依次分为若干子库：1 0 0 ，1 0 ，1 0 。，子库。每一 个子库中储存该位上所有可能的两个减数值对。 】o 。子库 库中元素编码为d n a 单链，分为三个功能区：相应减数对的互补区域， 本位结果值r o ( 差值) ，借位信息。 编码如下所示： 3万i 万厂了1 百； 图2 - 21 0 0 子库中的分子链 f i g 2 - 2m o l e c u l es i n g l e - s t r a n di n 1 0 0s u b w a r e h o u s e ( 1 0 0j 。= ? ) 表示是否向高一级借位，如果借位则? = 1 ，反之? ：0 。图中虚 线代表该位设置了限制性内切酶q 的识别位点。 对于每一个d ，的取值都需要编码1 0 条d n a 单链，所以在1 0 0 子库中共需要 9 编码l o x l 0 = 1 0 2 条d n a 单链。 1 0 。子库 在该子库中编码d n a 单链时，需要考虑减数的双重借位问题，即借进与借 出之问的关系。编码的时候d n a 单链分为四个功能段：相应减数对的互补区域， 借给低位的信息，本位结果值( 差值) ，向高位的借位信息。 功能段编码如图示： 3 ( 1 0 ，d ，6 ，) ( 1 0 一l ，j ，一。：? ) l l ( 1 0 1 ，s ，：? ) 图2 - 31 0 子库中的分子链 5 f i g2 - 3m o l e c u l es i n g l e - s t r a n di n 10 。s u b - w a r e h o u s e ( 1 0 ，口，6 ，) 表示与相应的该位的两个减数互补；( 1 0 “1 ，一。= ? ) 表示该位的减 数口，是否借给低位信息了，如果借出则? = 1 ，否则? = 0 ：( 1 0 ，s ，= ? ) 则又表明 在决定向低位的借位以后，该位的减数是否需要再向较高一级借位了，需要的话 ? = 1 ，否则? = 0 ：表示了该位最终的结果差值；在的两侧编码了限制性内切 酶的识别位点。 对于每一个q 的取值，不同的b ( f = 0 , i ，9 ) 都编码了两种不同的d n a 单链， 总共有2 1 0 种编码，在1 0 。子库中b 有1 0 种可能的取值，所以共有 2 1 0 x 1 0 = 2 x 1 0 2 中编码。 1 0 ”子库： 最高位不能是0 ，减数值只能为i , - - , 9 ，分予编码为d n a 单链。在该子库中 编码d n a 链时，不需要考虑到减数的双重借位问题，只需要考虑借出的问题即 可。所以该库的d n a 链只需要编码三个功能段：相应减数对的互补区域，借给 低位的信息，本位结果值( 差值) 。 功能段编码如图示： 0 5 图2 41 0 “子库中的分子链 f i g2 - 4m o l e c u l es i n g l e - s t r a n di n 10 “s u b w a r e h o u s e ( 1 0 ”，口。，b 。) 表示与相应的该位的两个减数互补：( 1 0 ”。，s 。= ? ) 表明该位是否 借给低位了：_ 表示了该位最终的结果差值。虚线部分编码了限制性内切酶的识 别位点。 在这里注意取值时由于被减数总是比减数小，所以b 。s a 。当b 。 延长反应 15 3 j 育t i 丁+ 3 5 ( 1 0 。 , 8 , 9 ) i 。( 。l o 。, s o = 0 ) i r l = 9 1 ( 1o , s , = 1 ) 。 3 5 ， ( 1 0 。j , 8 1 , 9 。) 1 i ( l o 。, s o = 1 ) i r l = 8 1 ( 1 0 i , s , = 1 ) 一 蠹3 + 3 ，一5f 匹翌丁两i 叮矿 l 匹翌丁两再1 r 7i(102,5,3)(101,sj=0)r2=2 一 j l 巴互卫互e 晒 连接并延长 + 面巧翌竺! 图3 - 8 计算产生每一位上的结果值 f i g2 - 8p r o d u c er e s u l to i le a c hb i t ( 6 ) 读取结果链：j ：5 ，s 。= 0 7 1 ，r o = l ，即2 8 5 除以4 最终的商是7 l ，余数是l 。 3 2 多位数除法 3 2 1 算法简介 该算法是模拟史丰收速算法中的除法心算，其主旨思想是从高位开始， 每商一位，便将被除数剥去一位，主要目的是消灭相应被除数的首位数，求得下 一个较短的( 至少短一位的) 被除数，直到最终实现整个除法的运算。 传统除法的图式： ( 除数) f 1 2盟盟盟 、1【2 】 3 】【4 】4【5 ， x ( 1 ) ( 1 ) ( 1 ) ( 1 ) 商数 被除数 x ( 2 ) ( 2 ) x ( 2 ) ( 2 ) x ( 3 ) x ( 3 ) ( 3 ) ( 4 ) ( 4 ) ( 5 ) 除数下方第一排是“除数x 商( 1 ) ”之积的各位数码。第二排是“除数商( 2 ) ” 之积的各位数码。如果在被除数位每下方竖着看那些数码。f 1 】i ( 1 ) 是无 疑的，而【2 卜x ( t 卜( 2 ) n 是未必的，这是因为【3 】下三位数累加一般有进 位数【2 1 1 1 1 应该还有进位数。同理 3 】中含有 4 1 - b - i n 位数累加的进位数 纯心算除法是每确一位要消灭相应被除数的首位，同时改变次位，作为下一 个被除数的首位，而不改变其他位，这就是把传统的除法的层层剥削改为步步缩 短，每商一位，被除数便缩短一位。 商( 1 ) 时，目的是消灭 1 1 ，【1 1 = ( 1 ) 是必然的，紧接着次位边改做 2 卜【2 一x ( 1 ) ，商( 2 ) 时意在消灭【2 】，但是不能像【1 】那样直截了当地确定( 2 ) 了。因 为【2 。】里有 3 i t 各数累加的进位数，必须预先扣去。那么这进位数是几昵? ( 2 ) 、 ( 3 ) 还没有出现，( 2 ) 全不知道，( 尽管可以知道( 1 ) ) 进位数无从知道。 这时只好估计、试探，这就发生了所谓的试商问题；而试商问题的焦点就是预扣 进位数问题。一般而言。加数越多，进位数越大。所以因该从下位的累加数的多 少来考虑。 在讲该算法时首先注意以下问题： 1 一个多位数除以一个两位数，根据史丰收快速算法的要求，除数首位一定划 o ，被除数首位大于除数首位时才戈l jo ，最终结果4 舍5 入。 不妨设b i b 2 b 。a l c l 2 如，其中口l = o ，4 2e 【l ，9 】，吗【0 ，9 】； 6 l = o 时，i j 6 2 【4 2 + l ，9 】， 【o ，9 】，i 23 ；若6 i o ，曩l6 1e 【1 ，1 2 2 一l 】，b 【o ，9 】，i 2 2 总之：b l o ，口2 一i 】 注：若b = 如，则需要比较b ：与口：的大小，此算法不考虑这种情况。 i i 、商的定位( 末位未补0 之前) ： b t 6 _ 4 t a 当被除数的首位数字小于除数的首位数字时，商的位数埘一”： 当被除数的首位数字大于除数的首位数字时，商的位数坍一 + l 当被除数的首位数字与除数的首位数字相同时，可再比较次位数字，比较出 大小后再用上述方法定位。 i i i 此算法是从最高位算起，逐位消去，消灭相应被除数的首位数字，求得下一 个较短的被除数，即从左向右，那么位标也简化为1 位、2 位 i v 每商一位要消灭相应被除数的首位数字，同时改变次位，次改后的试商都是 阻为除数的，每商一位是以q = 0 试出的，实际是根据a ，后进的，商s ，得根据 ：x 的进位判断。 v 根据要求可知编码时最高位只有( 0 ，o ) ，( o ，1 ) i ( o ，9 ) 1 0 种可能。 预扣值对该位来说是减少。或1 ，但对于下一位来说则是在相应的数值卜增 加。或1 0 ( 十进制) 改算法主要是模拟一个多位数除以一个两位数( 末位未划o ) ，除数的位数越 多，除法库相应的要分的越细，但是算法的复杂度的计算是与除数的位数无关的， 它是根据6 i 和s ，来考虑的。 3 2 2d n a 编码 除法库： 编码时根据a 2 = 1 , 2 ，9 分为9 个子库，后在每个子库中又根据q = o ，1 ，9 分 级( 分级主要是由于6 产6 j 一( 口2 s l - i ) 2 一( 。3xs h ) 2 一( 吩。s 。) 。，该数值是与口：及 q 有关的，当上两步计算所得到的s 。、s 。一定时，以的数值是固定的) 1 位 丽f ( 】，3 r ) 图3 - 9l 位的分子链 f i g3 - 9m o l e c u l es i n g l e - s t r a n di n1b i t 中间的双链编码的是位标及该位的结果值：( 1 ，马) ：0 ，o ) 代表的是该位的结 果值、预扣值= 0 ( 保证由l 位d n a 链的唯一性来确保其余位d n a 链的唯一性， 若s 商得太大，则在2 位考虑退位即可) 。 b 【o ，吼一1 而e 【0 , 9 ，每子库编码】0 条d n a 链，9 个子库共9 1 0 ：9 0 条d n a 链。 2 位： b0 b l ( 2 ，2 ) ( 量，) = 6 2 一( 口2 。) 2 一( 吒j 。) 。 m ，j 2 ，预而一 ( 2 ，j 2 ) 图3 - 1 02 位的分子链 f i g3 - 1 0m o l e c u l es i n g l e s t r a n di n2b i t 垃= b z 一( 口：s 1 ) ：一( 龟x s 。) ，代表的是从b 2 中躐去( q “毛) 的本位值和 ( a 3 丑) 的进位值，取值范围为【o ，d ：一1 】；双链编码的是位标及该位的结果值： ( 2 ，5 2 ) ；( s ，屯，预扣) 编码的是该位和前一位的结果值、预扣值( 可为1 或o ) 还有一种情况：若蜀商的太大，此时需要考虑到退位 ( 2 ，6 ：) ( s i ，。) ( ) ( s j - 1 , 0 , 0 ) 6 i 2l 。+ 6 2 一【口2 ( s - 一1 ) 】2 一【d ，( j - 一1 ) ) - 位 0 ，j 一1 ) 可i ( 2 ，是) 退五五可= i 旷鬲蕊 图3 一l li 位中的分子链 f i g3 - 11m o l e c u l es i n g l e s t r a n di nlb i t 其中：前两条链中的6 卜( 1 0 + ) b 一( d 2xs h ) 2 - ( a 3 x5 h ) 2 一( a ，x8 i - 1 ) 。，如果上一 步的预扣值为1 ，则该步中需要加上1 0 否则不用加。退位后 町= 1 0 + b i ( - 1 ) 一( 口2 s h ) 2 - ( a 3 j h ) 2 一( q 。s ，一1 ) l ，该步中由于上一位预 扣1 了必须在原先的数值上加上l o ，若在该步的计算中还需要向下一位 预扣1 ，则还需要在计算后的数值上再减1 。没有退位前的链中的双链依 m 位： 次代表( f ，s 。) ( f ，s ，) ，而退位后的链中的两个双链依次代表( f ，j 一一1 ) ，( f ，5 ，) 其中砹链代表( t r ，s 。) 图3 1 2m 位中的分子链 f i g3 - 1 2 m o l e c u l es i n g l e s t r a n di nmb i t 编码时考虑到b i 【o ，9 】，i 。【o ，c ：一l 】r 包括顿扣值j ，s ，【o ，9 】，每一位都需要 编码1 0 x 9 + 2 0 x 8 + + 9 0 x 1 + 1 0 0 = 1 7 5 0 条d n a 链。( r a 一1 ) 位共需要 1 7 5 0 ( m 一1 ) 条。 该算法总共需要编码1 7 5 0 ( m 一1 ) + 9 0 条d n a 链。 最终结果需要用表面基技术读出。 表面基的设计：将模板划分为n 个部分，每一个部分再分为1 0 个小的单位， 这1 0 个小单位分别编码数字o 9 。 将形成的结果链( 有可能不止一条) 上的双链用剪切酶切下来，投入到已经 设计好的带有荧光的表面基上最终用荧光反应读出结果，没有荧光反应的表明 已形成了双链，若某位最终桔有两个结果，取较小的那一位。若互补反应时形成 了多条双链，每一条双链都要进行上述的操作，最终计算余数来判断正确结果是 什么。 读结果数时根据商的定位来判断最终结果是多少。 余数的求法： 我们再考虑一下在作计算的时候没有考虑的项：a 3 s h ，a ：s m , 口3 s 。，将 这三项按照计算中的形式罗列相加，将得数看作小数，最后一步的预扣数减去这 个小数，将是终的结果转化为整数，亦即最终的所要求的余数。 吒j 十l + 2 2 s mf 2 3 s m 3 2 3 算法分析 3 9 6 4 8 8 4 被除数首位小于除数首位，命a = 3 9 6 4 8 ，除数首位当冠以0 之后，记作d = 0 8 4 部竖式如下： 0 8 4 1 39 648 ( 1 ) 第一位商的使命就是消灭a 的首位r = 3 ，乘d 的首位0 而能得3 的数 只有4 ( 0 4 得3 ) ，首位商4 ，把a 的首位3 划去，紧接着就是求第二个被除 数的首位数r ，第二个被除数应该从a 的第二、三两位9 6 里减去8 4 x 4 的乘积 的后两位数( 再缀上a 的末两位4 8 ) ，但是现在我们只要它的首位数，所以只从 第二位9 里减去8 x 4 ( d 的次位商的首位) 的个位数3 ，把这个乘积记作s 。 9 里除去s 、以外还应有下位进上来的数，姑且认为这个数是1 ，那么 r 2 = 9 一s l 一( 强扣迁位盎】) = 5 ( 2 ) 第二步是消灭a 的第二位9 ，实际工作是消灭r ，= 5 。d 的首位0 乘以 什么数得5 昵? 只有7 ，第二位商7 ，划去a 的第二位9 0 8 4l ! 1 3 9648 接着来求第三个被除数的首位数r ，。r ，包含在a 的第三位6 里，但是6 里 还有d 4 的末位数，和d x 7 的十位数二者之和的个位数；也就是d 与商相乘 中的一个逐位外移乘积之和s ：= 4 4 + 8 x 7 的个位数，心算乘积，指算求和得 6 + 8 = 1 4 ，对于a 的6 来说只是从6 减4 ，1 4 的十位数1 正好抵消前边预扣得进 位数所以要把第二位预扣得进位数l 和第三位拼成1 6 ，然后减& ，才合理： r 3 = 1 6 一s ：一( 预扣进位数1 ) = 1 ( 3 ) 现在需要做的t 作是消灭恐= 1 借以消灭a 的第三位6 ，由第i 位商完 成这任务，经过观察只有2 可以当选( 0 x 2 得1 ) ，第三位商2 ，划去a 的第三 位6 。 0 8 4l 兰z呈 396 48 然后求第四个首数r 。将上位预扣的1 与a 的第四位4 拼成1 4 ，这次要 先算一个外移乘积墨，上两次里s i , 足的首项都用商的首位做乘数，分别取d 的 第二、第三位做被乘数，先是8 后是4 ，s 的足码增大，d 的被乘位向右移，到 s ：移到末位了，是及其以后各s 的酋项，便一概取d 的末位开头，而商的数位 要逐个往后错。前次是用4 开始乘的，这次要用7 开始乘，7 的位号2 = ( 待消的 位号4 ) 一( d 的位数3 ) + l ， s 3 = 4 7 + 8 x 2 # t 8 + 6 = 1 4 r 。= 1 4 一s ，一( 预扣进位数) 现在不扣后进数已经使r = 0 了，r 。= o 就是a 的第四位4 消灭