计算分子生物学--算法逼近

1985年，我正在俄罗斯的莫斯科找工作，当时我正面临着一个困难的选择。一方面我在一个颇有声望的电子工程研究所获得了一个从事应用组合学研究的职位，另一方面，在莫斯科郊外的俄罗斯生物技术中心NIIGENETIKA，当时正在组建一个计算生物学小组。后一份工作的薪水是前一份的一半，而且连每周的食品包裹“zakaz”也没有，“zakaz”在当时食品匮乏的莫斯科是最重要的工作福利。我至今还不知道电子工程研究所中的人做的是哪种机密研究，因为在我没有签订保密协议之前，他们是不准泄露的。相反，NIIGENETIKA的Andrey Mironov则花了几个小时和我谈了一个崭新的超前的学科——计算分子生物学中的算法问题，于是我选择了NIIGENETIKA。我从没后悔过我的选择，虽然在一段时间里我不得不在莫斯科火车站收集空瓶子来补贴我在NIIGENETIKA的收入，在改革前的莫斯科，收集空瓶子是为数极少的挣外快的合法途径之一。
计算生物学对我而言是一门新的学科，我每个周末都泡在莫斯科列宁图书馆，那是惟一能找到计算生物学论文的地方。当时可用的书仅有Sankoff和Kruskal那本经典的“Time Warps，String Edits and Biomolecules：The Theory and Practice of Sequence Comparison”。由于1985年莫斯科实际上还没有供使用的复印机，我几乎把这本书的每一页都抄在了笔记本上。半年以后我意识到我已经看完了世界上所有的或几乎所有的计算生物学论文。哈，这不是什么了不起的事,这些论文中的一大部分是计算分子生物学的创立者David Sankoff和Michael Waterman写的，而且只有六本期刊需要细看。在接下来的7年里，我每个月去一次图书馆，阅读计算生物学这个领域中发表的所有文献。这样的情形没有持续很久。1992年，我察觉到计算生物学开始蓬勃发展了，因为我第一次没有时间看完所有已发表的计算生物学论文。
由于有些期刊连列宁图书馆也没有收藏，于是我向国外科学家发信索要文章，他们中的许多人好心地寄来了他们的文章预印本。1989年我收到了Michael Waterman寄来的沉重的包裹，里面有一沓即将出版的手稿。其中的一份用公式记述了一个未决问题，而我已经解出了此问题，我没有太担心证明过程就将我的解答寄给了Mike。后来Mike告诉我说，那封信是用非常“俄式的英语”写的，难以看懂，但是他对于有人能够通读他的论文一直到提出未决问题这一情节感到惊讶。不久之后，Mike邀请我去南加州大学和他一起工作，在1992年我讲授了我的第一堂计算生物学课。
本书是我在宾夕法尼亚州州立大学计算机科学系（1992～1995年）和南加州大学数学系（1996～1999年）讲授计算分子生物学课程的基础上完成的，它面向计算机科学专业和数学专业的研究生和高年级本科生。对生物信息学感兴趣的分子生物学家也会对本书的部分内容感兴趣。我也希望本书对计算生物学和生物信息学专业人员有所帮助。
本书的基本理论是阐述计算生物学中的算法思想，并说明了它们是如何同分子生物学和生物技术相联系的。为达到这个目的，本书有大量的“不含公式的计算生物学”内容，用简单的方式介绍了生物学动机和计算思想。这些对生物学和计算目标的简化叙述力求使进入这个新领域的计算机科学家和没有充分计算机技术背景的生物学家能够理解本书。例如，在“计算基因搜寻”一章中介绍了许多和搜寻囊肿性纤维化基因有关的计算问题，然后用公式表示了由这些问题导出的组合问题。每一章都有一节引言，叙述计算和生物学思想而无任何公式。本书着重于计算思想而非算法细节，并尽最大努力以简单的方式来介绍这些思想。毫无疑问，达到这一目标的惟一方法就是隐藏一些计算细节和生物学细节，但这在以后可能会被谴责为将计算生物学“卑俗化”。本书的另一个特点就是在每章的最后一节简要地叙述了一些超出本章内容的、重要的、最新的进展。
在计算机科学系开设的计算生物学课程通常先上２～３周的“简易分子生物学”导论。我注意到计算机专业的学生（通常对生物学一点儿也不懂）在一开始上生物学导论时如果不联系计算问题，他们的兴趣会很快减弱。如果给生物学家讲述算法而不联系实际的生物学问题，同样的情况也会发生。我发现同时介绍生物学和算法对保持学生在这方面的兴趣非常重要。“计算基因搜寻”一章符合这个目的，虽然这有意简化了生物学和算法的概念。我还发现有些计算生物学家没有清楚地看到计算生物学中不同领域之间的相互联系。例如，从事基因预测的研究人员可能对序列对比算法不甚了解。我尝试着去阐明计算分子生物学中不同领域所涉及的计算思想之间的联系。
本书的内容既包含了计算生物学中新兴的领域,也包含了其中一些相当老的领域。例如，“计算蛋白质组学”、“序列比较”和“DNA阵列”、“基因组重排”几章中的大部分内容还从未在其他的书中发表过。同时也有一些主题，比如在“限制酶切作图”一章中提到的是相当老的，其中所叙述的实验方法现在已经很少使用了。将这些相当老的计算思想包含在内的原因有两个：一是向新入门的人展示该领域中这些思想的来龙去脉，同时提醒他们计算生物学中的热点转移很快；二是这些计算思想常常在不同的应用领域里获得第二次生命。例如，限制酶切作图中那些几乎被遗忘的技术在计算蛋白质组学这个研究热点中得到新生。还有许多诸如此类的例子（比如一些和杂交测序有关的思想现在正用在大规模鸟枪法拼接上），所以我觉得同时包含老的和新的计算方法是重要的。
简要地谈一下本书中有关应用部分与理论部分间的孰轻孰重。毫无疑问，21世纪的生物学家必须要知道离散数学和算法的基本原理——至少能用公式来表示他们研究中导出的算法问题。在计算生物学中，将生物学问题恰当地公式化也许是研究中最困难的部分，至少和解这些问题同样困难。那么，我们如何教学生用计算术语来公式化地表示生物学问题呢？因为我不知道，所以我用一个故事代替。
20年前我从大学毕业，在莫斯科登了一则“数学咨询”的广告。我的客户主要是各个不同领域中的Cand.Sci.（俄语，类似于Ph.D.）学员，他们缺少良好的数学背景，为毕业证书（或至少是数学这部分）而希望得到帮助。我接触到从“机场清雪设备盘存的最优化”到“向特许经销商交付汽车的时间安排”大量不同领域的课题。在所有的项目中，最难的部分是断定这是一个怎样的计算问题并使其公式化，接下来的求解就是直接利用已有的方法了。
我永远忘不了一位来访者，他40来岁，彬彬有礼，体格健壮。他和别的客户不同，没有描述他的研究领域，而是让我解一个微分方程。一开始我很高兴，可结果却发现那个方程是没有意义的。要想出如何解决这个问题的惟一办法就是回到原始的应用问题并推导出一个新的方程。这位来访者对此有点踌躇，不过这是他获得Cand.Sci.学位的惟一办法，于是他开始透露一点他研究领域里的细节。到了最后，我领会到他研究的是让某个物体着陆在一个摇晃的平台上。这也使我明白了他为何从不给我他的电话号码，他是一位从事机密研究的军官，摇晃的平台是船，着陆的物体是飞机。我希望20年后揭露这个故事不会伤害他的军事生涯。
关于生物问题的公式化，大自然泄露的比那位军官还要少。此外，一些生物问题如果用足够多的公式来表示，则会变得太花哨，有时会遮蔽和掩盖计算思想。由于本书着重于计算思想而非技术细节，我有意用简化的公式来清楚地表达计算思想。这会使人感到本书太理论化，但我想不出别的方法来教授生物学中的计算思想。换句话说，要在真实的船上着陆真实的飞机之前，学生必须学会如何在玩具船上着陆玩具飞机。
我要强调一下，本书不打算一成不变地探讨计算生物学中的所有领域。当然，本书所选择的主题受我的爱好和研究兴趣的影响。计算生物学中的一些重大领域——其中大部分是值得注意的——没有在书中涉及，如DNA统计、遗传作图、分子进化、蛋白质结构预测和功能基因组。这些领域中的每一个都可以单独写成一本书，其中有些已经完成了。例如，Waterman在1995年写的书中【３５７】极好地介绍了DNA统计，Gusfield在1997年写的书中【１４５】详细地解释了字符串算法，Salzberg等在1998年写的书中【２９６】有几章全面地描述了蛋白质结构预测。Durbin等在1998年写的书【９３】和Baldi与Brunak在1997年写的书【２４】是着重于隐马氏模型和机器学习的专著。Baxevanis与Ouellette在1998年写的书【２８】是一本优秀的生物信息学实用指南，那本书更注重算法的应用而非算法本身。
我要感谢许多曾经教授给我计算分子生物学各方面知识的人。Andrey Mironov教导我的常识也许是任何应用研究中最重要的部分。当我从莫斯科来到洛杉矶的时候，Mike Waterman是我科学研究和生活上的最好的导师。尤其是他耐心地教导我，每一篇准备发表的论文都必须至少反复查看十几遍。虽然这个规矩使本书的出版延迟了几年，但我仍将它认真地传授给我的学生。我以前的学生Vineet Bafna和Sridhar Hannenhalli热心地教我他们所了解的知识，并加入了我这个艰难、长期的项目。我还要感谢Alexander Karzanov教我组合最优化，其中一些思想在我的计算生物学研究中非常有用。
我要感谢我的同事们和合著者：Mark Borodovsky，我和他共同研究过DNA统计，1985年他使我相信计算生物学有一个远大的前景；Earl Hubbell，Rob Lipshutz，Yuri Lysov，Andrey Mirzabekov和Steve Skiena是我做DNA阵列研究时的同事；Eugene Koonin，在第一个细菌基因组测序完成前，我就和他试着分析完整的基因组；Norm Arnheim，Mikhail Gelfand，Melissa Moore，Mikhail Roytberg和SingHoi Sze是我做基因搜寻时的同事；Karl Clauser，Vlado Dancik，Maxim FrankKamenetsky，Zufar Mulyukov和Chris Tang是我做计算蛋白质组学时的同事；Eugene Lawler，Xiaoqiu Huang，Webb Miller，Anaoly Vershik和Martin Vingron是我做序列比较时的同事。
我还要感谢许多同事，我和他们一起讨论计算分子生物学的各个方面，这都直接或间接地影响到本书：Ruben Abagyan，Nick Alexandrov，Stephen Altschul，Alberto Apostolico，Richard Arratia，Ricardo BaezaYates，Gary Benson，Piotr Berman，Charles Cantor，Radomir Crkvenjakov，KunMao Chao，Neal Copeland，Andreas Dress，Radoje Drmanac，Mike Fellows，Jim Fickett，Alexei Finkelstein，Steve Fodor，Alan Frieze，Dmitry Frishman，Israel Gelfand，Raffaele Giancarlo，Larry Goldstein，Andy Grigoriev，Dan Gusfield，David Haussler，Sorin Istrail，Tao Jiang，Sampath Kannan，Samuel Karlin，Dick Karp，John Kececioglu，Alex Kister，George Komatsoulis，Andrzey Konopka，Jenny Kotleman，Leonid Kruglyak，Jens Lagergren，Gadi Landau，Eric Lander，Gene Myers，Giri Narasimhan，Ravi Ravi，Mireille Regnier，Gesine Reinert，Isidore Rigoutsos，Mikhail Roytberg，Anatoly Rubinov，Andrey Rzhetsky，Chris Sander，David Sankoff，Alejandro Schaffer，David Searls，Ron Shamir，Andrey Shevchenko，Temple Smith，Mike Steel，Lubert Stryer，Elizabeth Sweedyk，Haixi Tang，Simon Tavarè，Ed Trifonov，Tandy Warnow，Haim Wolfson，Jim Vath，Shibu Yooseph等。
我和麻省理工学院出版社的Bob Prior和Michael Rutter合作很愉快。我要感谢Amy Yeager编辑了本书，Mikhail Mayofis设计了封面，Oksana Khleborodova举例说明了基因预测的算法步骤。我还要感谢那些曾经支持过我研究的部门：能源部、美国国立卫生研究院和美国国家科学基金会。
最后，很感谢Paulina和Arkasha Pevzner好心地保持安静并容忍我在写书时的心不在焉。

