计算机在分子生物学中的应用

计算机在分子生物学中的应用第一页，共一百五十页，编辑于2023年，星期二DNA双链模型第二页，共一百五十页，编辑于2023年，星期二5．1计算机在分子生物学中应用的简介分子生物学研究的对象往往是大规模的实验数据，利用手工计算来处理这些数据显然是力不从心.

例如越来越多的物种的基因组将基本上完全地测定。那种倾毕生精力研究一个基因、一条代谢途径、一种生理周期的时代已经过去.第三页，共一百五十页，编辑于2023年，星期二genbank数据增长示意图第四页，共一百五十页，编辑于2023年，星期二那种倾毕生精力研究一个基因、一条代谢途径、一种生理周期的时代已经过去。人们正在阐明细胞内的全部互相耦合的调控网络和代谢网络，细胞间的全部信号传导过程，从受精卵到成体的全部生理和病理的基因表达的变化等等。这一切都超出手工分析的可能性，数据的产生、搜集和分析，都必须依靠计算机和网络，都必须发展数据库、算法和程序。第五页，共一百五十页，编辑于2023年，星期二计算机科学的发展及其在生物学领域的应用，已经成为生物学发展和进步过程中不可替代的重要力量。计算机在分子生物学发展中的作用是无可替代的。第六页，共一百五十页，编辑于2023年，星期二在分子生物学中，DNA、RNA和蛋白质都是表现为特定的序列。不同生物的DNA或蛋白质的相似性是多方面的，可能是核酸或氨基酸序列的相似性，也有可能是结构的相似性。第七页，共一百五十页，编辑于2023年，星期二生物功能分子的序列测序与功能预测是从序列中发现基因的两个层次。测序的大致步骤如下：取DNA目标序列；查找开放阅读框架(ORF)并将目标序列翻译成蛋白质序列；据库中进行序列搜索；进行目标序列与搜索得到的相似序列的整体列线(globalalignment)；查找基因家族查找目标序列中的特定模序预测目标序列结构获取相关蛋白质的功能信息把目标序列输入“提醒”服务器第八页，共一百五十页，编辑于2023年，星期二5．2．1序列比较中的计算机技术从生物学的角度而言，一个普遍的规律是：序列决定结构，结构决定功能。序列的比较一般不考虑空间结构或功能的相似性。研究序列的相似性的另一个目的是通过序列的相似性，判别序列间的同源性，推测序列间的进化关系。序列比较的作用是：发现生物序列中的功能、结构和进化的信息，从而发现其中的相似性，找出序列间的共同区域，同时辨别序列之间的差异

第九页，共一百五十页，编辑于2023年，星期二5．2．1．1、序列的相似性台戏在计算机内部，不管是DNA、RNA还是蛋白质，都是用特定的字符集来表示的。对于一种未知功能的生物分子，则可以通过将它的序列与已知功能的分子的序列进行比较来推断。序列的相似性可以用定性的方法来描述，也可以用定量的方法表示。第十页，共一百五十页，编辑于2023年，星期二在讨论到序列相似性的关系时，经常会遇到同源（homology）和相似(similarity)两个概念。所谓同源序列，简单地说，是指从某一共同祖先经趋异进化而形成的不同序列。

