数学家传记
伦纳德·阿德曼是一位美国计算机科学家,最著名的是作为RSA加密算法的创造者之一。
伦纳德·阿德曼的父亲是一名电器销售员,母亲是一名银行出纳员。作为在旧金山长大的小男孩,阿德曼几乎没有抱负,更不用说成为数学家了。据他自己承认,他是[1]“incredibly naive and immature”。然而,是他的高中英语老师通过阅读《哈姆雷特》让他意识到思想的美。正是在这位打开他眼界的老师的建议下,“to the fact that one could see things more deeply than the purely superficial”,阿德曼进入了乔治·伯克利的加州大学。仍然犹豫不决,他最初宣布要成为一名化学家(受多年观看电视上的Mr.Wizard启发),然后是一名医生(受他的Kappa Nu兄弟会兄弟启发),最后才决定主修数学。[1]
我经历了无数的事情,最终唯一能在合理时间内脱身的就是数学。
他花了五年时间,终于在1968年毕业,随后在美国银行找到了一份计算机程序员的工作。不久之后,他申请了医学院并被录取,但他改变了主意,没有入学。他决定转而成为一名物理学家,并在银行工作期间开始在旧金山州立学院上课。他再一次失去了兴趣。
我不喜欢做实验,我喜欢思考问题。
阿德曼最终回到伯克利攻读计算机科学博士学位。他有两个动机,第一个是实际的:-
我认为获得计算机科学博士学位至少能促进我的职业生涯。
第二个更为浪漫。马丁·加德纳在Scientific American上发表了一篇关于库尔特·弗雷德里希·哥德尔定理的文章,其深刻的哲学意义让阿德曼大为震撼:-
我想‘哇。这太妙了。’有几件事我觉得很妙——黑洞、广义相对论。我想,在我的一生中,就这一次,我要真正理解这些深奥结果中的一个。
阿德曼决定读研究生,并深入理解库尔特·弗雷德里希·哥德尔的定理,而不是停留在表面。然而,在研究生院期间,他经历了另一件事——他终于领悟了数学的真正本质和引人入胜的美。他发现那就是“... less related to accounting than it is to philosophy”。
人们把数学看作某种实用技艺,……当你成为一名数学家时,关键就在于你以某种方式看透这一点,看到数学的美与力量。
1976年,阿德曼完成了他的学位论文“Number Theoretic Aspects of Computational Complexities”,获得了博士学位,并立即在麻省理工学院谋得数学助理教授的职位。(他的父亲建议他留在美国银行,至少那里有不错的退休计划)。阿德曼在麻省理工学院的同事之一是Ronald Rivest,他的办公室就在隔壁。Rivest被斯坦福大学计算机科学家Martin Hellman及其学生Whitfield Diffie在The IEEE Transactions on Information Theory上发表的一篇文章所吸引(见[2])。他们在文中描述了一种新型加密系统的构想。它基于引入新的秘密“密钥”——用于加密和解密消息的数学公式。在此之前,任何拥有加密密钥的人只需逆向执行加密指令就能解密。Hellman和Diffie提出的是相当革命性的想法——使用单向函数或数学公式,这些函数在一个方向上容易计算,但除非事先知道它们是如何构造的,否则在反方向上不可能做到。加密密钥可以公开,这样任何人都可以发送编码消息。但只有拥有密钥实际构造的人才有解密密钥,从而能够解码。
Rivest宣布将找到这样一种单向函数,从而创造出公钥密码系统。这个想法本身显然是可行的,但找到一个真正的单向函数似乎是一项艰巨的任务。Rivest有一位同样热情的支持者——他的同事Adi Shamir。然而阿德曼却不那么兴奋——他认为这个想法很不切实际,不值得追求。然而很快,Rivest和Shamir开始发明编码系统,阿德曼同意通过尝试破解每个系统来测试它们。两人提出了42种不同的编码系统,每次阿德曼都能破解。在第43次尝试中,基于一个困难的因子分解问题,阿德曼承认由于所涉及的数学,该密码确实无法破解,并且分解可能需要几个世纪的计算。Rivest彻夜未眠,准备描述该密码的手稿,然后交给阿德曼。他按字母顺序列出了论文作者——阿德曼、Rivest、Shamir。阿德曼表示异议:-
我告诉Ron,“把我的名字从论文中去掉。这是你的工作”。
但Rivest坚持,最终说服了他。
我想,‘好吧,这将是我参与过的最不重要的一篇论文,但几年后我需要简历上有足够多的条目来获得终身教职,……另一方面,我确实做了大量的智力工作来破解密码1到42。所以合理的做法是成为第三作者。’
马丁·加德纳在他的专栏中写到了这个密码,现在以相关人物的名字命名为RSA(见[3]),令阿德曼大为惊讶的是,他们和这个密码的名声迅速传播开来。大量信件涌入,而在此之前唯一研究加密技术的国家安全局(NSA)表示担心,像RSA这样看似不可破解的密码的发表可能会危及国家安全!
Rivest、Shamir和阿德曼将他们的密码专利转让给了MIT,并于1983年成立了一家公司,加利福尼亚州雷德伍德城的RSA Data Security Inc.,以制造RSA计算机芯片。阿德曼被任命为总裁,Rivest为董事会主席,Shamir为财务主管。1996年,该公司以2亿美元出售。
MIT为阿德曼提供了激发智力的氛围,但他渴望加利福尼亚,他想在那里定居并组建家庭。因此,他于1980年在洛杉矶的南加州大学找到了一份工作(他现在是那里的Henri Salvatori计算机科学讲席教授和分子生物学教授)。三年后,他在一次单身舞会上遇到了未来的妻子Lori Bruce。他们一见钟情,六周后结婚。
同年,阿德曼与R S Rumely和C Pomerance发表了一篇论文,描述了一种用于区分素数与合数问题的‘近乎多项式时间’确定性算法。这是理论计算机科学中第一个发表在Annals of Mathematics上的结果(见[4])。
这一年还见证了计算机科学的一个里程碑式发展。南加州大学的研究生Fred Cohen提出了关于“a program that can 'infect' other programs by modifying them to include a possibly modified version of itself”的新想法。阿德曼是Cohen的导师,他一得知这个想法就立即确信它会奏效。他向Cohen提议将程序命名为‘病毒’,Cohen最终于1984年发表了他的第一篇病毒论文,并于1986年发表了关于同一主题的博士学位论文。
阿德曼生活中的一个关键转折点出现在90年代初,当时他将热情转向免疫学领域。他对免疫学兴趣日益增长的原因之一是免疫学中未解决的问题“had the kind of beauty mathematicians look for”[5]。阿德曼很快专注于研究称为T淋巴细胞的白细胞,这些细胞在艾滋病患者中的稳步下降使他们容易受到致命感染。T细胞主要分为两种类型——CD4和CD8。在健康和新感染者中,每立方毫米血浆中大约有800个CD4 T细胞。然而,在与艾滋病相关的长达十年的潜伏期内,这个数字逐渐下降。通常,在CD4细胞计数降至200以下后,艾滋病特征性感染就会开始。然而,“losing a T cell is not like losing an arm or a leg”[5]。人体,即使是HIV感染者的人体,也可以通过制造新的T细胞来补充T细胞计数。为什么HIV感染患者的CD4 T细胞群会缩小,这相当神秘。
阿德曼和其他人提出,问题在于监测T细胞水平的稳态机制——它不区分CD4和CD8细胞。因此,每当它检测到T细胞丢失时,稳态机制就会同时生成CD4和CD8细胞以恢复T细胞总数。然而,CD8细胞的增加有效地抑制了CD4细胞的产生,因此HIV继续攻击CD4,从而降低其数量。正如阿德曼所说[5]:-
稳态机制……是盲目的。
阿德曼和旧金山加利福尼亚大学的弗洛伦斯·南丁格尔·大卫 Wofsy在1993年2月的Journal of Acquired Immune Deficiency Syndromes(JAIDS)上描述了他们对这一假说的检验(见[6])。遗憾的是,艾滋病研究界对阿德曼想法的回应并不令人鼓舞。阿德曼并未因此气馁,他决定更深入地了解HIV的生物学,以便成为更有说服力的倡导者。他进入南加州大学的分子生物学实验室,在Nickolas Chelyapov(现为阿德曼自己实验室的首席科学家)的指导下开始学习现代生物学的方法。
对阿德曼来说,这是一段密集学习的时期,他早先对生物学的看法正在经历重大转变。他解释了原因[7]:-
生物学如今是研究储存在DNA中的信息——由四个字母组成的字符串:A、T、G和C,分别代表碱基腺嘌呤、胸腺嘧啶、鸟嘌呤和胞嘧啶——以及这些信息在细胞中经历的变化。这里面有数学!
他开始阅读经典教材The Molecular Biology of the Gene,该书由因沃森-克里克模型而闻名的詹姆斯·D·沃森(见[13])合著。阿德曼生动地叙述了他研究一种相当特殊的酶[7]的描述时的情景:-
一天深夜,我躺在床上读沃森的教材,读到对DNA聚合酶的描述。这是酶之王——生命的制造者。在适当条件下,给定一条DNA链,DNA聚合酶会产生第二条“沃森-克里克”互补链,其中每个C都被G取代,每个G都被C取代,每个A都被T取代,每个T都被A取代。例如,给定一个序列为CATGTC的分子,DNA聚合酶将产生一个序列为GTACAG的新分子。聚合酶使DNA能够复制,进而使细胞能够复制,最终使你能够繁殖。对于严格的还原论者来说,DNA聚合酶对DNA的复制就是生命的全部意义。
他继续写道:-
DNA聚合酶是一台令人惊叹的小型纳米机器,一个单分子“跳”到一条DNA链上并沿着它滑动,“读取”它经过的每个碱基,并将其互补碱基“写”到一条新的、正在生长的DNA链上。
这是阿德曼顿悟的时刻:-
阿德曼当时正在思考“艾伦·图灵机”。
他的机器有一个版本由一对纸带和一个称为有限控制器的机制组成,该机制沿着“输入”纸带移动读取数据,同时沿着“输出”纸带移动读取和写入其他数据。有限控制器可以用非常简单的指令编程,人们可以轻松编写一个程序,在输入纸带上读取一串A、T、C和G,并在输出纸带上写出Watson-Crick互补串。与DNA聚合酶的相似性几乎再明显不过了。
甚至还有更多是真的:-
但有一条重要信息使这种相似性真正引人注目:图灵的玩具计算机被证明是通用的——尽管它很简单,但可以通过编程来计算任何可计算的东西。(这个概念本质上是著名的“丘奇论题”的内容。)换句话说,人们可以编程一个图灵机来产生Watson-Crick互补串、分解数字、下棋等等。
阿德曼几乎无法抑制他的兴奋:-
这一认识让我从床上坐了起来,对妻子洛里说:“天哪,这些东西可以计算。”那一夜我再没睡着,一直在想办法让DNA来解决问题。
他欣然决定制造一台DNA计算机,类似于艾伦·图灵机,但用酶取代有限控制器。十年前,IBM研究员Charles H. Bennet和Rolf Landauer已提出过基本类似的想法(见[8]),但当时还不确定是否存在既能产生Watson-Crick互补链又能执行其他数学功能的酶。阿德曼希望他的DNA计算机至少能做一些像下棋一样有趣的事情。为此,他开始学习DNA化学的基本工具,如聚合酶、连接酶、凝胶电泳、DNA合成等。商业DNA可根据特定要求定制且易于获得,这对他的目的帮助极大。
现在可以在纸上写下一段DNA序列,寄给商业合成机构,几天后就能收到一个试管,其中含有大约分子数量的DNA,全部(或至少大部分)具有所描述的序列。……这些分子以干燥形式装在小管中交付,看起来是一小团白色无定形块状物。
理论上,建造一台能计算任何可计算问题的计算机只需要两样东西——一种存储信息的方法以及作用于信息的简单操作。DNA本身就是信息的存储库(它包含‘生命的蓝图’!),而像聚合酶这样的酶已被用来操作这些信息。阿德曼知道他已经拥有足够的东西来建造一台通用计算机。
接下来他必须做的是选择一个他的DNA计算机能够解决的问题。阿德曼决定选择哈密顿路径问题。
……给定一个有向边图以及指定的起始顶点和终止顶点,当且仅当存在一条从起始顶点出发、在终止顶点结束并恰好经过其余每个顶点一次的路径时,称存在一条哈密顿路径。哈密顿路径问题就是对于任何给定起始和终止顶点的图,判定是否存在哈密顿路径。
尽管哈密顿路径问题已被广泛研究,但求解它的高效算法仍未出现。20世纪70年代初的研究表明,该问题根本不可能存在高效算法(证明这一点至今仍是一个未解决的问题!)。事实上,它属于一类更大的问题,称为“NP完全”问题。然而,仍有如下一些算法可以奏效:
给定一个有向图,有个顶点,起点为,终点为,
插图:Adleman.gif ↗
尽管这个算法效率不高,但只要路径生成得足够随机,并且所得集合足够大,它就能给出相当正确的结果。阿德曼在他的第一次DNA计算中使用的正是这个算法。对于他的哈密顿路径问题,他选择了以下有向图:
在这个图中,哈密顿路径的起点和终点分别是0和6。阿德曼首先为图中的每个顶点和每条边分配了一个随机的DNA序列(这些序列被称为寡核苷酸)。由于每个DNA序列都有其Watson-Crick互补序列,每个顶点都关联着它的互补序列。一旦编码确定下来,顶点对应的互补DNA序列和边对应的序列就被合成出来。剩下的步骤最好由阿德曼本人来描述:-
我取了一小撮(大约个分子)每种不同的序列,把它们放入一个共同的试管中。为了开始计算,我只是加入了水——再加上连接酶、盐和少量其他成分,以近似细胞内的条件。总共只用了大约五十分之一茶匙的溶液。在大约一秒钟内,我手中就有了哈密顿路径问题的答案。
阿德曼随后不得不进行一个相当繁琐的实验,通过这个实验他必须剔除大约100万亿个编码非哈密顿路径的分子。他实现了上述算法这一事实意味着,在执行完所有前面的步骤之后,试管中剩下的任何DNA都必然编码所需的哈密顿路径。最终,阿德曼花了七天时间在分子生物学实验室里完成了世界上第一次DNA计算。
阿德曼在Science1994年11月号上报告了他的这一杰出发现(见[9]),如今他被恰如其分地誉为“DNA计算之父”。分子计算是当代科学研究中最令人兴奋的领域之一,在阿德曼的实验之后的几年里,它见证了一些引人注目的突破。1995年,普林斯顿大学的Richard J. Lipton提出了(见[10])另一个著名的“NP完全”问题——即所谓“满足”问题(SAT)——的DNA解法。2002年,由以色列雷霍沃特魏茨曼科学研究所的Ehud Shapiro领导的一个研究团队设计出一种由酶和DNA分子组成的分子计算机器,它每秒可执行330万亿次操作,比最快的个人计算机还要快100,000倍以上。几个月内,同一个团队就在他们先前模型的基础上改进出一种新模型,其中DNA输入同时也是机器的燃料来源(见[12])。《吉尼斯世界纪录大全》承认这台计算机是迄今建造过的“the smallest biological computing device”[11]。
这类DNA计算设备在制药和生物医学领域具有革命性的意义。科学家们预见到一个未来,那时微小的DNA计算机将能够监测我们的健康状况,并释放正确的药物来修复受损组织。Shapiro [11]说:-
自主生物分子计算机或许能够作为“细胞中的医生”工作,在活细胞内运行并感知宿主的异常……通过查询其编程的医学知识,计算机可以通过合成并释放药物来对异常做出反应。
大卫 Hawksett,吉尼斯世界纪录的科学评委,恰如其分地指出[11]:-
这是一个让科幻作家也难以跟上的研究领域。
这种‘细胞中的医生’的分子计算愿景,只是科学家们正在大力追求的众多愿景之一,他们现在是新‘分子科学’的执火炬者,这门科学试图深入探索生命隐藏的奥秘。确实引人注目的是,看似迥异却同样多产的生物学和数学领域的结合催生了这样一项事业。在这个专业分工激烈的时代,同样令人鼓舞的是,这一切是由一位数学家开始的。也许有一天我们能够证明阿德曼的愿景[7]:-
在过去半个世纪里,生物学和计算机科学蓬勃发展,毫无疑问,它们将成为新千年我们科学和经济进步的核心。但生物学和计算机科学——生命与计算——是相关的。我相信,在它们的交界处,伟大的发现正等待着那些寻求它们的人。
Leonard Adleman's father was an appliance salesman, his mother a bank teller. As a young boy growing up in San Francisco, Adleman had little ambition, far less of becoming a mathematician. By his own admission, he was [1] "incredibly naive and immature". However, it was his high school English teacher who made him realize the beauty of ideas through a reading of Hamlet. It was at the suggestion of this teacher who had opened his eyes "to the fact that one could see things more deeply than the purely superficial" that Adleman enrolled at the University of California at Berkeley. Still hesitant and undecided, he first declared to be a chemist (inspired by years of watching Mr.Wizard on television), then a doctor (inspired by his Kappa Nu fraternity brothers) before settling on a mathematics major. [1]
I had gone through a zillion things and finally the only thing that was left where I could get out in a reasonable time was mathematics.
It took him five years to finally graduate in 1968 when he took a job as a computer programmer at the Bank of America. Soon after, he applied to medical school where he was accepted but he changed his mind and did not enroll. He decided instead to be a physicist and began taking classes at the San Francisco State College while working at the bank. Once again he lost interest.
I didn't like doing experiments, I liked thinking about things.
Adleman eventually returned to Berkeley for pursuing a PhD in computer science. He had two motivations, the first being practical:-
I thought that getting a PhD in computer science would at least further my career.
The second was more romantic. Martin Gardner had written an article on Gödel's theorem in Scientific American which overwhelmed Adleman with its deep philosophical implications:-
I thought 'Wow. This is so neat.' There were several things I found neat - black holes, general relativity. I thought for once in my life, I want to really understand one of these deep results.
Adleman decided to join graduate school and come away with an understanding of Gödel's theorem at a level beyond the superficial. However, while in graduate school, something else happened to him -- he finally understood the true nature and compelling beauty of mathematics. He discovered that it was "... less related to accounting than it is to philosophy."
People think of mathematics as some kind of practical art, ... the point when you become a mathematician is where you somehow see through this and see the beauty and power of mathematics.
In 1976, Adleman completed his thesis "Number Theoretic Aspects of Computational Complexities", received his PhD, and immediately secured a job as an assistant professor of mathematics at MIT. (His father advised him to stay with the Bank of America where atleast they had a good retirement plan). One of Adleman's colleagues at MIT was Ronald Rivest who had his office next door. Rivest had been gripped by an article in The IEEE Transactions on Information Theory written by Martin Hellman, a computer scientist at Stanford, and his student Whitfield Diffie (see [2]). In it, they had described an idea for a new kind of encryption system. It was based on introducing new secret "keys" -- mathematical formulas for scrambling and unscrambling messages. Up until then, anyone in possession of an encrypting key could also decrypt by simply reversing the encryption instructions. What Hellman and Diffie proposed was quite revolutionary -- use one-way functions or mathematical formulas that are easy to compute in one direction but impossible to do in the reverse unless one knew how they were constructed in the first place. The encryption key could be made public so that anyone could send an encoded message. But only someone having the actual construction of the key would have the decryption key and thus be able to decode it.
Rivest announced that such a one-way function would be found which would lead to the creation of a public key cryptosystem. The idea itself was manifestly workable but finding a truly one-way function seemed a formidable task. Rivest had an equally enthusiastic supporter in one of his colleagues -- Adi Shamir. Adleman however was less than excited -- he thought the idea was quite impractical and unworthy of pursuing. Soon however, Rivest and Shamir were inventing coding systems and Adleman agreed to test each of the systems by trying to break it. The duo came up with 42 different coding systems and each time Adleman was able to break it. On the 43rd attempt, based on a difficult factoring problem, Adleman confessed that the code was really unbreakable because of the mathematics involved and could presumably take centuries of computation to factor. Rivest stayed up all night, preparing the manuscript describing the code before he handed it to Adleman. He had listed the paper's authors in alphabetical order - Adleman, Rivest, Shamir. Adleman demurred:-
I told Ron, 'Take my name off the paper. It's your work'.
But Rivest insisted and eventually prevailed upon him.
I thought, 'Well, it's going to be the least important paper I've ever been on, but in a few years I will need so many lines on my vita to get tenure, ... on the other hand, I did do a substantial amount of intellectual work breaking the codes 1 through 42. So the reasonable thing to do is be the third author'.
Martin Gardner wrote about the code, now called RSA after the persons involved, in his column (see [3]) and much to Adleman's astonishment, their fame and that of the code spread rapidly. A barrage of letters poured in and the National Security Agency (NSA), hitherto the only place where encryption was studied, expressed fears that the publication of seemingly unbreakable codes like RSA might potentially jeopardise national security!
Rivest, Shamir and Adleman assigned the patent for their code to MIT and in 1983 formed a company, RSA Data Security Inc. of Redwood City, California, to make RSA computer chips. Adleman was made president, Rivest chairman of the board and Shamir the treasurer. In 1996, the company was sold for $200 million.
MIT provided Adleman with an intellectually stimulating atmosphere but he yearned for California where he wanted to settle down and have a family. Accordingly, he took up a job at the University of Southern California in Los Angeles (where he is presently the Henri Salvatori Professor of Computer Science and Professor of Molecular Biology) in 1980. Three years later, he met his future wife Lori Bruce at a singles dance. It was love at first sight and the couple got married six weeks later.
In that same year, Adleman, along with R S Rumely and C Pomerance, published a paper describing a 'nearly polynomial time' deterministic algorithm for the problem of distinguishing prime numbers from composite ones. It was the first ever result in theoretical computer science to be published in Annals of Mathematics (see [4]).
The year also witnessed a landmark development in computer science. Fred Cohen, a graduate student at USC, put forth a new idea regarding "a program that can 'infect' other programs by modifying them to include a possibly modified version of itself". Adleman, who was Cohen's supervisor, was immediately convinced that the idea would work the moment he learned about it. He proposed the name 'virus' for the program to Cohen who eventually published his first virus paper in 1984 and his PhD dissertation on the same topic in 1986.
A key turning point in Adleman's life came during the early 90's when he directed his enthusiasm towards the field of immunology. One of the reasons for his growing interest in it was that unsolved problems in immunology "had the kind of beauty mathematicians look for"[5]. Adleman was soon preoccupied with the study of white blood cells called T lymphocytes whose steady decline in AIDS patients leave them vulnerable to lethal infections. The T cells are primarily of two types - CD4 and CD8. There are about 800 CD4 T cells in each cubic millimeter of blood plasma in healthy and newly infected persons. This number however, declines gradually during the decade-long latency period associated with AIDS. Typically, after CD4 cell count drops below 200, infections characteristic of AIDS set in. However, "losing a T cell is not like losing an arm or a leg"[5]. The human body, even that of an HIV-infected person, can replenish the T cell count by making new ones. It was quite mysterious why CD4 T cell population shrank in HIV-infected patients.
Adleman and others suggested that the problem lay in the homeostatic mechanism which monitors the levels of T cells - it does not distinguish between CD4 and CD8 cells. Thus every time it detects the loss of T cells, the homeostatic mechanism generates both CD4 and CD8 cells to restore the total T cell-count. However, addition of CD8 cells effectively suppresses the production of CD4 cells and consequently HIV continues attacking CD4, thus lowering its count. As Adleman put it [5]:-
The homeostatic mechanism ... is blind.
Adleman and David Wofsy of the University of California at San Francisco described their test of the hypothesis in the February 1993 issue of Journal of Acquired Immune Deficiency Syndromes (JAIDS)(see [6]). Unfortunately, the AIDS research community's responses to Adleman's ideas were less than encouraging. Undeterred, Adleman decided to acquire a deeper understanding of the biology of HIV in order to be a more persuasive advocate. He entered the molecular biology lab at USC and began to learn the methods of modern biology under the guidance of Nickolas Chelyapov (now chief scientist in Adleman's own laboratory).
It was a period of intense learning for Adleman whose own earlier views on biology was undergoing a significant transformation. He explains why [7]:-
Biology was now the study of information stored in DNA -- strings of four letters: A, T, G and C for the bases adenine, thymine, guanine and cytosine -- and of the transformations that information undergoes in the cell. There was mathematics here!
He began reading the classic text The Molecular Biology of the Gene, co-authored by James D. Watson (see [13]) of Watson-Crick fame. Adleman vividly recounts the time he studied the description of a rather special enzyme [7]:-
Late one evening, while lying in bed reading Watson's text, I came to a description of DNA polymerase. This is the king of enzymes - the maker of life. Under appropriate conditions, given a strand of DNA, DNA polymerase produces a second "Watson-Crick" complementary strand, in which every C is replaced by a G, every G by a C, every A by a T and every T by an A. For example, given a molecule with the sequence CATGTC, DNA polymerase will produce a new molecule with the sequence GTACAG. The polymerase enables DNA to reproduce, which in turn allows cells to reproduce and ultimately allows you to reproduce. For a strict reductionist, the replication of DNA by DNA polymerase is what life is all about.
He continues:-
DNA polymerase is an amazing little nanomachine, a single molecule that "hops" onto a strand of DNA and slides along it, "reading" each base it passes and "writing" its complement onto a new, growing DNA strand.
It was Adleman's moment of epiphany:-
While lying there admiring this amazing enzyme, I was struck by its similarity to something described in 1936 by Alan Turing, the famous British mathematician.
Indeed, Adleman was thinking about the "Turing machine".
One version of his machine consisted of a pair of tapes and a mechanism called a finite control, which moved along the "input" tape reading data while simultaneously moving along the "output" tape reading and writing other data. The finite control was programmable with very simple instructions, and one could easily write a program that would read a string of A, T, C and G on the input tape and write the Watson-Crick complementary string on the output tape. The similarities with DNA polymerase could hardly have been more obvious.
Even more was true:-
But there was one important piece of information that made this similarity truly striking: Turing's toy computer had turned out to be universal - simple as it was, it could be programmed to compute anything that was computable at all. (This notion is essentially the content of the well-known "Church's thesis".) In other words, one could program a Turing machine to produce Watson-Crick complementary strings, factor numbers, play chess and so on.
Adleman could hardly contain his excitement:-
This realization caused me to sit up in bed and remark to my wife, Lori, "Jeez, these things could compute." I did not sleep the rest of the night, trying to figure out a way to get DNA to solve problems.
He readily decided to make a DNA computer similar to a Turing machine with an enzyme replacing the finite control. A decade earlier, IBM researchers Charles H. Bennet and Rolf Landauer had suggested essentially similar ideas (see [8]) but there was uncertainty regarding the existence of enzymes which not only produced Watson-Crick complements but were able to perform other mathematical functions as well. Adleman wanted his DNA computer to perform something at least as interesting as playing chess. To this end, he began learning the essential tools of DNA chemistry like polymerases, ligases, gel electrophoresis, DNA synthesis etc. The fact that commercial DNA, tailor-made to specific requirements, was readily available was more than helpful for his purpose.
It is now possible to write a DNA sequence on a piece of paper, send it to a commercial synthesis facility and in a few days receive a test tube containing approximately molecules of DNA, all (or atleast most) of which have the described sequence. ... The molecules are delivered dry in a small tube and appear as a small, white, amorphous lump.
Theoretically, only two things were needed to build a computer capable of computing anything computable - a method by which information was stored and simple operations which acted on it. DNA itself was a storehouse for information (it contains the 'blueprint of life'!) while enzymes like polymerases had been used to operate on this information. Adleman knew he had enough to build a universal computer.
The very next thing he had to do was to select a problem which his DNA computer would be able to solve. Adleman decided upon the Hamiltonian Path Problem.
... given a graph with directed edges and a specified start vertex and end vertex, one says there is a Hamiltonian path if and only if there is a path that starts at the start vertex, ends at the end vertex and passes through each remaining vertex exactly once. The Hamiltonian Path Problem is to decide for any given graph with specified start and end vertices whether a Hamiltonian path exists or not.
Although the Hamiltonian Path Problem has been studied extensively, an efficient algorithm to solve it is yet to emerge. It was shown during the early 1970's that no efficient algorithm for the problem is at all possible (proving it is still an open problem!). In fact, it belongs to a larger class of problems known as "NP-complete" problems. However, there are algorithms such as the following which work nevertheless:
Given a directed graph with vertices, having start vertex and end vertex ,
插图:Adleman.gif ↗
Though not an efficient one, this algorithm gives reasonably correct results provided paths are generated randomly enough and the resulting sets are large enough. It was precisely this algorithm which Adleman used in his first DNA computation. For his Hamiltonian Path Problem, he chose the following directed graph:
In this graph, the start and end vertices for the Hamiltonian path are respectively 0 and 6. Adleman first assigned a random DNA sequence to each vertex and edge in the graph (the sequences are known as oligonucleotides). Because each DNA sequence has its Watson-Crick complement, each vertex is associated with its complement sequence. Once the encodings were set in place, the complementary DNA sequences for the vertices and the sequences for the edges were synthesized. The remaining procedures are best described by Adleman himself:-
I took a pinch (about molecules) of each of the different sequences and put them into a common test tube. To begin the computation, I simply added water - plus ligase, salt and a few other ingredients to approximate the conditions inside a cell. Altogether only about one fiftieth of a teaspoon of solution was used. Within about one second, I had the answer to the Hamiltonian Path Problem in my hand.
Adleman had to then perform a rather tedious experiment by which he had to weed out about a 100 trillion molecules that encoded non-Hamiltonian paths. The fact that he implemented the algorithm described above meant that any DNA remaining in the test tube after every preceding steps were carried out should necessarily encode the desired Hamiltonian path. In the end, it took Adleman seven days in the molecular biology lab to perform the world's first DNA computation.
Adleman reported his brilliant discovery in the November 1994 issue of Science (see [9]) and he is now rightly hailed as the 'father of DNA computation'. One of the most exciting fields in contemporary scientific research, molecular computation has witnessed some remarkable breakthroughs in the years following Adleman's experiment. In 1995, Richard J. Lipton at Princeton University proposed (see [10]) a DNA solution to another famous 'NP-complete' problem - the so-called "satisfaction" problem (SAT). In 2002, a research team led by Ehud Shapiro at the Weizmann Institute of Science in Rehovet, Israel devised a molecular computing machine composed of enzymes and DNA molecules which could perform 330 trillion operations per second, more than 100,000 times the speed of the fastest PC. Within months, the same team improved on their previous model with one in which the DNA input is also the source of fuel for the machine (see [12]). The Guinness Book of Records recognized the computer as 'the smallest biological computing device'[11] ever constructed.
Such DNA computing devices have revolutionary implications in the pharmaceutical and biomedical fields. Scientists foresee a future where tiny DNA computers would be able to monitor our well-being and release the right drug to repair damaged tissues. Says Shapiro [11]:-
Autonomous bio-molecular computers may be able to work as 'doctors in a cell', operating inside living cells and sensing anomalies in the host ... Consulting their programmed medical knowledge, the computers could respond to anomalies by synthesizing and releasing drugs.
David Hawksett, the science judge at the Guinness World Records, puts it aptly [11]:-
This is an area of research that leaves the science fiction writers struggling to keep up.
This 'doctor-in-a-cell' vision for molecular computation is only one of many others being vigorously pursued by scientists who are now the torchbearers of the new 'molecular science' which attempts to penetrate deep into the hidden mysteries of life. It is indeed remarkable that the marriage of the seemingly disparate yet equally fecund fields of biology and mathematics has fostered such an enterprise. No less inspirational, in this age of fierce specialization, is the fact that it was a mathematician who started it all. Perhaps someday we might vindicate Adleman's vision [7]:-
In the past half-century, biology and computer science have blossomed, and there can be little doubt that they will be central to our scientific and economic progress in the new millenium. But biology and computer science - life and computation - are related. I am confident that at their interface great discoveries await those who seek them.
正文里的方括号编号指向这里,悬停即可直接看到条目。书目保留原文——译了书名反而查不到文献。
原站列出的延伸阅读与外部数据库,照原样保留,目标多为英文页面。