编者

计算分子生物学是数学、计算机科学和生物科学交叉的新兴领域之一。本书覆盖了算法和组合问题的主要领域，并揭示了这些问题是如何同分子生物学和生物技术相联系的。本书包含一个内容丰富的“无公式的计算分子生物学”部分，用相对简单的方式介绍了生物学概念和计算思想，但涉及的内容却是许多基因组基本问题及其结果的核心思想。本书力求用通俗的写法表达如何用深刻的数学思想解释复杂的生物难题，这使得没有经过生物学训练的计算机科学家和只有有限的计算机科学背景的生物学家都能够理解本书。

1计算基因搜寻1
11引言1
12遗传作图1
13物理作图4
14测序6
15相似性搜寻8
16基因预测9
17突变分析10
18比较基因组11
19蛋白质组学13

2限制酶切作图15
21引言15
22双酶切问题16
23双酶切问题的多重解17
24着色图中的交错圈20
25交错欧拉圈的变换21
26物理图谱与交错欧拉圈23
27部分酶切问题25
28同效集26
29若干其他的问题和方法28
291光学作图28
292加探针部分酶切作图29

3图谱装配30
31引言30
32非惟一探针的作图33
33惟一探针的作图36
34区间图37
35用限制酶切片段指纹图谱作图39
36若干其他的问题和方法41
361LanderWaterman统计41
362筛选克隆文库41
363放射杂交作图42