第十一页，共一百五十页，编辑于2023年，星期二相似性(similarity)和同源性(homology)是两个完全不同的概念。相似性概念的含义比较广泛，除了上面提到的两个序列之间相同碱基或残基所占比例外，在蛋白质序列比对中，有时也指两个残基是否具有相似的特性，如侧链基团的大小、电荷性、亲疏水性等。第十二页，共一百五十页，编辑于2023年，星期二序列比较的基本操作是比对(align)，它是一种关于序列相似性的定性描述，反映的主要是在什么部位两条序列相似或差异。如果一个比对方法能够揭示两条序列的最大相似程度或根本差异，就称这个比对是最优比对。第十三页，共一百五十页，编辑于2023年，星期二1.字符表和序列：在计算机中处理生物功能分子的序列比对时，将其序列抽象为字符串，这些字符串从一个特定的字符集合中抽取，这个字符集合称为：字符表。如教材中的表5.1和表5.2第十四页，共一百五十页，编辑于2023年，星期二在分子生物学研究的一些场合，常常要用到子序列，如：分析功能基因或是保守序列，重复序列。生物序列中的子序列在形式上看起来同计算机数据结构中的子串的概念很相近，但实际上子序列和子串还是有些不同的：子序列的范围包含了子串，所有的子串都是子序列，但子序列不一定是子串。子序列可以通过对序列进行选择，删除等操作或取。例如：第十五页，共一百五十页，编辑于2023年，星期二基因片段1的序列为：ATTTTGCCCTTA，基因片段2的序列是：AGCT，基因片段3的序列是：TTGC。则片段2是片段1的子序列，但2不是1的子串，片段3是片段1的子串。如果有两个生物分子序列分别为t和s，则当t为s的子串时，称s是t的超串。如果t是s的子串，也称t是s的连续子序列。第十六页，共一百五十页，编辑于2023年，星期二生物功能分子中的序列比对根据比较的范围不同可以分成全局比较和局部比较两种。全局比较指的是比较两条完整的序列，而局部比较指的是找出最大相似的子序列。对于两条序列的比对，根据不同的应用场合，常常将序列比较分成以下几种基本操作：第十七页，共一百五十页，编辑于2023年，星期二(1)判断一个序列是不是另一个序列的子序列；(2)寻找两个序列中的最大相似子序列；(3)寻找两个相似序列中的细微差别；(4)判断一个序列的特定部份（如前缀或后缀）与另一个序列的特定部份是否相同。其中，（1）和（3）是全局比较，（2）和（4）是局部比较。第十八页，共一百五十页，编辑于2023年，星期二2．编辑距离对于两条DNA序列，有时很难看出它们有相似的地方，但是只要对其中的一条序列进行了一些简单的操作，就会发现它们之间有很多的相似之处。例如，有以下两个英文单词“tomorrow”和“sorrow”，我们可以很清楚的看到，只要将sorry错移3个位置，并对起来，就可以发现它们的相似性。tomorrowtomorrowsorrow----sorrow移位前移位后第十九页，共一百五十页，编辑于2023年，星期二对于生物序列,有两种方法可以用来定量的表示两条序列的相似程度：一种方法是利用相似度函数来说明，相似度越大，说明两条序列相似的程度越大；另一种方法就是利用两个序列间的距离来说明，距离越大，说明两个序列的相似程序越小。一般说来，相似度较为灵活，所以应用的较多第二十页，共一百五十页，编辑于2023年，星期二两个序列间的距离，可以用海明距离表示。但对于不同长度的序列用海明距离表示起来不是很精确。而且在实际的实验中，一些生物功能分子如DNA往往会发生像删除或插入一个碱基这样的错误，这时如果用海明距离来表示时，就会产生较大的误差。为了克服海明距离的缺陷，引入了编辑距离的概念，所谓编辑距离（editdistance），指的是：一个字符串变到另一个字符串时插入、删除和替换的最少的字符个数。第二十一页，共一百五十页，编辑于2023年，星期二利用编辑距离来表示两个序列的比对时，一般说来有如下的字符编辑操作：设有两个序列s和t，用-代表空位（或空缺，space）则有如下的操作：Match(a,a)----------字符匹配；Delete(a,-)----------从s序列中删除一个字符或在t序列中插入一个空位；Replace(a,b)------以t中的字符b替换s中的字符a，a≠b；Insert(-,b)-------在s序列中插入空位字符，或在t序列中删除一个字符b。第二十二页，共一百五十页，编辑于2023年，星期二进行序列比较最简单的方法就是利用点标法（Fitch,1969）来实现。这种比较方法的原理是：将两条待比较的序列分别放在二维作标的X轴上（序列的方向是自左向右）和Y轴上（序列的方向是自下而上）。当对应的行与列的字符匹配时，则在作标轴上给出相应的记号，逐个比较所有的字符对，最终形成若干个匹配子串。如下所示:第二十三页，共一百五十页，编辑于2023年，星期二如有两个序列s,t，序列分别为：s:ATCGt:ATGC第二十四页，共一百五十页，编辑于2023年，星期二4.序列比对的数学方法(1)打分矩阵打分矩阵被广泛的用于评价序列比对的质量，通常采用得分（+）、无分（0）和罚分（-）来进行综合的评价。可以定义一个打分函数ψ,用它来表示在序列比对中不同类型的编辑操作所需要的代价。第二十五页，共一百五十页，编辑于2023年，星期二假定有一字符表ξ，字符a,b满足：a∈ξ,b∈ξ；则有如下定义：分别对应于得分、无分和失分的情况。第二十六页，共一百五十页，编辑于2023年，星期二在两条序列s和

t进行比对时的得分等于将s转化为t所用的编辑操作的得分总和；它们间的最优比对是可能的比对中得分最高的一个比对；s和t的真实的编辑距离应当是在打分函数ψ值最大时的距离。这样,进行序列比对的目的就是寻找一个打分函数ψ值最大的比对。第二十七页，共一百五十页，编辑于2023年，星期二（2）核酸打分矩阵与蛋白质打分矩阵：核酸与蛋白质都是常见的生物功能分子，在分子生物学研究中，经常遇到要对它们的序列进行比对的场合。前面所说的打分矩阵方法过于简单，不能考虑到字符替换后实际的生物意义。特别对于蛋白质序列，有些氨基酸的取代是很容易产生而且不会对蛋白质的特性造成太大的影响。也就是说，不同情况下的替代是不等效的。所以，为了区分不同情况下替代对生物功能分子所起的作用，人们提出了核酸与蛋白质的打分矩阵。第二十八页，共一百五十页，编辑于2023年，星期二核酸打分矩阵（i）等价矩阵给出了一种最简单的核酸打分矩阵（等价矩阵），它的设计的原理是，只有相同核苷酸匹配的情况下打分为“1”，其它的情况下，打分均为“0”。这种矩阵过于简单，在实际的应用中很少用到。第二十九页，共一百五十页，编辑于2023年，星期二ATGCA1000T0100G0010C0001核酸的等价矩阵第三十页，共一百五十页，编辑于2023年，星期二（ii）转换-颠换矩阵众所周知，核酸的碱基可以分成两大类：一类是嘌呤，一类是嘧啶。嘌呤的碱基有两个环状结构，而嘧啶的碱基只有一个环。根据这个特点，如果DNA碱基的变化保持环数不变，则称为转换(transition)，如G变成A，如果环数发生变化，则称为颠换(transversion)，如A转成C。第三十一页，共一百五十页，编辑于2023年，星期二根据这个特性，当两个碱基的替换发生颠换时，它的打分是-5分；当发生转换时，它的打分是-1分；发生匹配时为1分。从而，也可以得到一个矩阵，通常称它为转换-颠换矩阵。第三十二页，共一百五十页，编辑于2023年，星期二ATGCA1-5-5-1T-51-1-5G-5-11-5C-1-5-51转移-颠换矩阵

第三十三页，共一百五十页，编辑于2023年，星期二（iii）BLAST矩阵

