戴夫·多蒂介绍算法自组装

||谈话

戴夫Doty肖像戴夫Doty是加州理工学院的高级研究亚博体育官网员。他证明了关于分子计算的定理,并通过DNA实施实施算法分子自组装的实验。

卢克·穆罕沃斯:几年前你写了一个评论文章在算法自组装上,也创建了一个视频介绍对象。您的评论文章开始:

自组装是小部件自动组装成大型复杂结构的过程。自然界中有很多这样的例子:脂类自我组装细胞膜,噬菌体病毒蛋白质自我组装衣壳,使病毒能够入侵其他细菌。算法自组装系统自动完成了一系列简单的生长任务,在这些任务中,被生长的物体同时也是控制其自身生长的机器。亚博体育苹果app官方下载

作为一个例子,这是一个电子显微镜图像的一个谢尔宾斯基三角形通过DNA分子的算法自组装

Sierpinski三角形

在您看来,迄今为止在实验室中产生的最令人印象深刻的算法分子自组装例子是什么?


戴夫Doty:让我玩这里的政治家和回答这个问题我希望我一直问,也就是说,有什么区别算法和non-algorithmic自组装,算法自组装情况如何工作截至2014年4月,是什么理由认为我们可以使它工作更好的未来?

非算法自组装
有非常令人印象深刻的例子non-algorithmic在实验室中的分子自组装。两种非常成功的技术是DNA折纸和DNA瓷砖。DNA Origami需要一个长长的DNA链,称为a脚手架(最常用的一个有7249个基础)。这个想法是合成大约200多的(〜32个碱基)单链的DNA,称为斯台斯特,每个通过碱配对(与T和C结合到G)结合到支架的多个区域中以使区域一起粘合在一起,基本上折叠支架。仔细设计哪一个区域将被聚集在一起,这意味着通过不同的折叠方式,可以从同一个支架中创造出不同的形状。

DNA瓷砖以不同的方式使用碱基配对DNA。DNA瓦片是一种络合物,其具有一些(通常4)的单链区域,称为“稠粘的末端”,可在4个不同的侧面上结合(它们是“粘性的”,因为它们将通过基部配对与互补的粘合在其他瓷砖上的单股线)。DNA瓦片的一个优点是我们不受支架股线的尺寸的限制;可能很多超过200瓦可以绑定形成大结构。

这些技术中的任何一个的“默认”方法是使用唯一的方法类型每一个自组装形状的“像素”对应的DNA链:200个DNA链结合形成一个形状意味着200个不同的DNA序列。

算法自组装
算法自组装的“算法”方面意味着许多不同的副本一个类型DNA瓦片可以在结构的几个不同部分中重复使用。通过模拟小程序(例如,PI的一个打印数字)可以编码大型或无限对象(PI的数字)而呼叫此“算法”,尽管本地规则,可以对大型或无限对象(PI的数字)进行编码。

例如,如果一个瓦片被设计成与它自身的所有副本绑定,那么整个空间(如果在二维空间中是一个平面)将被一个规则的正方形网格中的自身副本所填充。我们可以做得更漂亮一些:设计两种类型的瓷砖,白色和黑色,这样白色只能绑定到黑色,黑色只能绑定到白色。然后你会得到一个无限的棋盘图案。有点有趣,但仍然是周期性的。

事实上,如果我们能够实现所谓的“合作绑定”,我们可以变得更有吸引力:正确地设置实验条件,以便只有当一个贴图的两个粘性端点匹配时,它才能绑定到其他贴图的网格上。窍门是,有些其他类型的瓷砖可能只匹配一个或另一个粘性末端,但只有一个匹配两者将被允许绑定。如果这个规则可以强制执行,那么tiles就可以组装任意高算法复杂度的结构,因为这给了tiles执行的能力任何程序随着他们的成长,又使用该计划直接进一步增长。

那么回到你的问题:今天在实验室里最令人印象深刻的算法自组装例子是什么?我们有组合成二进制计数的瓦片(瓦片以二进制表示连续正整数的行绑定)和计算异或的瓦片(这反过来导致了一种模式,就像您所展示的,它创建了Sierpinski三角形的离散版本)。最好发布的二进制计数器从1到6,然后绑定错误将其发送到9。有一些未发表的图像显示计数器在出错之前已经走得很远了,但是我们离完全消除错误还有很长的路要走。

那么这些错误是什么,我们打算如何驯服它们呢?这些错误来自于合作绑定的失败尝试:一个tile与它的一个粘性端匹配,而不是另一个(因此是错误的tile类型),但它还是连接了。