4测序44
41引言44
42重叠、排列和共有序列45
43双管鸟枪测序46
44若干其他的问题和方法47
441最短超字符串问题47
442DNA测序的结束阶段48

5DNA阵列49
51引言49
52杂交测序51
53SBH和最短超字符串问题52
54SBH和欧拉路问题53
55惟一序列重构的概率56
56字符串重排57
572最优欧拉圈60
58杂交法定位测序62
59DNA阵列的设计62
510DNA阵列的分辨率64
511多探针阵列与均匀阵列的比较65
512DNA阵列的制造66
513若干其他问题和方法69
5131利用通用碱基的SBH69
5132自适应SBH70
5133SBH类型的鸟枪测序法70
5134DNA阵列的保真探针70

6序列比较71
61引言71
62最长共同子序列问题73
63序列联配75
64局部序列联配76
65有缺口罚分的联配77
66空间效率高的序列联配77
67杨氏表79
68最长共同子序列的平均长度82
69广义序列联配和对偶性84
610序列比较的原始对偶方法86
611序列联配和整数规划87
612近似字符串匹配88
613依靠数据库的序列比较89
614多重过滤90
615若干其他的问题和方法92
6151参数的序列联配92
6152联配统计量和相变92
6153次优序列联配93
6154串联重复片段的联配93
6155筛选数据库中的搜索结果93
6156文本之间的统计距离93
6157RNA折叠94