BLAST（basiclocalalignmentsearchtool）是一种基本的局部对位排列搜索工具，这里也提供了一个相似性记分矩阵。这个矩阵也相对简单，如果等比较的两个核酸序列是相同的，则打5分，反之，得分为-4分。第三十四页，共一百五十页，编辑于2023年，星期二ATGCA5-4-4-4T-45-4-4G-4-45-4C-4-4-45BLAST矩阵第三十五页，共一百五十页，编辑于2023年，星期二2)蛋白质打分矩阵（i）等价矩阵：假设蛋白质的字符表如教材上表5.1所示，则可以构建如下的等价矩阵（如教材上表5-6所示）。它的规则是当组成蛋白质的两种氨基酸相匹配时，打分为“1”，反之，均为“0”。第三十六页，共一百五十页，编辑于2023年，星期二第三十七页，共一百五十页，编辑于2023年，星期二（ii）疏水矩阵蛋白质由于它的氨基酸残基上的电荷不同，可以分成极性氨基酸、带电氨基酸和疏水氨基酸三大类。所谓的疏水指的是氨基酸与水的亲和力的很小，这主要是因为疏水性强的氨基酸中的原子间仅靠非极性共价键相连，所以，这类氨基酸分子缺少与水分子共同作用的基础。而与疏水性氨基酸相对应的是亲水性氨基酸，这些氨基酸中的原子存在极性的共价键，从而可以与水互相溶解。第三十八页，共一百五十页，编辑于2023年，星期二根据氨基酸的亲水或疏水，也可以生成一个矩阵，称为疏水矩阵，它的设计思想是：如果一个氨基酸残基取代另一个氨基酸残基后，疏水性没有发生太大的变化，就打分高些；反之，如果替换后，疏水性发生了较大的变化，打分就低些。如下图所示:第三十九页，共一百五十页，编辑于2023年，星期二蛋白质疏水矩阵示意图第四十页，共一百五十页，编辑于2023年，星期二（iii）GCM矩阵生命是不断进化的，在研究分子水平的进化时，常常用到GCM矩阵，它可以方便地描述分子的进化距离，并可以用来绘制进化树。但在蛋白质比对中较少直接用到。GCM矩阵的设计思想是：计算一个氨基酸残基转变成另一个氨基酸残基所需的密码子变化的次数，将变化的次数作为对应矩阵的元素的值。如果一个氨基酸的残基只要有一个碱基发生变化，那么这两个氨基酸的替换代价即为1；如果是发生了两个碱基的变化，则为2，其它依此类推。第四十一页，共一百五十页，编辑于2023年，星期二iv）Dayhoff突变数据矩阵（PAM矩阵）一个PAM的进化距离定义为每100个氨基酸中发生一个点突变的概率。在这个矩阵中，大于0的值表明发生的突变的可能性较大，等于0是中性的（随机突变），小于0的则表示发生突变的可能性较小。一个PAM就是一个进化的变异单位，即1%的氨基酸发生改变，但实际上并不可能说经过100次变化，每个氨基酸都会发生变化。PAM有一系列的的替换矩阵，每个矩阵用于特定的进化距离的序列。但是一般说来，只有当置换速率通过至少具有85%一致性的序列对位排列才能获取。第四十二页，共一百五十页，编辑于2023年，星期二PAM250矩阵第四十三页，共一百五十页，编辑于2023年，星期二V）模块替换矩阵（BLOSUM矩阵）Henikoff(1992)首先从BLOCKS数据库的对位排序列块中导出了一级置换矩阵，称为BLOSUM矩阵。它是从蛋白质序列块（短序列）比对而推导出来的，它用关系较远的序列来获取矩阵元素；而低阶BLOSUM矩阵更多是用来比较亲缘较远的序列。第四十四页，共一百五十页，编辑于2023年，星期二BLOSUM62矩阵图第四十五页，共一百五十页，编辑于2023年，星期二小结:（I）基于“等价矩阵”的记分这种记分方法，只考虑序列是否匹配，匹配的位点记正分（通常为1），非匹配的位点记0分。这种方法的优点是：简单明了，适用于高度相似性序列；这种方法的缺点是：没有考虑非匹配位点间的不等价问题，在对相似性较低的序列进行对位排列时，效果尤差。第四十六页，共一百五十页，编辑于2023年，星期二（II）基于“化学相似性”的记分方式该方法是对一致性记分方法的局部改进。例如，Mclachlan（1972）和Fengetal。(1984)结合氨基酸的性质（如极性、电荷、大小和结构特征），对不同的氨基酸进行了加权。这种方法的优点是考虑了氨基酸和蛋白质的结构与性质；缺点是并非所有的蛋白质的结构与功能的改变都可以用简单的记分描述。第四十七页，共一百五十页，编辑于2023年，星期二（III）基于“遗传密码”的记分该方法考虑到当一个氨基酸转换成另一个氨基酸时，在基因组水平上碱基变化的最小数目。这种方法的优点是它充分考虑到了在分子水平上的变化，具有一定的分子生物学基础。但是，它忽略了随机因素，例如：碱基变化的数目并不是氨基酸序列间相似性的惟一决定因素。第四十八页，共一百五十页，编辑于2023年，星期二（IV）基于“实验观察”的记分这种方法考虑了对位排序中所实际观察的频率，从而更有助于解释序列间的进化关系。Dayhoff和BLOSUM矩阵就属于这样的矩阵。Dayhoff矩阵基于进化的突变模型基于蛋白质家族进化过程中从一个共同祖先分化的蛋白质的首次变化的。而BLOSUM矩阵忽略近端和远端的关系，这称为蛋白质进化的星状模型。第四十九页，共一百五十页，编辑于2023年，星期二Dayhoff对相关序列中所有氨基酸位置进行计分，而BLOSUM矩阵则是基于区块中置换和保守位置。因而，Dayhoff模型可用于寻找蛋白质的进化起源，而BLOSUM模型用于发现蛋白质的保守域。第五十页，共一百五十页，编辑于2023年，星期二计算机在生物序列比对处理中起到的作用