减少错误有许多实验方法。

Lately we’ve been working a lot on getting certain experimental conditions right for cooperative binding to be favorable: for example, each sticky end should have the same binding strength as every other (G-C bonds are twice that of A-T bonds, for example, so this isn’t trivial to achieve just by using identical sticky end lengths).

长时间的温度保持似乎产生良好的效果,但是正确的温度选择往往取决于许多其他因素,所以有时候我们努力寻找合适的温度,然后在下一次实验中,随着条件的轻微变化,需要找到一个新的最佳温度。

有办法纠正错误“软件”通过设计一些冗余的瓷砖,在类比纠错编码,使用200位表示一个100位的信息,所以,一砖一瓦的代表,一个2×2或3×3块瓷砖都表示相同的。

最后,还有几个实验室在研究DNA纳米技术社区的其他想法,以实现合作结合。例如,有一种被广泛使用的技术叫做DNA链置换,它被证明在控制人工DNA系统的相互作用方面非常有用。亚博体育苹果app官方下载这是可以想象的,它可以用于DNA瓦片检测条件“我的‘输入’结合位点匹配”,然后才允许瓦片附着。许多DNA纳米技术和合成生物学项目利用现有的酶,特别是那些与DNA和RNA相互作用的酶,重新利用它们来帮助驱动人工DNA系统的某些部分,所以这可能也是一个探索算法自组装的想法。亚博体育苹果app官方下载

我不知道我提到的任何这些想法是否最终是从“梦幻理论游乐场”到“可靠技术,用于自下而上的分子制造”的算法自组装。我毫无疑问某物但是,将工作。每天,大自然使用自下而上的自组装自动组装令人难以置信的复杂性的分子结构。我们正在做的是弄明出,所需的工程原则可以可靠和便宜地进行。


路加福音:对于算法自组装领域的人,您认为它是否特别难以吸引资金和研究人才,以这种“梦幻般的理论游乐场”?亚博体育官网您曾习惯于帮助利用资金和研究人才来努力解决这些问题的方法,尽管它们是远离实际应用的几年?亚博体育官网


戴夫:我不认为要么困难。

我想“资金的难度”总是相对于我们可以学习的其他科目,但不是。例如,获得企业资助可能更容易学习公司如何使用在线病毒营销,以便提高其利润,但该项目的主要风险是在我死亡之后我无法完成它。

当然,当您可以显示保证结果时,资金总是更容易获得保证。但大的突破是制造的 - 只有 - 只有人们决定在一个项目上工作,在那里提前明确,它将上班。

美国国家科学基金会(National Science Foundation)的使命明确指出,基础科学是一个目标,也就是说,研究世界是为了更好地理解它,而不仅仅是作为某种应用的手段。我认为这对整个社会来说是一件好事。让我们高兴的是,美国国家科学基金会在与算法自组装和更普遍的分子计算相关的资金资助方面一直很慷慨,其他一些政府资助机构也是如此。

就吸引人才来说,我应该说有很多实验科学家在立即进行实际应用中进行工作:例如,使用“DNA电路”,或使用自组装的DNA结构,从而指导精确放置其他结构如碳纳米管或晶体管,具有非常精细的分辨率。

但我相信很多人都和我一样,被这个领域所吸引正是因为人们对它理解得如此之少,组织得如此混乱,以至于它离(甚至更大的)实际应用还有好几年的时间。一旦一个领域被很好地理解,应用程序很容易遵循,我们就会感到厌倦,并想转移到其他还没有人理解的领域,这样我们就可以成为第一个在试图理解它方面取得进展的人。

我受到了艾伦·图灵(Alan Turing)这样的人的启发,他在1936年对可编程计算机进行了深入思考,那是在第一台可编程计算机问世之前的很多年。到了20世纪50年代,实用的电子计算机真正取得了长足的发展,图灵转而研究生物形态发生。

当然,我经常被问到,“编程物质操纵自己的实际应用是什么?”,我礼貌地迫使猜测“智能药物”和“纳米级机器人”。我很好奇,如果在1936年被问到,“自动化计算的实际应用是什么?”以及他是否有一个令人记忆的回应,肯定没有包括“太空飞行”,“互联网”,“智能手机”或“巡航控制”。

我并不是说每个项目都应该资助,无论它是否有申请。但即使是最晦涩的想象力也可能会出现一些可能遵循的实际后果,从学习和控制分子水平时可以遵循。