7多重联配95
71引言95
72计算多重联配的得分96
73装配成对联配97
74多重联配的近似算法98
75装配l路联配99
76点阵和图像重构100
77点阵相乘的多重联配101
78若干其他的问题和方法102
781借助于进化树的多重联配102
782在编辑图中切割角102

8发现DNA中的信号103
81引言103
82Edgar Allan Poe和DNA语言学104
83适合傻子的最好的赌博106
84Conway等式107
85DNA中的频繁词108
86共有词的分析110
87CG岛和“公平赌场”111
88隐马氏模型112
89Elkhorn赌场和隐马氏模型参数估计114
810剖面隐马氏模型联配114
811吉布斯抽样116
812若干其他的问题和方法116
8121找出带缺口的信号116
8122在带偏倚频率样本中找出信号116
8123信号寻找中字母表的选择117

9基因预测118
91引言118
92基因预测的统计学方法119
93基于相似性的基因预测方法121
94剪接联配123
95反向基因搜索和cDNA中外显子定位126
96关于基因的多次提问策略127
97可变剪接与癌症128
98若干其他的问题和方法130
981基因预测的隐马氏模型130
982细菌基因预测131

10基因组重排132
101引言132
102断点图141
103难以排序的排列142
104期望的反序距离143
105有符号排列145
106交叉图和障碍146
107排列的等价变换149
108搜索安全反序153
109清除障碍156
1010反序距离的对偶定理160
1011反序排序算法163
1012人基因组变换成老鼠基因组164
1013加帽染色体168
1014帽子和尾部171
1015基因组距离的对偶定理173
1016基因组重复175
1017若干其他的问题和方法175
10171基因组重排和系统发育研究175
10172依照反序排序的快速算法176

11计算蛋白质组学177
111引言177
112肽测序问题178
113谱图180
114学习离子类型182
115给谱图中的路径打分183
116肽测序与反对称路径185
117肽鉴定问题186
118谱的卷积186
119谱联配188
1110依靠谱联配肽191
1111若干其他的问题和方法192
11111从蛋白质组学到基因组学192
11112大尺度蛋白质分析192

12问题193
121引言193
122限制酶切作图193
123图谱装配195
124测序196
125DNA阵列197
126序列比较199
127多重联配202
128探测DNA中的信号203
129基因预测203
1210基因组重排204
1211计算蛋白质组学206

13必须了解的分子生物学208

参考文献211

索引230