计算机在生物序列比对中起到的作用是显著的:1.比对算法是比效率高低的重要基础全局比对和局部比对各有其相应的算法2.数据存储的形式和数据压缩三角形矩阵,稀疏矩阵还有序列的压缩算法可以节省空间,降低大量数据存放时要占用的大量空间第五十一页，共一百五十页，编辑于2023年，星期二5．2．1．2序列的两两比对在生物学中，对各种生物功能分子的序列进行分析是一件非常基本的工作。在遗传物质长期的演化过程中，一些序列在进化的过程中不免发生一些变化。在进行比对时，这些序列就不能进行精确的匹配，但是他们具有一定的相似性。我们应该如何判定序列之间的这种相似程度？对于这种情况，生物学家提出了一种用来评定序列相似性的方法，称为记分函数的方法。第五十二页，共一百五十页，编辑于2023年，星期二1、两两比对的基本算法进行序列的两两比对最直接的方法就是先生成两条待比较序列的所有可能比对，然后分别计算得分函数的值，在这些结果中寻找一个值最大的比对（也就是代价最小的比对）。第五十三页，共一百五十页，编辑于2023年，星期二生物序列比对算法实际上常常用到的算法是著名的N-W算法与S-W算法，它们都是动态规划算法。其中，N-W算法常用于序列的全局比对，S-W算法常用于序列的局部比对。第五十四页，共一百五十页，编辑于2023年，星期二（1）N-W算法

1970年，Needleman和Wunsch提出了著名的Needleman-Wunsch算法，简称为：N-W算法。Needleman-Wunsch算法是一种整体联配(globalalignment)算法，最佳联配（两条蛋白质序列具有最多匹配残基）中包括了全部的最短匹配序列。这一算法是为氨基酸序列发展的，第五十五页，共一百五十页，编辑于2023年，星期二算法最初寻求的是使两条序列间的距离最小。尽管这类距离的元素是以一种特定的方式定义的，但该算法的良好特性在于它确定了最短距离。这是一个动态规划(dynamicprogramming)的方法。第五十六页，共一百五十页，编辑于2023年，星期二该算法可以用代数形式加以描述。设有两个序列S和T，S[i]和T[j]（0<i≤Length(S)，0<j≤length(j)，length表示求序列的长度）都属于某个字符集Ω，这两个序列间的距离可以用记分函数σ(S,T)表示。通过评价序列S中的前i个位置和序列T中的前j位置的距离σ(Si,Tj)，递归得到距离σ(S,T)。由于S和T的长度为m=Length(S)和n=Length(T)，所以它的期望距离是σ(Sm,Tn)。第五十七页，共一百五十页，编辑于2023年，星期二在单元(i,j)内，到达该单元距离增加的三种可能事件是：从单元(i-1,j)向(i,j)方向垂直移动，相当于在T序列中插入一个空位使相似序列延伸，即：T序列由S序列中的缺失产生，这一事件的权重记作W_(Si)；从单元（i,j-1）向(i,j)方向水平移动，相当于在序列T中增加一个空位使得序列延伸，即：T序列由Tj插入到S序列产生，这一事件权重记作W+（Tj）;从单元（i-1,j-1）向（i,j）对角线移动，相当于增加Si与Tj使得相似序列延伸，即：S序列的Si由T序列的Tj取代所得。这一事件的权重记为W_（Si,Tj）；所以，单元（i,j）的距离可以看作是三个相邻单元的距离和相应的权重的和的最小者。第五十八页，共一百五十页，编辑于2023年，星期二初始条件为:σ(S0,T0)=0第五十九页，共一百五十页，编辑于2023年，星期二S-W例题将待比较的两条序列放在矩阵的两个维上，并按照公式对矩阵进行初始化打分。第一行分别表示S序列的前缀空位与T序列的前面连续j个字符组成的前缀的比对得分；第一列则表示T序列的前缀空位与S序列的前面连续i个字符组成的前缀的比对得分，如下图示：第六十页，共一百五十页，编辑于2023年，星期二t

s

ACACACTA

0-1-2-3-4-5-6-7-8A-1

G-2

C-3

A-4

C-5

A-6

C-7

A-8

待比较序列第六十一页，共一百五十页，编辑于2023年，星期二在这里规定，当不匹配时分数为0，匹配时的分数为1，产生空位时分数为-1。表中的一个单元可以从(至多)三个相邻的单元达到。我们把到右下角单元距离最大的方向看作相似序列延伸的方向。等距离时意味着存在两种可能的方向。将这些方向记录下来，并在研究了所有的单元之后，沿着记录的方向就有一条路径可从右下角(两个序列的末端)追踪到左上角(两个序列的起点)，由此所产生的路径将给出的最优序列联配，本例中的路径如下图中的箭头方向所示。第六十二页，共一百五十页，编辑于2023年，星期二第六十三页，共一百五十页，编辑于2023年，星期二这里，对角线表示匹配或替换发生的情况；水平线表示插入；垂直线表示删除。则本例的路径可以让我们得到如下的序列比对，如图所示第六十四页，共一百五十页，编辑于2023年，星期二我们可以看出，N-W算法是一种动态规划算法。这种算法是在打分矩阵的基础上进行推导的，得分值表示序列间的相似程序，它是一种全局性的比对算法。对于两条序列的比对采用N-W算法时，序列的长度也有着很大的影响。第六十五页，共一百五十页，编辑于2023年，星期二设MARK(S,T)表示两个长度各为m和n的序列的相似性打分，如果MARK(S,T)=99，则两条序列共有99个字符是一致的，如果m=n=100的话，说明这两条序列是很相似的；反之，如果m=n=1000，则仅有10%的字符相同。所以，在实际序列比较时，使用相对的长度得分就更加的有意义了，可以定义如式：用Sim(s,t)作为衡量序列相似性的指标。第六十六页，共一百五十页，编辑于2023年，星期二（2）S-W算法Smith和Waterman在Needleman-Wunsch算法的基础上进行改进，提出序列局部比对算法；后来其他人又进一步改进，形成改良Smith-Waterman算法，该算法将寻找多种最好的但不相互交叉的比对方式作为结果。