我认为我们的领域确切地吸引了聪明的人,因为他们不需要任何令人信服,这是一个重要的目标。他们只需要听到两件事:

  1. 物理法中没有任何内容表明它无法完成,而且
  2. 我们不知道该怎么做。

路加福音那很有趣。比尔希伯德我有一个即将到来的纸张CACM.叫“人工智能中的探索工程,“我列出了一些名为”探索工程“的Eric Drexler的若干例子。我命名为TINGE'S Pre-Eniacal工作,前斯图尼克航天和其他一些例子。回顾一下,我应该命名算法自我组装并引用你的CACM.纸张!

人工智能在这方面很有趣,因为有些人认为完全是通用的。”美国国际集团“现在是一个合理的事情,即使是几十年的几十年,恰恰是因为物理学表明它应该是可行的,但我们只是不知道该怎么做。但是,还有其他人认为写作关于AGI的论文甚至在公共场合谈论这篇文章,因为这是过于投机和理论的。

在你的领域中也存在这种划分吗?如果没有,你有理论解释为什么在人工智能领域有这种划分,而在你自己的领域却没有?


戴夫:这个部门肯定存在于我的领域。我经常想到有两个理论的口味,我将司归咎于第一种类型的第二种理论的判断结果:

1)描述性的理论这有助于预测现有自然系统的行为,亚博体育苹果app官方下载在服务中实验。在这里,如果理论预测与实验不同,那么理论模型的错误有问题,理论模型,理论版需要更加努力使模型更加现实。一个例子是牛顿的动作定律,预测台球将如何在台球桌周围移动。当他们不如上所序地移动时,它是模型的问题,需要更新摩擦,空气阻力等想法。

2)规范理论这是用于谈论我们想要在可能或可能不存在的新系统中工程师的行为的编程语言,亚博体育苹果app官方下载服务于实现程序化行为的实验。布尔电路的理论工作就是一个例子,它抽象出了晶体管的底层实现(或者最近,用DNA链或遗传转录因子实现)。当电子电路没有输出正确的比特时,这不是布尔电路模型的问题,这是实验实现的问题,未能以这种方式保持模拟电压,以正确表示布尔电路中的离散比特。

如果我理解你的意义,这两种类型的第二种理论中的第二个在正在研究的系统尚未存在时非常好。亚博体育苹果app官方下载最自然科学的大多数理论是描述性的,但理论计算机科学几乎完全是规范性的。理论计算机科学家不会预测通过实验确认的物理结果。Rather they show what is possible (and impossible) for certain engineered systems to do, and sometimes (as in the case of algorithmic self-assembly, or quantum computing, or electronic computing in 1936) they are reasoning about systems that haven’t even been built yet.

抽象的瓷砖装配模型是一种说明性理论(它的一种变体;另一种变体称为动能瓷砖组装模型更接近于潜在的化学成分,在我们做实验时更多地使用描述性的意义)。抽象的瓷砖组装模型并不能预测DNA瓷砖的作用,这也不是它的目标。该理论的要点是,如果DNA瓷砖可以建立具有理想行为的模型,那么,嘿,看看他们可以做的所有其他惊人的事情!事实上,我们目前无法通过实验来设计这种行为,这并不是理论模型的问题。这是实验的问题。

当仅熟悉描述性理论遇到规范理论的人遇到的某人时,会使困惑结果。我证明了不可能性定理(表格,“没有系统存在的行为”)并被问到我是否打算在实验上确认他们,这是一个甚至没有逻亚博体育苹果app官方下载辑意义的概念。

例如,通过1936年进行的暂停问题的无禁令性,这些问题在于,没有计算机程序P可以预测另一台计算机程序是否作为输入给出的另一个计算机程序,永远不会停止。没有实验可以做到证实这个定理,但它的真相是自然的基本法。

因为我不太了解,我无法评论AI字段及其批评者。这种现象可能是一个解释。

也就是说,并非所有探索工程都同样有效。通过猜测可删除不可能的任务,可以过于推测。我认为理解关于尚不存在的系统是很好的,只要我们有一个有充分的理由相信他们亚博体育苹果app官方下载可以有一天的理由存在。不幸的是,我已经看到了很多在模型中完成的理论,这些理论与物理学法则有所不同,例如填充2的想法500将DNA链(比宇宙中原子的数量还多)放入一个试管中,以“并行测试”一些复杂的组合问题的“所有解决方案”。

