（基础数学专业论文）算术运算的dna自装配模型.pdf

摘要 1 9 9 6 年f r a n kg u a m i e r i 发表在s c i e n c e 上的“d n a 的加法”一文首先开创 了利用d n a 解决数值运算的先河同时，文中提出的“全列举与自动选择”成 为d n a 代数运算工作的基础思想在这一基础思想的指导下，本文在四个基础的代 数运算的d n a 运算模式方面作了探讨 首先，运用l a b e a l l 解决累加异或问题的编码思想，实现n 进制的两个加数的 加法进位问题这种算法摆脱了以往的串行加法运算思想，将每一位上两个加数对 的所有可能进行全列举，同时考虑每一位上接受进位值的两种可能，使得加法运算 在自动进行选择的过程中完成并行的加法和进位 第二个d n a 代数运算模式是关于数制的转换，因为二进制的d n a 代数运算 模型结果较多，所以当数制的互换问题解决以后，可以间接的解决其他进制数的代 数运算数制转换库的结构和分子的设计编码是这个算法的核心，利用全列举的思 想，将不同数制互换时的对应进制级分别编码，编码满足一定的规则，这种规则使 得各个进制级可以任意顺次连接，并且唯一的对应着转换得到的不同进制的数 第三个是关于多个加数连加的d n a 运算模式若要解决代数运算中的乘法 问题，首先要解决运算过程中出现的连加运算在第四章中介绍了两种连加运算的 d n a 模型，第一种是基于l a b e a n 累加异或的方法，第二种方法是利用了数制转换 库的基本思想 最后，运用与数制转换库思想相似的乘法库解决了一位数与多位数的乘法问 题，乘法库中全列举了所有可能的乘数与被乘数对这种算法可以根据乘数的不同 选择不同的乘法子库 关键词： d n a 计算；d n a 加法：并行计算 a b s t r a c t i ti 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 kg u a m i e r ii n l9 9 6 ，s t a n i n gt h ew o r ko f a l g e b r ad n a - b a s e dc o m p u t a t i o n a t t 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 d a u t o m a t i cs e l e c t i o n ”i nt h i s p a p e rb e c a m et h e b a s i ci d e ao fa l g e b md n a - b a s e d c o m p u t a t i o n d i r e c t e db yt h a ti d e a ，w ed e v e l o p e d f o u rd n a - b a s ec o m p u t a t i o n m o d e la b o u tb a s i c a 1 9 e b r ao p e r a t i o n f i r s t ，w i t ht h ec o d i n gi d e ao ft h o m a sh l a b e a n “l o g i c a lc o m p u t a t i o nu s i n g d n am 0 1 e c u l e s ”，w ed e v e l o p e dad n a - b a s e da d d i t i o nm o d e lo ft w on s y s t e m a d d e n d t h i sa r 主t h m e t i cc a s to f rs e r i a la d d i t i o ni d e a ，b u te n t i r e l ye n u m e r a t ee v e r yp a i r o fa d d e n d so nab i ta n di ta i s oc a l c u i a t et w op o s s i b j er e c e i v i n gc a i t yv a l u eo ne a c h b i t s ot h ea d d i t i o nc a nb eo p e r a t e d t 1 1 r o u g h a 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 e c o l l a t e r a la d d i t i o na n dc a r r yo p e r a t i o n t h es e c o n da l g e b r ad n a - b a s e dc o m p u t a t i o nm o d e li sa b o u n u m e r a ls w i t c h b e c a u s em a l l yr e s u l t si sa b o u tt h ed n a - b a s e dc o m p u t a t i o nm o d e lo fb i s y s t e m ， w h e nt h eq u e s t i o no fn u m e r a ls w i t c hi sd o n e ，w ec a ni n d i r e c t l yr e s 0 1 v ea 1 9 e b r a d n a - b a s e dc o m p u t a t i o nm o d e lo fo m e rn u m e r a ls y s t e m n u m e r a ls w i t c hw a r e h o u s e i st h ek e m e lo ft h i sa l g o r i t h m i c w i t lt 1 1 ei d e ao fe m i r e l ye n u m e r a t i o n ，w em a k ee a c h b i tc o d e df o rd i f r e r e n ts y s t e ms w i t c h i n g ，a n dt h ec o d i n gs a t i s f i e dd e f i i l i t em l ew h i c h c a u s ee a c hb i ta r b i t r a r yc a n1 i 1 1 ki no r d e l t h et h i r di sa b o u td n a - b a s e dc o m p u t a t i o nm o d e lo fm u l t i a d d e n ds u c c e s s a d d i t i o n 1 br e s o l v em u l t i p l i c a t i o nd n a - b a s e dc o m p u t a t i o nm o d e l ，w em u s ts o l v e s u c c e s sa d d i t i o ni nt h ec o m p u t a t i o n p m c e s s a t 血s t a tc h 印t e rf b 峨w ei n t r o d u c et 、v o k i n d so fd n a - b a s e dc o m d u t a t i o nm o d e lo fs u c c e s sa d d i t i o n t h en r s ti sb a s eo n l a b e a n si d e ao fl o 百c a lc o m p u t a t i o n a n dt h e s e c o n di m p o s en u m e r a ls w i t c h w a r e h o u s e f i n a l l y ，w i mt h em u i t i p l i c a t i o n w a r e h o u s ew ec a i lr e s o l v et h em u i t i p l i c a t i o n b e t w e e no n eb i tn 啪b e ra 1 1 dm u l t i _ b i tn u m b e lh lt h em u l t i p l i c a t i o nw a r e h o u s e ，m e r e h a v ee n t i r e l ye n u m e r a t i o no fe a c hp a i ro fm u l t i p l i e ra n dm u l t i p l i c a n d t h i sa r i t h i n e t i c c o u i ds e l e c td i 丘b r e n ts u b w a r e h o u s eb a s eo nd i f 诧r e n tm u l c i p l i e ra n dm u l l i p l i c a n d k e y w o r d s ：d n a c o m p u t i n g ，d n a _ b a s e da d d i t i o n ，p a r a l l e lc o m p u t a t i o n i i 第l 章绪论 近二十年来，在计算机领域，人们发现传统运行模式的电子计算机，不论是体 积的增大还是运行速度的加快都面临着临界的问题所以，非标准计算模型越来 越受到人们的关注，特别是d n a 计算虽然现在还无法看到他们的原型，但它们发 展的潜力是巨大的，因为他们都具有并行性、容量大、速度快等特点这一章介绍 了d n a 计算的基本知识，以及d n a 代数运算的发展现状 1 1 d n a 计算的基本知识 1 9 9 4 年南加州大学的l e o n a r d m a d l e m a i l 在实验室里成功的用d n a 分子解 决了一个七个顶点的有向哈密尔顿问题“1 ，从此开创了d n a 计算研究的新纪 元d n a 计算的诞生向人类揭示，d n a 可以作为计算的介质而用于解决人类的数 学问题，这是真正意义上的生物数学：生物是计算工具而人类数学问题是计算的 目的，因此完全不同于以往科学文献中“生物数学或数学生物学”的含意：数学 是工具而生物学问题是目的。1 最初，大部分研究致力于n p 问题的解决，这是因为n p 问题是计算机与分子计 算根本的差别所在”j “a d l e m a n 所在研究组的工作已经可以解决2 0 个变量的 3 一s a t 问题目前解决的具有标志性的n p 问题有有向哈密顿路径问题、 3 一s a t ( l i p t o n 模型) 、最大团问题、3 一s a t ( 发卡模型) 等 随后，出现了另一个很重要的问题：代数运算的d n a 实现9 6 年g u a r n i e r i 等人实现了用d n a 计算来作加法“1 要想说明d n a 计算具有通用性，除了n p 问题 以外，代数问题也应当受到重视 w i n f r e e 对d n a 自装配计算的发展作出的贡献最大，他的关于二维d n a 格设 计和自装配影晌了后来d n a 计算的发展方向在他的工作基础上，d n a 计算的问 题解决更具有简单和仿真性后来自装配计算成为d n a 计算一个重要研究方面 e h e n g d em a 。等人款论文弱d 凇三螺旋分子豹囊装配来实现加法和逻辑异或 运筹”3 ，a s h i s hg e h a n 释 珏乙a b e a n 等人把这矜方法用于掇密系统，提密了一 稀基于次性密码本的d 涨加密算法8 日本的k e n s a k us a k a m o t o 等人提出的发 卡状计算模型解决可满足性问题“1 ，也怒建立在分子自装配的基础上的 基于表露的d 凇计镎是早在9 7 年裁提如的一辞模型，它的饯越性在于具有实 现蠢动操髂豹潜力。2 0 0 0 年t u r e 秘载了q i n g h u 8l i u 豹文章，标患者表藤上黪 d n a 计算正在逐步完善“ 实现d n a 计算的期动化一直是研究者的一个嗣标，在这方短，比较突出的工 作是以色列萋襄熬可绽糗生物分子自动担的提出模拟弛r i n g 枧瓣装置可以爨 动莠行瓣稷据输入鼹稷净技幸亍不嗣鼢数据鲶理“ 王本人宣布露4 造蹬篷界上第一 台d 敞计算机，它楚专稍来作基因分析豹“ 剥用生物分子去傲计算较利用电予器件去做计算有明显的优越性：一、生物 分子取之不尽用之不退：二、d n a 计嬖是蓦度并萼亍的。原理上l o 亿个甚至l 亿个d n a 分子冒黼对发生亿学反瘫，邵计算是嗣辩送行静；三、此辩，d n a 分予 存储同祥多的数疆占用的空间仅为电予计箨税的l l o ”，雨做同样的计算所耗能 量仪为电子计算机的1 1 0 9 透露，d n a 计算主要包括三个步骤： l 、进行编码，帮将所要解决的闷题浚射为一个p n a 分子静集合： 2 、计算过程，进行备种生化反成如杂交、链接及延伸等生成可能解空间； 3 、解的分离和读取( 如p c r 反应和凝胶电泳) d n a 计葬在本质上楚生化反应，因藏，为了利用p n a 分予完成给定静任务，必 须借助对d n a 分子的各种操作技术对d n a 分子的操作，既有物理的，也裔仡学的 物理操作实质上是调控生化反戍的外部条件，例如潋度，酸碱度等等。此外是来自 各矛孛生化试验手段，尤其是通过各葶申酶的操作在试管中d n a 生化操作经常用到 熬鸯以下几秽m 1 ： 2 1 合成：游离的碱基形成寡核苷酸的过程 2 连接：两个d n a 分子在有连接酶存在的条件下，按w a s t o n c r i c k 原则配对且 将缝隙修补好，从而连接在一起的过程 3 提取：将含有特定d n a 短链的分子提出来，这要通过将特定短链的互补链吸附 在小磁珠上，然后用磁铁将小磁珠吸出来的过程 4 延长：这一过程需要一条已知单链模板和一条已存在的，已与模板的一小段匹 配的引物d n a 序列，要延长的d n a 序列根据模板给出的序列结构，在聚合 酶的作用下由5 到3 的方向不断延伸 5 缩短：通过核酸外切酶从d n a 分子的末端去掉一个核苷酸而缩短d n a 分子 6 剪切：限制性内切酶将含有它能识别的序列处，将双链的d n a 分子切为两段的 过程 7 退火和溶解：这是两个完全相反的过程，退火是指两条互补的d n a 单链在温度 逐渐降低的条件下，合成一条双链的过程；溶解是一条d n a 双链在温度升 高时，解为两条单链的过程 8 凝胶电泳：将d n a 分子置于凝胶电场中，由于d n a 分子带负电，在电场中会向 正极移动，长度大的分子链受到凝胶的阻力大，移动速度慢，因此可用此 技术去获取一定长度的d n a 分子链，也可区分不同长度的d n a 分子 9 放大( 复制) ：游离的碱基与作为模板的链配对连接形成双链，然后解成单链， 继续这样的过程，于是目标链会以2 的指数级增长 区别与a d l e m a n 的操作方法，另一种方法是将d n a 链固定在一个表面上，这对 于d n a 计算提供了许多帮助最初，寡核苷酸的溶液集附着在一个表面上( 玻璃， 硅片，金片，等等) 然后对它们进行一系列的操作：在溶液中进行杂交或外切核酸 酶的降解，提取出期望的解决结果这种方法大大减少了纯化步骤中d n a 分子的 丢失这种基于表面的生化操作经常用到下面几种“”1 ： l 、重摔：龟称作裙始仡这步将产生所寿需要生成酶d n a 链这些镶可以根据 要求代表不同的数值 2 、附羲化学反成：发面姻接触预上的分子和初始化的d n a 链附着到表面上( 袋 嚣秘初始他教d n a 链都经过特殊准备，使它们姥够附蛰到表殛上) 3 、标谗：标记这些链傻需在这些镱的舀由段把它们变成双链，爵为初始状态时这 些链都是单链把一些单链加入到表面上，它们将与需要标记的链进行邋 火这样根据w a t s o n 。c r i c k 原则就会形成部分双链 4 、 # 标记：即将袭题上的d n a 双链解链，只嚣在蒸馏水中清洗表猫持且提高温 度，这群在容器中只会有单链髫在表兹。 5 、翮除：这一步操作楚和厢一些外切核酸酶逸释表瑟上酶d n a 链的末端外甥 核酸酶具有一定的特性，可以针对革链，也可以针对双镌通过选择不同的 外切核酸酶，可以有选择的删除标记的双链成者非标记的单链 6 、读出：；罄要把表题上的链分离出去。些内切酶可以识别双链的短序列中的限 制牲位点，并在这个位虑把硬链切繇当表嚣上黪链含有返些位点，巍热入 内切酶时所有表面上酶链都可敬被分离然螽利蔫滚滚中读取玢n a 链的 方法进行读取 1 ，2d n a 代数运算的发展现状 利用d n a 解决代数运算问题已经有了一些初步的研究结渠1 9 9 6 年，f r a n k g u a n l i e r i 发表在s c i e n c e 上的“d n a 的加法”一文首先开创了年用d n a 解决数 值遂算的先河；1 9 9 9 年的d i s c 俄em a t h e m a t i c s a i l dt h e o f e t i c a lc o m p u t e rs c i e n c e 土又发表7 ：如b s 0 i i l v e r 豹矩跨乘法豹d 卦玖计算模式“”，t h o m a s h l e e 把的 符号行捌式展开静d n a 并行诗算，f 托】呔g 珏a r n i 酾鞠dc 毡矗。rb 张。f o 最题水平 链式反应的d n a 夯翳法8 ：就屠，z f 怒】i ) j ( q 砖a n d 确乙u 又撬密了耩决符号行舞式 的展开的d n a 表面计算模式”“ 在自装配方法得到发展后，l a b e a n 等人用自装配方法也能实现累加异或”1 研究d n a 解决代数运算的计算模式，主要是为了开发将来的d n a 计算机在代数 运算问题上的计算模型，并且改变代数运算的串行逻辑，实现代数运算的并行逻 辑 在f r a n kg u 锄i c f ia n dc a r t e rb a n c r o r 的水平链式反应的d n a 加法这篇文章 中5 1 ，利用d n a 链表示每一位上的两个加数，让加数从低位向高位依次相加，每一 次只加一个加数零位上的第一加数与第二加数相加是选择互补的粘头发生链接 形成一条双链，然后解开成为单链，其进位信息粘头与第一位上的第二加数选择 互补粘头发生链接，形成双链，解成单链以后再与第一位上的第一加数选择互补 粘头发生链接，依次进行下去虽然这种方法已经实现了d n a 做加法，但是这种加 法没有从本质上利用d n a 的并行逻辑运算的优点，还处于串行逻辑思维 在j o h n s 0 l i l v e r 的矩阵乘法的d n a 计算这篇文章中“，主要探讨了利用 d n a 计算模式解决特殊的布尔矩阵的乘法与特殊的实数矩阵的乘法计算布尔矩 阵时，先将矩阵与图论中的有向路径一一对应起来，然后利用d n a 链表示路径中 的每一条边，当选择了互补的粘头以后，这些链发生链接，形成一条路径，表示了 积矩阵中的对应元素；计算实数矩阵时，矩阵与带有权值的有向路径一对应， 用与权值的大小成正比的d n a 链的浓度表示矩阵中的每个元素，同时也表示了 路径中的每一条边的大小，当这些边按照化学可逆反应形成一定浓度的路径时， 浓度的大小就表示了积矩阵中的元素的大小文章中的主要算法是： 利用d n a 来代表边、顶点和路径来完成计算计算由以下若干步组成： a 、计划和综合利用d n a 代表图中的顶点和边； b 、构造准确的d n a 进行反应以形成路径： 。、分析生化反应，辨识通过酶限定的起始顶点与终止顶点之间的路径起始 点与终止点之间的路径由一段线性的双链d n a 来代表，这些双链d i n a 分别在其 每一个终点处包含不同的特定顶点限制性内切酶位点 强o m a s 壬己e e e 与z 。f f a l 墩q i h 赫dm il u 所馋鹩嚣簇文章分别从溶液、表瓣 两种不蠲生亿操作豹角度解决了符号行捌式展开酌d 淑并行计算“4 ”这两种 算法都蹩按照第一行的元素展开行捌式，将编码不同行不同捌的元素的d n a 链按 照行的顺序依次链缓起来，中间过程中将不正确的结果链利用p c r 扩增反应稀释 去除这种算法把行列式展开后的每一项元索( 不包括符号+ ，一) 用双链d n a 表示 出来，但是还没宵鲻决每一项的符号如何表示 这些算法黪极铡是按照设计豹算法摸式，利用d n a 分子的生化操作，让大量 豹渊a 分子同辩避行努甥与连接懿循嚣，形成结累d n a 分子链达到竞成代数遮 算的目的鲻前，利糟d 佟代数运算静计算模式酶研究还链予裙缀阶段，裔大鼙 的代数问题等待着迸一步的研究和改善 星兹，在国内也蠢一些d 凇加法的进位计算摸型的文肇，鳃决二进铡热法中 的蠡动避位文章串豹算法是：将酝有可能抟二进到热数对都列举出来，针对不网 的加数对运用不同的算法搽作，达鄹低位离离使音动遴位的过程这种算法对于 二遂制的加法比较可行，但在对待n 迸制加法，本质上没有建立并行运算的杭制 总体上看，髫翦d 凇计算熬研究状况类似予电子计算机在四，五十年代的形 势，鄯建立计算梳溪论蒸磁凝群辊设计静除段。3 ，特剃令人鼓舞豹是d 凇基计算 的完备性与通糟性研究已得到充分的证确，计算速度与存储静巨大优势褥掰瑗 论与实验的证明，生化实验已经普遍成功，也已经建立了解决许多复杂数学问鼷 的计算模型，其中有许多是基于表面的d n a 计算模型等 僵楚鸯凡东臻莲不嚣，点是发展黪速度扶，特别是在现代生诧技术飞速遂 步的直接作甭下，觚第篇论文算起，斑短，年辩溺已经有相当自动佬黪模嫠梳 诞生，也就是2 0 0 1 年威兹蔓实验室扶实验的角度证明了d n a 计算机能够实现电 子计算机所能实现的功能，这些都袭明d n a 计算这一新的科学领域越来越受到 科学界的瞩目另一点更为重要，因为本质上并行的计算装置其运行模式将可能 完全不嗣予以串行诗冀规划( t u r i n g 计算模型) 的运行横式，至今虽然有大量 计算模式捻塞，健是龆没有被营速接受蜘统一模式甚至将来的d 凇计算枫是否 6 将采取单模式都受到怀疑第三点，由于d n a 计算，从一开始就关注解决人类 数学中的困难问题，即所谓n p 问题，而许多研究者认为众多数值计算是电子计 算机的专用领地”1 ，所以d n a 计算的定位，或者说d n a 计算机的应用范围都是争 论的问题因此，类比于t u r i n g 时代，d n a 计算的形势远为复杂 目前，对于代数运算的d n a 计算模式的探讨也处于摸索的阶段，至今还有大 量关于代数运算中的加法问题，进位问题等基础运算问题的计算模式的推出，这 些问题的解决是为下一步包括矩阵运算、行列式运算、线性方程组运算等代数 运算系统的d n a 计算模式的创建打下基础所以，建立一个统一并且通用的d n a 代数运算模式也仍然是一个悬而未决的问题 1 3 本章小结 这一章中综述了研究者们对d n ac o m p u t i n g 各个领域的探索和成果，以及用 于d n ac 。m p u t i n g 的几种常用的试管和基于表面的生物操作另外，还介绍了d n a c o m p u t i n g 代数运算中的加法，矩阵和行列式的d n a 运算模式的发展和研究成果 第2 章n 进制线形l a b e a n 加法 d n a 运算模型 在自装配方法得到发展后，t h o m a shl a b e a n 等人用自装配方法实现了累加 异或问题”3 t x 片的编码方法很好的实现了逻辑运算的并行算法，并且在运算过 程中能够一次性完成累加问题本文从这种自装配方法的思路出发，设计一种n 进制加法自动d n a 运算模型，这种算法突破了以往的串行d n a 加法思想，并且将 t x 片复杂的三层d n a 片改造成单链d n a 片 2 1 自装配的l a b e a n 累加异或模型 2 0 0 0 年，n a t u r e 杂志上发表的t h o m a shl a b e a l l 等人的文章l o g i c a l c o m p u t a t i o nu s i n ga l g o r i t h m i cs e l f - a s s e m b l yo f d n a t r i p l e c r o s s o v e rm o l e c u l e s 用 自装配方法实现了累加异或问题 聊 y i = o 】【i = 0 x l = o 一篓，1 即= o v l = 0 弛= 1 弘l = 1 y l = l 盈= o y l = 1 v i = 1 x l = 1 y - l = 0 蘑霆垦垦垦垦蟹皇三 叵= = 医羔二盏医互= 盏医苴二盏区量二盈 图2 1t x 三螺旋自装配模型 f i g 2 一lt x 啊一c m s s m g s e l f a s s e m b l ym o d e l - 8 第一1 章n 进制线形i ，a b e a n 加法d ，。a 蒜苗：1 曼代 图2 一l 上方有作为自装配用的8 个组分t x 片，上面6 个是作计算的，下面两 个是用来初始化计算计算片的中间编码工。+ y 。的计算结果值，。，下面编码两个 加数z ，y 。，上面编码作为下一个加数y ，的计算结果值s ，x 。，y 。，y ，都编码在粘 头上，碱基分布的不均匀性使得自己的粘头不能互补，但是可以互补于其它必要的 片图一中间的图示表明了计算的结果，自装配计算从左下角开始，先是x 。、c - ，c 2 三 类片，链接成最初的结构，这时自装配会把相应的y 。找出并链接在初结构上；第二 步链接x z 片，同样的自装配找出y 2 链接在结构上，依次下去，累加异或的所有计算 过程都在自装配成的结构中了报道链从经由所有的x 、c 、c z 、y ，并记录了它们的 值，图右下方深颜色的一条线既是报道链 2 2 两个n 进制数的线形l a b e a n 加法 下面的内容主要介绍的是：从自装配方法的思路出发，设计两个n 进制加数 的加法d n a 运算模型，该算法吸取了自装配的并行运算，并且将t x 片复杂的三层 d n a 结构改造成单链d n a 结构，在加法运算过程中能够一次性完成两个n 进制 多位加数的加法问题 两个n 进制的加数相加，首先每位的加数对( 两个加数) 相加会产生至多 两位数的结果，一个称为本位结果值，另一个称为进位值；然后，除了o 位，每一位 的本位结果值需要与低一位的进位值( 针对本位称作接受进位值) 相加，又因为 进位值取值为0 或者l 所以每一位相加的结果有两种可能：本位结果值加上1 ， 或者本位结果值不变 当利用d n a 运算模型进行计算时，首先将每一位的加数对编码成两种d n a 链( o 位的加数对只需编码一种) ，一种对应接受进位值为0 ，另一种对应接受进 位值为1 运行加法计算的过程中，o 位的d n a 链决定了1 位的两种d n a 链中 的一种( 即，o 位的进位值决定1 位的接收进位值) ，依次下去，每一位被唯一的 正确选择了d n a 链的连接，于是得到每一位相加后的正确结果下面具体介绍算 法，编码和操作过程 2 2 1 线形l a b e a n 加法理论 2 2 1 t 代数算法：两个n 进制加数的相加是d n a 代数运算可以实现的 一种计算功能，把这种运算称作两个加数的线形单链l 曲e a f l 加法这种并行加法 的运行过程是： 第一步：两个加数中的每一位分别相加，各位的运算并行，每位产生的结果 是至多两位数的n 进制数，此两位数结果中，其一为本位结果值( i ) ( 未加入低位 进位值) ，另一个为进位值即： 假设两个n 进制数在位上的两个加数分别为：口j 和岛( q ，岛= o ，n 一1 ) ， 那么 口，+ 6 ，= 5 ，1 + ( 2 一1 ) 其中，s 。为和中的进位值，若。+ 6 。，则s 。= 1 ：若a f + 6 f _ - i 2 卜 _ j i f ，| j 。，n 为二进制数 所以，十进制数转化为二进制数的关键是： 1 、将m 分解为t ，”也，月 ，； 2 、将十进制数”t 转化为二进制数的位标，即“t = 2 同理，设n 为一个二进制数，把n 写作口i n h 口。口。，其中口。= o 或者l ，表示2 i 位 上的数值为。或者l ，不妨设，d 。：，等于l ，其余为o ： n = 岛 2 鼻+ 口1 2 + 2 2 + 口h + 2 1 = + + 月i ：+ ” 2 ( 3 2 ) 其中，口 = l ，”h 为十进制数，”= 2 ，为十进制数 所以，二进制数转化为十进制数的关键是： 1 、将n 的数值为l 的位2 ，2 “，2 转化为十进制数，即2 = 月k ； 2 、将所有的h 。相加 ( 2 )d n a 运算器的数制转换的实现方法： l 、输入十进制数m 或者二进制数n ： 输入十进制数时，将十进制数m 编码为一条d n a 单链：输入二进制数时，将 二进制数n 中数值为1 的位2 “，2 “，2 编码成引物单链 2 、利用数制转换库中的转换分子实现数制转换： 十进制转换为二进制数时，各级子库中的转化分子与十进制数m 的d n a 单 链发生选择性的互补链接反应，完全互补链接的d n a 双链表示转换的完成：二进 制数转换为十进制数，2 “，2 “，2 单链与转换库中相对应的，七：，j ，子库中的 分子互补连接并进行延长然后进行自动选择性的互补链接反应，连接出最长的 d n a 双链即表示转换的完成 3 、输出结果值： 十进制数转换为二进制数时，将最长的d n a 双链上的发卡式结构剪切下来， 与输出结果值单链反应。利用荧光反应观察输出结果链，有荧光的序列表示该位 上的结果数值为0 ，无荧光的序列表示该位上的结果数值为】二进制数转换为十 进制数时利用带有编码序号l 的d n a 序列提取结果链，并通过凝胶电泳的办法 读取最长d n a 双链的最后序列，读取的序列标号就是二进制数转换为十进制数 的结果 31 2 数制转换的d n a 模型的描述 ( 1 ) 十进制数m 的d n a 单链的设计：将十进制数m 表示成一条由m 个功 能段组成的d n a 单链，这条单链上从5 号端到3 号端的m 个功能段依次为：l ，2 ， m ，且每一个功能段的d n a 编码全部不相同如下图所示： 5 1 t _ t _ 一 3 l23 m 一1m 图3 1 十进制数m 的输入d n a 单链 f i g 3 一ln u m b e r m o f d e - s y s t e mi n p u ts m g l e s t r a n d ( 2 ) 二进制数n 的单链的设计： 将二进制数n 中数值为1 的2 ，2 “，2 t 位分别编码成单链，一个位标编码为一段d n a 单链，所有位标的编码全部不相同 如下图所示： 5 3 2 “位 5 ：3 2 z 位 5 3 2 位 图3 2 二进制数n 输入d n a 单链 f 培3 2n u m b e r n o f b i s y s t e mi n p u ts i n g l es t r a n d ( 3 )输出结果值单链的设计： 输出结果链是一条由1 0 9 ：，2 个功能段组成 的d n a 单链，每一个功能段编码一个二进制的位标，这条单链上从5 号端到3 号 端的l 0 9 2 m 个功能段依次为：2 0 ，2 1 ，2 。，2 “8 一，如下图所示： s 1 - r 厂厂厂一3 2 02 。2 2 2 2 ”9 2 “ 图3 3 二进制数的输出结果单链 f i g 3 - 3s y s t e ms w i t c ho f b i s y s t e mo u t p u ts i n g l es t m d ( 4 )数制转换库的结构：首先介绍数制转换库，数制转换库按照二进制 的位标分为若干个子库，2 0 位是第一子库，2 1 位是第二子库，2 位是第f + 1 子库 如下图，数值转换库的结构： 表3 1 十进制与二进制互换的数制转换库 t a b l e 3 - ls w i t c hw a r e h o u s eo f d e s y s t e ma 1 1 d b i s y s t e mi n t e r c h a n g e ( 2 0 )( 2 1 )( 2 2 )( 2 卜1 ) 第一子库第二子库第三子库第f 子库 1 21 2 3 - 41 2 3 一一2 “ 5 69 - 1 0 “1 22 + l 一2 + 2 2 + 2 1 2 p + 12 2 p + l 一 2 3 p + 1 23 p + 2 一2 p + l 一2 p + 2 一2 。p + 2 卜1 一2 2 p + 2一2 3 p + 3 23 p + 4 此数制转换库满足两个主要的规则和一个定理 子库中p 的取值：每一个子库中的分子链的个数由子库中的p 值决定，p 值的选取有以下的规律：假设数制转换库中的最高位为第2 “1 位，即第k 子库，那 么： 第k 子库中p = o ，库中仅有一种分子链，功能段编码是： 1 2 3 一- 一2 “ 第k - 1 子库中的p = o ，l ，库中有两种分子链，功能段编码是： 2 一1 p + 1 2 一1 p + 2 一一一2 - 。p + 2 一2 第k 2 子库中的p = o ，1 ，2 ，3 ，库中有四种分子链，功能段编码是： 2 2 一p + 1 2 - 2 p + 2 一一2 一2 p + 2 一3 第f 子库中的p = 0 ，1 ，2 ，2 “一1 ，库中有2 “种分子链，功能段编码是： 2 p + 1 2 p + 2 一一一2 7 p + 2 一1 第一子库中的p = o ，1 ，2 ，2 “一1 ，库中有2 “1 种分子链，功能段编码是： 2 p + 1 所以，按照p 的取值，将每一个子库中包含的分子链个数相加，数制转换库 中的分子链总量为： 1 + 2 + 4 + + 2 一+ 2 一1 = 2 i ：2 分子连接的规则：数制转换库的结构与转换分子的功能段的编码存在下面 的性质： 第2 子库与第2 7 子库的分子链接时( f 卜，) ，链接得到的分子链是： 2 。p 。+ 1 2 p 。+ 2 一一2 p f + 2 h 一2 ，+ 1 2 7 p ，+ 2 一2 p + 2 一1 ( p ，- p ) 所以，2 p 。十2 “= 2 p ，链接后的分子链长度为2 “+ 2 卜1 个功能段，代表2 1 位和2 。位的结果值为1 f ，= 1 ，2 ，3 ，；p = o ，l ，2 ， 数值转换库满足的定理：任意一条十进制数m 的d n a 输入链，均可以由数 制转换库中的分子链唯一的组合构成与其完全互补的d n a 链 证明：没有任意一条十进制数m 的d n a 输入链，对应的十进制数为m 因为，十进制数与二进制数是一一对应的，m 唯一的对应着一个二进制数n 州= 九t 1 + t 2 + 。+ 以鼻 = 2 2 。+ 2 2 十+ 2 f = 以 二进制数n 中2 ，2 “，2 位上的数值为l ，其余位的数值为o 下面只需证明， 数制转换库中的d n a 分子链存在唯的组合可以对应二进制数n 对应的d n a 链 首先证明组合的存在： i ) 因为n 中2 位的数值为l ，而数制转换库的2 “子库中的分子的功能段为： 2 毛p + 1 2 ，州p + 2 一一一2 1 p + 2 七i 此分子链表示2 个1 ，也表示2 “位的数值为1 ，可以令p = o ，所以，这条分子链就对 应着n 中的2 “ i i ) 同理，因为n 中的2 z 位上的数值为l ，而数制转换库的2 如子库中的分子的功能 段为： 2 ：+ 1 p + l 一2 ：h p + 2 一一一2 2 p + 2 2 此分