第六十七页，共一百五十页，编辑于2023年，星期二对于两个序列S和T，S[i]和T[j]（0<i≤Length(S)，0<j≤length(j)，length表示求序列的长度）都属于某个字符集Ω，对于Ω中的任何元素和空符号，它们之间都有一个记分值，用记分函数σ(x,y)表示，F(i,j)表示序列S的前缀S[1]S[2]……S[i-1]S[i]和序列T的前缀T[1]T[2]……。T[j-1]T[j]之间的最优相似性比较得分，则有如下公式第六十八页，共一百五十页，编辑于2023年，星期二Smith-Waterman算法先用迭代方法计算出两个序列的所有可能相似性比较的分值，然后通过动态规划的方法回溯寻找最优相似性比较，从而我们最终可以找出i*和j*，使得F（i*,j*）=maxF(i,j)第六十九页，共一百五十页，编辑于2023年，星期二例如有如下问题：例设有S=“abcxdex”，T=“xxxcde”，其对应的记分函数(x,y)分别如下：发生匹配时：(x,x)=2，不匹配或产生空位：(x,y)=(x,-)=(-,y)=-1。试求解S和T的最优局部子序列。第七十页，共一百五十页，编辑于2023年，星期二ji01x2x3x4c5d6e000000001a02b03c04x05d06e07x0初始化矩阵图第七十一页，共一百五十页，编辑于2023年，星期二第七十二页，共一百五十页，编辑于2023年，星期二最终，可以反推出它的最佳路径，结果是：S=“abcxdex”，T=“xxxcde”的局部最优联配是：

cxde

和

c-de或

x-de和

xcde

第七十三页，共一百五十页，编辑于2023年，星期二（3）MUMmer算法

MUMmer算法是Delcher于1999年提出的，它是一种基于后缀树的数据结构的比对算法。MUM的意思是最大唯一匹配（MaximalUniqueMatch）。第七十四页，共一百五十页，编辑于2023年，星期二（4）PattenHunter算法

2002年BinMa等人提出了序列搜索的PatternHunter算法，该算法创建了一个新颖的匹配模型，不仅提高了匹配的敏感度，而且大大降低了同源搜索的匹配时间第七十五页，共一百五十页，编辑于2023年，星期二2．序列两两比对的启发式算法（1）BLAST算法BLAST是由美国国立生物技术信息中心（NCBI）开发的一个基于序列相似性的数据库搜索程序。它是“局部相似性基本查询工具”(BasicLocalAlignmentSearchTool)的缩写。它包含了很多个独立的程序，这些程序是根据查询的对象和数据库的不同来定义的。比如说查询的序列为核酸，查询数据库亦为核酸序列数据库，那么就应该选择blastn程序。第七十六页，共一百五十页，编辑于2023年，星期二程序名查询序列数据库搜索方法Blastn核酸核酸核酸序列搜索逐一核酸数据库中的序列Blastp蛋白质蛋白质蛋白质序列搜索逐一蛋白质数据库中的序列Blastx核酸蛋白质核酸序列6框翻译成蛋白质序列后和蛋白质数据库中的序列逐一搜索。Tblastn蛋白质核酸蛋白质序列和核酸数据库中的核酸序列6框翻译后的蛋白质序列逐一比对。TBlastx核酸核酸核酸序列6框翻译成蛋白质序列，再和核酸数据库中的核酸序列6框翻译成的蛋白质序列逐一进行比对。主要的BLAS程序第七十七页，共一百五十页，编辑于2023年，星期二BLAST算法的基本思想是：通过产生数量较少的但质量更好的匹配片段来提高速度．其算法描述如下：首先是在数据库中找出与查询序列相同的匹配片段(也叫命中片段HIT)，且这一局部片段中不含空位，并建立查询表记录下该片段的位置；一个匹配字串选中后，程序会进行没有空位的局部延伸，根据匹配情况计算分值，当比对延伸时遇到不匹配片段则赋予负分，使得比对的分值下降，直到用动态规划算法得到某个局部最大分值为止，也即高分片段对HPS(highsequencepairs)；设定一个统计显著性阀值E，统计显著性大于E的HSP将被舍弃，剩下的HSP即为高质量的匹配片段对。第七十八页，共一百五十页，编辑于2023年，星期二BLAST算法流程图第七十九页，共一百五十页，编辑于2023年，星期二(2)FastA算法

FastA算法是由Lipman和Pearson于1985年发表的（Lipman和Pearson，1985）。FastA的基本思路是识别与代查序列相匹配的很短的序列片段，称为k-tuple。第八十页，共一百五十页，编辑于2023年，星期二3、空位处罚的处理算法所谓空位指的是序列中任意连续的尽可能长的空格，空位的引入是为了补偿那些插入或缺失，但是在序列的比对中引入的空位不能太多，否则会使序列的排列变得面目全非。每引入一个空位，比对的分值都会有所扣除，常见的罚分规则主要有两种：空位权值恒定模型和仿射空位处罚模型。第八十一页，共一百五十页，编辑于2023年，星期二空位权值恒定模型：在每个空位中的空格的分值为零，即：(x,-)=(-,y)=0。其中S’和T’分别为S和T加入空位后的序列，|S’|=|T’|=l，Wg为开放一个空位的罚分。第八十二页，共一百五十页，编辑于2023年，星期二(II)

