在算法自我组装上Dave Doty

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

自组装是小部件自动将自己组装成大型复杂结构的过程。实例中的实例比比皆是：脂质自组装细胞膜，并且噬菌体病毒蛋白质自组装衣壳，允许病毒侵入其他细菌。即使是晶体形成的现象也是自动组装的过程......算法自组装系统自动化一系列简单的生长任务，其中所生长的物体同时控制其自身的生长。金宝博官方

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

在您看来，到目前为止，实验室生产的算法分子自组装最令人印象深刻的例子是什么？

Dave 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执行的能力任何程序随着他们的成长，又使用该计划直接进一步增长。

所以回到你的问题：今天实验室中的算法自我组装最令人印象深刻的例子是什么？我们有拼凑地组装成二进制（Tiles绑定在二进制中的连续正整数的Tiles）和计算XOR的图块（它又导致图案，就像您所显示的那样，它创建了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系统的相互作用方面非常有用。金宝博官方可以想象它可以用作DNA瓦片来检测“我的”输入的绑定站点匹配的条件“，并且允许瓦片附加的条件。许多DNA纳米技术和合成生物学项目采用现有的酶，特别是与DNA和RNA相互作用的酶，并将它们重新培养以帮助驱动某些人工DNA系统，因此这可能是用算法自组装探索的想法金宝博官方出色地。

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

卢基：对于算法自组装领域的人，您认为它是否特别难以吸引资金和研究人才，以这种“梦幻般的理论游乐场”？金宝博娱乐您曾习惯于帮助利用资金和研究人才来努力解决这些问题的方法，尽管它们是远离实际应用的几年？金宝博娱乐

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

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

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

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

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

但我喜欢相信很多人都像我一样，被田野所吸引恰恰是因为它非常糟糕地理解，因此偏离（甚至更大）的实际应用是多年的。一旦一个领域很好地理解，应用程序遵循很容易，我们都会感到无聊并希望继续前进到其他人没有人理解的事情，这样我们就可以成为第一个在试图理解它方面取得进步的人。

我的灵感来自艾伦图灵等人，他们在1936年的可编程计算机上非常深刻地思考，在第一个建造之前。一旦实用的电子电脑在20世纪50年代真正击中了他们的步伐，所以已经搬到了所有事情，生物形态发生的研究。

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

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

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

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

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

在这方面，AI很有意思，因为有些人认为全面普遍“agi.“现在是一个合理的事情，即使是几十年的几十年，恰恰是因为物理学表明它应该是可行的，但我们只是不知道该怎么做。但是，还有其他人认为写作关于AGI的论文甚至在公共场合谈论这篇文章，因为这是过于投机和理论的。

该划分是否存在于您的领域？如果它没有，你是否有一个理论为什么在AI字段中有这个部门，但不是在你自己的领域？

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

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

2）规范理论这是用于谈论我们想要在可能或可能不存在的新系统中工程师的行为的编程语言，金宝博官方服务于实施程序行为的实验。一个例子是Boolean电路的理论上工作，摘要与晶体管（最近，使用DNA链或遗传转录因子的实施）摘要其底层实现。当电子电路未输出正确的位时，它不是布尔电路模型的问题，这是一个问题的实验实现的问题，该问题未能以正确表示布尔电路中的离散位的方式维持模拟电压。

如果我理解你的意义，这两种类型的第二种理论中的第二个在正在研究的系统尚未存在时，这两种理论中的第二个是探索工程。金宝博官方最自然科学的大多数理论是描述性的，但理论计算机科学几乎完全是规范性的。理论计算机科学家不会预测通过实验确认的物理结果。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瓷砖可以建立具有理想行为的模型，那么，嘿，看看他们可以做的所有其他惊人的事情!事实上，我们目前无法通过实验来设计这种行为，这并不是理论模型的问题。这是实验的问题。

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

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

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

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

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

卢基：在进行规定的理论时，有明确的，正式的法律模型非常方便，该法律管理您想要做什么。例如。如果没有原则的方式摘要远离实施细节，则难以做量子算法设计，但事实证明有，所以人们实际上可以证明某些结果，即使量子计算机还不存在。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纳米技术领域的实验工作研讨会之一），几年前显示了您可以思考的每一个抽象的化学反应网络可以系统地翻译成金宝博官方一种金宝博官方DNA复合物系统，经过实际反应模仿摘要反应。

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

卢基：谢谢，戴夫！