但是,当有人告诉我,工作算法自组装是与现实格格不入,因为他们从来没有见过这样的发生在一个实验,我想象他们告诉电气工程师在1930年代之前,仅仅因为他们从没见过一个二进制数字电子电路做算术,这种观念一定与现实不符。有很多方法可以证明某些系统是无法构建的,但仅仅缺乏构建它们的想象力并不是这亚博体育苹果app官方下载些方法之一。


路加福音:在进行规定的理论时,有明确的,正式的法律模型非常方便,该法律管理您想要做什么。例如。如果没有原则的方式摘要远离实施细节,则难以做量子算法设计,但事实证明,所以人们实际上可以证明某些结果,即使量子计算机还不存在。AGI理论的一个问题是,没有人知道AGI将会是什么样子,而且你只能用(例如)物理和计算复杂性理论来演示AGI的终极能力。至少在艾基(及其可计算变体)可以制作原则参数什么某些类AGIS会做或不做,但到目前为止,该领域很少可用。

如何通过正式模型启用现场的规范理论,这些模型摘要远离实施细节?


戴夫:抽象的瓷砖装配模型是一个规范理论的主教。它摘要摘掉所提出的DNA实施。事实上,它真的基于普通结晶理论而不是DNA。形成正方形晶格的任何结晶分子,仅在单体附着率的温度下刚刚大于由两个键保持的单体的分离速率(假设所有粘合强度相等),应具有相同的实施效果合作绑定:只有在至少两个债券保持时,瓦片最终才会永久地附加。可以使用特异于DNA的技术或更普遍的生物分子来实施这种合作结合的其他物理方法。

这个模型有一些变体,它们基于实现的合理物理机制,抽象了实现的精确方法。最近有一些关于信号通行证瓷砖,其能够在响应于从相邻瓦片接收信号之后地附加信息。它们可以反过来向其他瓦片发送信号,并且信号用于做像激活或停用键的事情,这允许比其原始模型中的更复杂的组件更复杂的组件发生。被动瓷砖。假设的合理限制是在用完之前,只能在瓦片上发送固定数量的信号;这是基于这样的想法:如果发送信号是热力学上有利的(无论什么精确的机制),那么它应该在发送信号之后将瓦片放在较低的能量状态之后,并且在某些时候它到达最小能量。

There is some unpublished lab work I’m aware of implementing the beginnings of this sort of thing using DNA, but the point of the model is to say, “What’s a reasonable abstract model of signalling tiles that seems plausible and likely to capture lots of different ways of doing it?” and then ask what the model can do. The hope is that the results apply not just to one potential implementation of signalling tiles, but lots of different ways.

另一个例子是在运动中的一些工作:如果单体能够在附加后相对于彼此移动?同样,这可能是由ATP驱动的某种分子电机,或者它可以由比以前在运动之后附着的更多碱基对的事实驱动。

在算法自我组装之外移动到分子计算中更普遍,我最喜欢的型号之一是所有科学中最古老的模型之一:化学反应网络。These are lists of reactions like X + Y –> A + B, indicating that when a molecule of X and a molecule of Y collide, they might change into molecules of A and B. It’s abstracting away the question, “What exactly are X and Y and A and B, and why would they have this effect if X and Y collide?” As long as your system is based on molecules floating around a well-mixed liquid and bumping into each other (with no control of who’s going to bump into whom), and some of them might change as a result of colliding, then the model of chemical reaction networks applies to it.

自1860年以来,该模型已经存在。在20世纪70年代,一群数学家开始对不同类别的化学反应网络可能进行的数学家进行相当严重的审查:振荡,稳定状态。最近,已经应用了更多的计算视角,提出问题,“什么样的计算如果我们允许工程师任意化学反应,是可能的吗?“

这看起来像是理论肚皮凝视的终极:是什么让任何人认为我们可以工程师进行任意化学反应?嗯,假设一种称为DNA链位移的物理机制的合理模型(DNA纳米技术领域的实验工作研讨会之一),几年前显示了您可以思考的每一个抽象的化学反应网络可以系统地翻译成亚博体育苹果app官方下载一种亚博体育苹果app官方下载DNA复合物系统,经过实际反应模仿摘要反应。

当然,这只是尝试实施化学反应网络的一种方法。当我们使用化学反应网络进行规范理论时,我们没有考虑特定的实施。我们知道它在那里,它有助于我们在晚上睡觉,但也许还有其他方式来工程师人工化学反应,以及抽象化学反应网络的工作也适用于这些系统。亚博体育苹果app官方下载


路加福音:谢谢,戴夫!