仿射空位处罚模型：这是最常用的一种罚分规则。空位处罚函数依赖于空位中空格的数量：用一个附加的罚分比例去乘空位的长度，其中有两个参数，Wg表示空位开放处罚，Ws表示空位延伸处罚。仿射处罚函数可表示为：Wg+q×Ws，q表示某一个空位的长度。这样比对的相似度：其中S’和T’分别为S和T加入空位后的序列，|S’|=|T’|=l。实际上空位权值恒定模型是仿射空位处罚模型的一个特例，即Ws=0。第八十三页，共一百五十页，编辑于2023年，星期二空位处理的算法初始条件：

V(0,0)=0;

V(i,0)=E(i,0)=Wg+iWs;

V(0,j)=F(0,j)=Wg+jWs;递归条件：

V(i,j)=max{G(i,j),E(i,j),F(i,j)};

G(i,j)=V(i-1,j-1)+σ(S[i],T[j]);

E(i,j)=max{E(i,j-1)+Ws,V(i,j-1)+Wg+Ws}

F(i,j)=max{F(i-1,j)+Ws,V(i-1,j)+Wg+Ws}。第八十四页，共一百五十页，编辑于2023年，星期二公式E(i,j)可以理解为从以下两项中取最大值：在已存在的空位后面添加一个空格或者重新开放一个空位。公式F(i,j)的表示与此相似。从算法里可以看出，利用动态规划计算序列最优联配的算法的复杂度分析：时间复杂度为O(nm),空间复杂度为O(n+m)。第八十五页，共一百五十页，编辑于2023年，星期二多序列比对有时用来区分一组序列之间的差异，但其主要用于描述一组序列之间的相似性关系，以便对一个基因家族的特征有一个简明扼要的了解。与双序列比对一样，多序列比对的方法建立在某个数学或生物学模型之上第八十六页，共一百五十页，编辑于2023年，星期二三个序列的最佳比对第八十七页，共一百五十页，编辑于2023年，星期二利用标准动态规划算法，则每个节点的计算量为2k-1多序列比对时每个节点计算量的示意图第八十八页，共一百五十页，编辑于2023年，星期二（1）渐进比对算法多序列比对的绝大多数方法都是基于渐进比对（progressivealignment）的概念。渐进比对的思想依赖于使用者用作比对的蛋白质序列之间确实存在的生物学上的或者更准确地说是系统发生学上的相互关联。渐进比对是最常用的多序列比对方法，其基本思想是：要比对的序列是进化相关的，因此可以按着序列的进化顺序，由近至远将序列或子比对结果按双重比对(pair—wisealignment)算法逐步进行比对，重复这一过程直到所有序列都加入为止．这类算法的主要优点是：简单、快速；缺点是：在比对初期引进的空位插入错误无法在比对后期因加入其它序列而改正，易于陷入局部最优解．第八十九页，共一百五十页，编辑于2023年，星期二（I）CLUSTAL算法CLUSTAL算法是一个最广泛使用的多序列比对程序，已经有十多年的历史。CLUSTAL算法所提供的是全局序列比对算法，这种算法同最初的启发式算法有所不同。CLUSTALW是这个算法较新的的应用软件系统,CLUSTALX则提供了图形用户界面，便于用户使用。第九十页，共一百五十页，编辑于2023年，星期二下面是CLUSTALW算法的大至步骤对所有序列进行两两比对，并由此计算出距离矩阵；基于距离矩阵，利用NJ（neighbour-join-method）方法构建系统先导树；依据指导树的分支顺序，由关系最近的两个序列开始进行比对，出现在比对中的空位保持固定不变；由近至远，逐步添加序列，直到所有序列全部加入为止，从而构成一个系统发育树。第九十一页，共一百五十页，编辑于2023年，星期二ClustalW对于亲缘关系较近的序列比对效果较好，但是对于分歧较大的序列，比对的准确率明显降低．第九十二页，共一百五十页，编辑于2023年，星期二（II）T—Coffe算法T—Coffee是另一个有代表性的渐进比对算法，它的主要特点是将序列的两两局域及全局比对结果收集在一起，做成一个扩展比对信息库．再利用扩展比对信息库中提取的信息取代替代矩阵进行渐近比对，使得在每一步渐近比对过程中用到的是所有序列之间的关系信息，而不只是仅考虑当前要比对的序列信息，从而在一定程度上提高了比对准确率，尤其是对于存在大量空位插入的情况，效果更为明显．第九十三页，共一百五十页，编辑于2023年，星期二T-coffee算法中最关关键的两个因素是：构建扩展比对信息库和优化。它的算法示意图如下：第九十四页，共一百五十页，编辑于2023年，星期二第九十五页，共一百五十页，编辑于2023年，星期二其中，基本库是建立在一系列待比较序列的两两比对的基础上的（这种比对有可能是全局的比对，也有可能是局部的比对）。每种比对结果在基本库中的权重是不同的，我们需要对所得的比对结果进行分析，并对每种结果给出一个权重。T-coffee的时间复杂度大至在O（N3L）（其中，L是序列的平均长度）第九十六页，共一百五十页，编辑于2023年，星期二（III）DIALIGN算法DIALIGN算法是基于片断一片断的局域多序列比对算法，它首先找出无空位的保守片段对(相当于点矩阵中的对角线)；然后为每一保守片段对赋予一个权重w用以评价其生物意义，并找出具有最大加权总和的相容片断对搜集(consistentcollectionofdiagonals)，这些片段都满足相容性准则，即这些片段对可以被排序，而不会相互重叠；利用贪婪法将对角线依据分值高低逐步联配(assemble)成多序列比对；在序列中加入空位直到所有对角线相关的残基都被适当安置．由于以保守片断作为考虑问题的出发点，自然形成比对的空位位数及空位位置，从而避免了序列比对中的一个最为困扰的问题：空位罚分的设定．第九十七页，共一百五十页，编辑于2023年，星期二（I）基于遗传算法的多序列比对SAGA算法基于遗传算法的多序列比对SAGA算法将序列集中不等长的序列以两端加空位方式补齐，构造初始群体中的个体；共设有交叉，加空位，移动空位等22个遗传算子，并根据上一代算子所起的作用，给其以一定的权值，根据权值的大小动态决定这一代是否使用该算子；选用WSP度量作为适应度函数．该算法的优点是：可以对任意多个序列同时比对，而不会受到限制．主要缺点是速度慢，易于陷入局域优化解．第九十八页，共一百五十页，编辑于2023年，星期二（II）Prrp迭代比对算法

