北京海淀区科学院南路6号，是中国科学院计算技术研究所（下称“计算所”）。1956年8月，中国科学院决定，成立计算技术所等三个研究所筹委会，并建立半导体物理研究小组，中国第一个专门从事“计算机科学技术”的学术机构由此诞生。我国第一台通用数字电子计算机、我国高性能计算机的研发基地、我国首枚通用CPU芯片，都出自于此。计算所有一条准则：瞄准国家重大需求，开展研究和技术转移工作。很长一段时间，计算所都是我国的计算机人才高地，一大批年轻人代表国家新兴力量留学海外。其中一位，就是李明。1980年，李明成为科学院公派出国的第一批研究生。这年4月，李明前往美国密歇根三大高校联盟之一的韦恩州立大学（WSU），攻读计算机科学硕士。只用了8个月时间，李明取得WSU硕士学位。1981年，他赴康奈尔大学（Cornell）继续攻读计算机科学系。康奈尔大学是美国大学协会的十四个创始院校之一，著名的常春藤盟校八成员之一，李明在那里成为「计算复杂性」理论奠基人、图灵奖得主——Juris Hartmanis 的学生。Juris Hartmanis教授康奈尔大学的计算机科学系与Hartmanis有着重要渊源。五十年代，Hartmanis拿到博士学位后，曾在康奈尔大学数学系任教过一段时间，后加入通用电气公司的信息研究部，与Richard Stearns一起开辟了计算复杂性。直到1965年，Hartmanis才离开通用电气，重返康奈尔大学任教。但他没有回到数学系，而是负责筹建计算机科学系。Hartmanis的到来，随即吸引了一批著名计算学者加盟，J.E.Hopcroft（1986年图灵奖得主)、David Gries（1995年ACM优秀计算机教育奖获得者)、E.Horowitz、P.Wegner、A.Shaw，都慕名而来。李明加入时，Hartmanis带领的计算机科学系正值发展上升期。蔡进一、郭百宁、周礼栋后来也陆续来到了该校计算机系。Hartmanis任教的25年中，有21个博士研究生，李明是第13位。他延承了导师的的计算复杂性研究。博士期间，李明曾用Kolmogorov复杂性完全解决了Hartmanis-Stearns 20年前留下来的未解难题。此前，Michael O. Robin以及Zvi Galil等人曾做出部分进展，但一直没有人彻底解决该问题。李明创造了一个分析算法平均复杂性的新方法。他解释道，图灵机有一个单向输入带，而他用一个工作带，成功模拟出两个工作带的紧致时间下界，开创了Kolmogorov复杂性在计算机领域的应用。这个方法后来被李明和他的同事们用来解决诸多问题，如，Shellsort平均复杂性、Heapsort平均复杂性、Lovasz Local Lemma的新证明——多头有限状态自动机是否可以做字符串匹配，k个下推栈是否真的比k-1个好，等等。1985年3月，李明拿到博士学位后，去了俄亥俄州立大学的计算机科学与信息系任教一半年。同期，李明的中科院硕士同学李国杰也读完博士（1981年李国杰前往美国普渡大学攻读博士学位，师从美国计算机界的权威华云生教授），进入伊利诺伊大学CSL实验室工作。两年后，李国杰回到中科院计算所，开始了自己终身的科创事业。1986年，李明去往哈佛师从图灵奖得主——Les Valiant，做了一年的博士后。
Les Valiant教授Les Valiant是一位英国人，同样是计算机科学背景，求学和任教经历相当丰富。他先后在英国剑桥大学、伦敦帝国理工学院、华威大学的计算机科学系学习，此后在卡内基梅隆大学、利兹大学和爱丁堡大学任教。直到1982年，Valiant来到哈佛，在异国他乡开始了长期的教学生活。Valiant的一大贡献是1984年的论文《A Theory of the Learnable》，这让诞生于1950年代的机器学习第一次有了坚实的数学基础，对人工智能诸多领域包括加强学习、机器视觉、自然语言处理和手写识别等，都产生了巨大影响。在与Valiant做博士后度过一年后，李明先后在哈佛大学Aiken计算实验室和加拿大约克大学短暂任教。两年后的1989年，他以副教授的身份去了滑铁卢大学的计算机科学系，与彼时刚刚博士毕业的杨强成为同事。若干年后，杨强再赴他处就职，而李明留在了滑铁卢大学，1994年拿到终身教授职位，2009年成为校级教授（University Professor），并一直工作至今。滑铁卢大学计算机系和多伦多大学计算机系一直并列为加拿大第一名，但滑铁卢大学计算机专业从来都是加拿大理科学生的首选。在当地人心中，滑铁卢既是一座大学城，也是加拿大的高科技重镇。这所位于加拿大安大略省多伦多市西部、距离多伦多市区大约100公里的学校，创建于二战后的1957，其初衷就是为加拿大的经济建设培养人才。正因如此，学校非常注重工程学科的建设和发展，尤其是计算机科系和工程系，学校更是倾其全力发展，并以全面的Co-op系统（Cooperative Education Program，指“带薪实习课程”）而世界闻名。时至今日，这两大系仍是滑铁卢大学的学术根基。在这里，李明迎来了自己研究生涯的第一个“转型期”。 02“误入”生信深处
在与雷峰网的对话中，李明坦言：“完全是误打误撞做起了生物学问题。”在滑铁卢开始独立研究后，这位在计算机科学道路上近乎一路直线前进的学者，绝想不到自己会有一天与人类基因组计划产生联系。1985年，人类基因组计划提出。这份史无前例的全人类的合作计划，不到五年时间就完成了全部的准备工作。1990年，美国正式启动了该计划。投资30亿美元，用15年时间，破译组成人体约2.5万个基因的30亿个碱基对，绘制出关于人类基因的遗传图、物理图、排序图、转录图等所有图谱。换言之，美国试图用“1美元1个碱基对”的预算，破译一本“生命天书”。然而，这30亿碱基对相当于30亿阶楼梯，要按照正确的顺序排列完成，工程之浩大难以想象，被称为美国历史上的“第三大工程”（第一大工程为1944年的曼哈顿原子弹计划，第二大工程为1969年的阿波罗登月计划）。然而，人体基因组计划的意义及复杂程度史无前例。一旦揭开了基因的奥秘，人类将获悉生命的种族、血型、孕育、生长、凋亡等过程的全部信息。这也是为什么美、英、法、德、日和中国等六国的科学家，要共同参与这项国际性科研的原因。一场对人类终极奥秘的探索，以1990年作为了分水岭。在《生物信息学三十年》系列专题中曾提到，徐鹰、许东二人就是在这个时候参与到人类基因组计划中，他们建立了各种生物数据库，开发各种检索工具，并在DNA和蛋白质序列分析方面，合作做出了那个年代最好用的算法工具Prospect。1989年，李明来到滑铁卢大学，接触的第一个问题就是困扰了计算机科学十年的——最短超串的近似算法分析。他发现，这一抽象的理论研究能够解决当时科学界的一个实际问题—— DNA序列的组装Shotgun算法的精确度问题。用现在的眼光和影响来看，李明的这一发现恰逢其时。基因组测序的困难在于，当时的技术无法准确读取长链，“读取”技术仅能够有效地读取较短的链。于是，科学家们决定将长链切成较短的碎片进行测序，最后在所有测序完成后，再拼装片段形成完整的DNA。当时应用最广的一种技术为“快速标签测序法”，被多国合作小组所承包。但没想到的是，在人类基因组计划启动后，这项研究不仅迅速席卷多国，同时也扩散到诸多私营性质的基因研究机构中。其中，最具代表性的就是的文特尔（J. C. Venter），他在1991年提出“霰弹枪法”的测序技术，目的是将一个细胞的所有基因复制多次，粉碎成无数个DNA小片段，再把大量基因测序工作交给计算机，从而大大加快DNA测序速度。一旦成功，他将把基因测序商业化，申请基因成果专利。一场公私之间的竞争，在三十年前拉开帷幕。J. C. Venter李明身在计算机科学领域，却发现了一个关键问题。他注意到，霰弹枪法虽然大幅度提高了测序速度，但也造成了众多重合度过高的碎片，导致原序列重建时速度降低。因此，只需要在大量的碎片中找到有最大重合的碎片，就可以像玩拼图游戏一样，将基因组还原，组装速度大大加快。这也就引出了“最短超串（shortest superstring)解决法”。1990年，李明做出了长度为O(n log n) 的超串来逼近长度为n的最短超串，成果发表至计算机科学领域的顶级会议期刊FOCS。一年后，李明找到在加拿大麦克马斯特大学任教的姜涛，以及从荷兰来的访问学生John Tromp，合作钻研这一问题。三人相距不远，同在加拿大安大略省，开车一小时的距离。频繁交流中，姜涛解决了修改过的贪婪算法的线性解。正在此时，三人发现MIT的Avrim Blum、贝尔实验室的Mihalis Yannakakis，也在钻研这一问题，并且也独立得到了修改过的贪婪算法线性解。“分头做不如合作”，李明表态，五人一拍即合，最后由李明解决了原始贪婪算法的线性解，并合作发布了一篇STOC论文《 Linear approximation of shortest superstrings》。无意中，李明这一为期两年的研究，为人类基因组测序方法提供了理论依据，为这一全人类的科研项目添了一把火。后续，这一证明被收录至众多计算生物教科书中，其中影响最为广泛的一本，就是1995年被Michael S. Waterman（生物信息学和计算生物学的奠基人之一）收录至个人所著的《Introduction to Computational Biology：Maps, sequences and genomes》。不过，对于这项成果，李明表现得相当淡然。他向雷峰网说到，“完全是误打误撞，我们把一个计算理论的问题解决了，属于先有了锤子再找钉子，结果可以用在生物学上，挺好玩，我们就开始做计算生物学了。”也正是在这几篇论文之后，李明走向了生物信息学。1995年，李明和时任明尼苏达大学计算机系教授的堵丁柱，决定回国创办一个计算机和算法相关的会议。