Prrp这是一个著名的迭代比对算法，其基本思想是：将一个序列集随机地分为两组，然后用双重动态规划比对算法再将这两组序列合并起来．对于不同的随机分组重复这种两组比对过程，直到满足终止条件为止．具体算法为：从一个多序列比对开始(这一比对可以由任意简单方法而得到，并做为这个算法的种子)，以该比对中任意两个序列的距离构造一棵系统发育树，并计算所有序列的的权重；以WSP分值优化两组比对；再以该比对作为种子重复进行上述过程，直到权重w收敛为止．第九十九页，共一百五十页，编辑于2023年，星期二（III）Muscle算法Muscle算法以系统发育树作为分组依据，使得分组迭代更为合理，该算法主要由三部分组成)：首先初步、快速地利用渐进比对算法构建一个多序列比对结果MSA1；然后以这个比对为基础，计算两两序列的距离，重新用渐进比对算法构建多序列比对MSA2；最后根据指导树的分支点，将序列分为两组(profile)，通过重新比对这两个profile，构建一个新的多序列比对MSA3，若该比对的SP分值有改善则保留，否则删除该比对结果；重复执行第三部分，直到满足事先规定的结束条件为止．由于有导向的分组，使得Muscle算法的准确率高于Prrp。第一百页，共一百五十页，编辑于2023年，星期二5．3分子生物学信息中心及其数据库近20年来，有关分子生物学的大规模研究合作项目（如HGP等）在世界范围内开展起来。这些跨单位，跨地区甚至跨国的科研协作均要求在保证实验数据可靠性与完整性的前提下，及时进行信息的共享。第一百零一页，共一百五十页，编辑于2023年，星期二分子生物学数据库中数据的增长速度是十分迅速的第一百零二页，共一百五十页，编辑于2023年，星期二作为分子生物学的数据库，应当要满足以下的特点：时间性注释支撑数据数据质量集成性第一百零三页，共一百五十页，编辑于2023年，星期二生物分子数据库可以分成一级数据库和二级数据库两大类：一级数据库：数据库中的数据直接来源于实验获得的原始数据，只经过简单的归类整理和注释二级数据库：对原始生物分子数据进行整理、分类的结果，是在一级数据库、实验数据和理论分析的基础上针对特定的应用目标而建立的。第一百零四页，共一百五十页，编辑于2023年，星期二1、世界上主要的分子生物学信息中心与它们的数据库介绍现阶段建立的分子数据库种类繁多，内容广泛；并且随着网络技术的普及，分子生物学信息系统大都实现了网络化；数据库中的信息量也呈爆炸性的增长；数据库的相关数据操作算法也不断增加。第一百零五页，共一百五十页，编辑于2023年，星期二（1）欧洲分子生物学实验室EMBL(TheEuropeanMolecularBiologyLaboratory)EMBL的主页：http://www.embl-heidelberg.de/ExternalInfo/public_relations/contents.html如图示：第一百零六页，共一百五十页，编辑于2023年，星期二EMBL主页第一百零七页，共一百五十页，编辑于2023年，星期二EMBL的数据库主要是EMBL—EBI，EBI是一个非营利性的学术机构，它是EuropeanMolecularBiologyLaboratory（EMBL）组成的一部分。BI的网址是：http://www.ebi.ac.uk/embl/

，它的主页如图示第一百零八页，共一百五十页，编辑于2023年，星期二EBI数据库第一百零九页，共一百五十页，编辑于2023年，星期二(2)美国国立生物技术信息中心（NationalCenterforBiotechnologyIn-formation,NCBI）网址:/第一百一十页，共一百五十页，编辑于2023年，星期二Ncbi主页第一百一十一页，共一百五十页，编辑于2023年，星期二NCBI的主要数据库是GeneBank,它由美国卫生与人类服务部注册。在1992年10月，NCBI承担起对GenBank

DNA序列数据库的责任。NCBI受过分子生物学高级训练的工作人员通过来自各个实验室递交的序列和同国际核酸序列数据库（EMBL和DDBJ）交换数据建立起数据库。第一百一十二页，共一百五十页，编辑于2023年，星期二GeneBank中的EnterZ主页第一百一十三页，共一百五十页，编辑于2023年，星期二（3）日本国立遗传研究所（NationalInstituteofGenetics,NIG）日本国立遗传研究所作为一所日本国内进行遗传多样性研究的中央研究机构始建于1949年。第一百一十四页，共一百五十页，编辑于2023年，星期二国立遗传研究所还逐渐成为日本国内遗传学（如突变研究、克隆，致病菌等）的信息资源中心，而且，还是著名的核酸数据库DDBJ的开发与维护单位。它的主页是：http://www.nig.ac.jp/section/index.html

第一百一十五页，共一百五十页，编辑于2023年，星期二日本国立遗传研究所主页第一百一十六页，共一百五十页，编辑于2023年，星期二日本国立遗传研究中最著名的数据库当属DDBJ（DNADataBankofJapan），它的主页是：http://www.ddbj.nig.ac.jp/

第一百一十七页，共一百五十页，编辑于2023年，星期二DDBJ数据库主页第一百一十八页，共一百五十页，编辑于2023年，星期二5．4计算机在HGP中的应用5．4．1有关基因的概念从分子生物学的角度出发，基因指的是负载特定生物遗传信息的DNA分子片段，基因在一定条件下能够表达这种遗传信息，产生特定的生命功能。第一百一十九页，共一百五十页，编辑于2023年，星期二（1）基因的分类：基因的分类根据不同的划分标准可以划分成不同的种类。按照基因的功能分，可以将基因分成：结构基因（可被转录形成mRNA，并进而翻译成多肽链，构成各种结构蛋白质、催化各种生化反应的酶和激素等）调控基因（可调节控制结构基因表达的基因）只转录而不翻译的基因（如rRNA基因、tRNA基因）第一百二十页，共一百五十页，编辑于2023年，星期二（2）人类基因的结构：一般认为，人类结构基因的结构包括4个区域：外显子（在转录时，一些被转录形成RNA的序列叫外显子）；内含子（在转录时，基因中一些间隔序列的转录物在RNA成熟过程中被切除了；前导区（位于编码区上游，相当于mRNA5’端非编码区（非翻译区））；调节区（包括启动子和增强子等基因编码区的两侧，也称为侧翼序列）；第一百二十一页，共一百五十页，编辑于2023年，星期二人类基因结构示意图第一百二十二页，共一百五十页，编辑于2023年，星期二

5．4．2HGP（人类基因组计划）简介1984年，正式启动了人类基因组计划，也就是HGP（HumanGenomeProject）。有关HGP发展的情况大致如下：第一百二十三页，共一百五十页，编辑于2023年，星期二1984.12犹他州阿尔塔组织会议，初步研讨测定人类整个基因组DNA序列的意义1985Dulbecco在《Science》撰文“肿瘤研究的转折点:人类基因组的测序”美国能源部(DOE)提出“人类基因组计划”草案1987美国能源部和国家卫生研究院（NIH）联合为“人类基因组计划”下拨启动经费约550万美元1989

美国成立“国家人类基因组研究中心”，Watson担任第一任主任1990.10

经美国国会批准，人类基因组计划正式启动第一百二十四页，共一百五十页，编辑于2023年，星期二HGP的最初目标是通过国际合作，用15年时间(1990～2005)至少投入30亿美元，构建详细的人类基因组遗传图和物理图，确定人类DNA的全部核苷酸序列，定位约10万基因，并对其它生物进行类似研究，研究的结果是得到4张图：遗传图、物理图、序列图、基因图。第一百二十五页，共一百五十页，编辑于2023年，星期二HGP的终极目标是：阐明人类基因组全部DNA序列；识别基因；建立储存这些信息的数据库；开发数据分析工具；研究HGP实施所带来的伦理、法律和社会问题。第一百二十六页，共一百五十页，编辑于2023年，星期二人类基因组组成示意图第一百二十七页，共一百五十页，编辑于2023年，星期二一般认为功能基因组研究的核心问题有：基因组的多样性；基因组的表达及其时空调节；模式生物基因组研究伦理学问题等第一百二十八页，共一百五十页，编辑于2023年，星期二5．4．3基因芯片的简介基因芯片（又称DNA芯片、生物芯片）指将大量（通常每平方厘米点阵密度高于400）探针分子固定于支持物上后与标记的样品分子进行杂交，通过检测每个探针分子的杂交信号强度进而获取样品分子的数量和序列信息。第一百二十九页，共一百五十页，编辑于2023年，星期二该技术应用领域主要有基因表达谱分析、新基因发现、基因突变及多态性分析、基因组文库作图、疾病诊断和预测、药物筛选、基因测序等。第一百三十页，共一百五十页，编辑于2023年，星期二1．基因芯片的主要类型芯片种类较多，制备方法也不尽相同，但基本上可分为两大类：一类是原位合成；一种是直接点样。原位合成适用于寡核苷酸；直接点样多用于大片段DNA，有时也用于寡核苷酸，甚至mRNA。原位合成有两种途径，一是光刻法；一是压电打印法。第一百三十一页，共一百五十页，编辑于2023年，星期二２．样品的准备及靶基因的杂交检测待分析基因在与芯片结合探针杂交之前必需进行分离、扩增及标记。根据样品来源、基因含量及检测方法和分析目的不同，采用的基因分离、扩增及标记方法各异。由于灵敏度所限，多数方法需要在标记和分析前对样品进行适当程序的扩增,可在一个样品中同时对数以万计的DNA片段进行克隆，且无需单独处理和分离每个克隆第一百三十二页，共一百五十页，编辑于2023年，星期二３．基因芯片技术的主要应用可同时、快速、准确地分析数以千计基因组信息的本领而显示出了巨大的威力。这些应用主要包括基因表达检测、突变检测、基因组多态性分析和基因文库作图以及杂交测序等方面。此外，基因芯片技术还被广泛地应用于临床疾病诊断、药物筛选和新药开发、环境保护、农业和畜牧业、军事和司法等领域。第一百三十三页，共一百五十页，编辑于2023