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

《计算机在分子生物学中的应用.ppt》由会员分享，可在线阅读，更多相关《计算机在分子生物学中的应用.ppt（150页珍藏版）》请在三一办公上搜索。

1、第五章 计算机在分子生物学中的应用,DNA双链模型,51 计算机在分子生物学中应用的简介,分子生物学研究的对象往往是大规模的实验数据，利用手工计算来处理这些数据显然是力不从心.例如越来越多的物种的基因组将基本上完全地测定。那种倾毕生精力研究一个基因、一条代谢途径、一种生理周期的时代已经过去.,genbank数据增长示意图,那种倾毕生精力研究一个基因、一条代谢途径、一种生理周期的时代已经过去。人们正在阐明细胞内的全部互相耦合的调控网络和代谢网络，细胞间的全部信号传导过程，从受精卵到成体的全部生理和病理的基因表达的变化等等。这一切都超出手工分析的可能性，数据的产生、搜集和分析，都必须依靠计算机和网

2、络，都必须发展数据库、算法和程序。,计算机科学的发展及其在生物学领域的应用，已经成为生物学发展和进步过程中不可替代的重要力量。计算机在分子生物学发展中的作用是无可替代的。,在分子生物学中，DNA、RNA和蛋白质都是表现为特定的序列。不同生物的DNA或蛋白质的相似性是多方面的，可能是核酸或氨基酸序列的相似性，也有可能是结构的相似性。,生物功能分子的序列测序与功能预测是从序列中发现基因的两个层次。测序的大致步骤如下：取DNA目标序列；查找开放阅读框架(ORF)并将目标序列翻译成蛋白质序列；据库中进行序列搜索；进行目标序列与搜索得到的相似序列的整体列线(global alignment)；查找基因家

3、族查找目标序列中的特定模序 预测目标序列结构 获取相关蛋白质的功能信息把目标序列输入“提醒”服务器,521序列比较中的计算机技术 从生物学的角度而言，一个普遍的规律是：序列决定结构，结构决定功能。序列的比较一般不考虑空间结构或功能的相似性。研究序列的相似性的另一个目的是通过序列的相似性，判别序列间的同源性，推测序列间的进化关系。序列比较的作用是：发现生物序列中的功能、结构和进化的信息，从而发现其中的相似性，找出序列间的共同区域，同时辨别序列之间的差异,5211、序列的相似性台戏在计算机内部，不管是DNA、RNA还是蛋白质，都是用特定的字符集来表示的。对于一种未知功能的生物分子，则可以通过将它的

4、序列与已知功能的分子的序列进行比较来推断。序列的相似性可以用定性的方法来描述，也可以用定量的方法表示。,在讨论到序列相似性的关系时，经常会遇到同源（homology）和相似(similarity)两个概念。所谓同源序列，简单地说，是指从某一共同祖先经趋异进化而形成的不同序列。,相似性(similarity)和同源性(homology)是两个完全不同的概念。相似性概念的含义比较广泛，除了上面提到的两个序列之间相同碱基或残基所占比例外，在蛋白质序列比对中，有时也指两个残基是否具有相似的特性，如侧链基团的大小、电荷性、亲疏水性等。,序列比较的基本操作是比对(align)，它是一种关于序列相似性的定性

5、描述，反映的主要是在什么部位两条序列相似或差异。如果一个比对方法能够揭示两条序列的最大相似程度或根本差异，就称这个比对是最优比对。,1.字符表和序列：在计算机中处理生物功能分子的序列比对时，将其序列抽象为字符串，这些字符串从一个特定的字符集合中抽取，这个字符集合称为：字符表。如教材中的表5.1和表5.2,在分子生物学研究的一些场合，常常要用到子序列，如：分析功能基因或是保守序列，重复序列。生物序列中的子序列在形式上看起来同计算机数据结构中的子串的概念很相近，但实际上子序列和子串还是有些不同的：子序列的范围包含了子串，所有的子串都是子序列，但子序列不一定是子串。子序列可以通过对序列进行选择，删除

6、等操作或取。例如：,基因片段1的序列为：ATTTTGCCCTTA，基因片段2的序列是：AGCT，基因片段3的序列是：TTGC。则片段2是片段1的子序列，但2不是1的子串，片段3是片段1的子串。如果有两个生物分子序列分别为t和s，则当t为s的子串时，称s是t 的超串。如果t是s 的子串，也称t是s的连续子序列。,生物功能分子中的序列比对根据比较的范围不同可以分成全局比较和局部比较两种。全局比较指的是比较两条完整的序列，而局部比较指的是找出最大相似的子序列。对于两条序列的比对，根据不同的应用场合，常常将序列比较分成以下几种基本操作：,(1)判断一个序列是不是另一个序列的子序列；(2)寻找两个序列中

7、的最大相似子序列；(3)寻找两个相似序列中的细微差别；(4)判断一个序列的特定部份（如前缀或后缀）与另一个序列的特定部份是否相同。其中，（1）和（3）是全局比较，（2）和（4）是局部比较。,2编辑距离对于两条DNA序列，有时很难看出它们有相似的地方，但是只要对其中的一条序列进行了一些简单的操作，就会发现它们之间有很多的相似之处。例如，有以下两个英文单词“tomorrow”和“sorrow”，我们可以很清楚的看到，只要将sorry错移3个位置，并对起来，就可以发现它们的相似性。tomorrow tomorrowsorrow-sorrow移位前 移位后,对于生物序列,有两种方法可以用来定量的表示两

8、条序列的相似程度：一种方法是利用相似度函数来说明，相似度越大，说明两条序列相似的程度越大；另一种方法就是利用两个序列间的距离来说明，距离越大，说明两个序列的相似程序越小。一般说来，相似度较为灵活，所以应用的较多,两个序列间的距离，可以用海明距离表示。但对于不同长度的序列用海明距离表示起来不是很精确。而且在实际的实验中，一些生物功能分子如DNA往往会发生像删除或插入一个碱基这样的错误，这时如果用海明距离来表示时，就会产生较大的误差。为了克服海明距离的缺陷，引入了编辑距离的概念，所谓编辑距离（edit distance），指的是：一个字符串变到另一个字符串时插入、删除和替换的最少的字符个数。,利用

9、编辑距离来表示两个序列的比对时，一般说来有如下的字符编辑操作：设有两个序列s和t，用-代表空位（或空缺，space）则有如下的操作：Match(a,a)-字符匹配；Delete(a,-)-从s序列中删除一个字符或在t序列中插入一个空位；Replace(a,b)-以t中的字符b替换s中的字符a，ab；Insert(-,b)-在s序列中插入空位字符，或在t序列中删除一个字符b。,进行序列比较最简单的方法就是利用点标法（Fitch,1969）来实现。这种比较方法的原理是：将两条待比较的序列分别放在二维作标的X轴上（序列的方向是自左向右）和Y轴上（序列的方向是自下而上）。当对应的行与列的字符匹配时，则

10、在作标轴上给出相应的记号，逐个比较所有的字符对，最终形成若干个匹配子串。如下所示:,如有两个序列s,t，序列分别为：s:ATCG t:ATGC,4.序列比对的数学方法(1)打分矩阵打分矩阵被广泛的用于评价序列比对的质量，通常采用得分（+）、无分（0）和罚分（-）来进行综合的评价。可以定义一个打分函数,用它来表示在序列比对中不同类型的编辑操作所需要的代价。,假定有一字符表，字符a,b满足：a,b；则有如下定义：分别对应于得分、无分和失分的情况。,在两条序列s和t进行比对时的得分等于将s转化为t所用的编辑操作的得分总和；它们间的最优比对是可能的比对中得分最高的一个比对；s和t的真实的编辑距离应当是

11、在打分函数值最大时的距离。这样,进行序列比对的目的就是寻找一个打分函数值最大的比对。,（2）核酸打分矩阵与蛋白质打分矩阵：核酸与蛋白质都是常见的生物功能分子，在分子生物学研究中，经常遇到要对它们的序列进行比对的场合。前面所说的打分矩阵方法过于简单，不能考虑到字符替换后实际的生物意义。特别对于蛋白质序列，有些氨基酸的取代是很容易产生而且不会对蛋白质的特性造成太大的影响。也就是说，不同情况下的替代是不等效的。所以，为了区分不同情况下替代对生物功能分子所起的作用，人们提出了核酸与蛋白质的打分矩阵。,核酸打分矩阵（i）等价矩阵给出了一种最简单的核酸打分矩阵（等价矩阵），它的设计的原理是，只有相同核苷酸

12、匹配的情况下打分为“1”，其它的情况下，打分均为“0”。这种矩阵过于简单，在实际的应用中很少用到。,核酸的等价矩阵,（ii）转换-颠换矩阵 众所周知，核酸的碱基可以分成两大类：一类是嘌呤，一类是嘧啶。嘌呤的碱基有两个环状结构，而嘧啶的碱基只有一个环。根据这个特点，如果DNA碱基的变化保持环数不变，则称为转换(transition)，如G变成A，如果环数发生变化，则称为颠换(transversion)，如A转成C。,根据这个特性，当两个碱基的替换发生颠换时，它的打分是-5分；当发生转换时，它的打分是-1分；发生匹配时为1分。从而，也可以得到一个矩阵，通常称它为转换-颠换矩阵。,转移-颠换矩阵,（

13、iii）BLAST矩阵 BLAST（basic local alignment search tool）是一种基本的局部对位排列搜索工具，这里也提供了一个相似性记分矩阵。这个矩阵也相对简单，如果等比较的两个核酸序列是相同的，则打5分，反之，得分为-4分。,BLAST矩阵,2)蛋白质打分矩阵（i）等价矩阵：假设蛋白质的字符表如教材上表5.1所示，则可以构建如下的等价矩阵（如教材上表5-6所示）。它的规则是当组成蛋白质的两种氨基酸相匹配时，打分为“1”，反之，均为“0”。,（ii）疏水矩阵蛋白质由于它的氨基酸残基上的电荷不同，可以分成极性氨基酸、带电氨基酸和疏水氨基酸三大类。所谓的疏水指的是氨基酸

14、与水的亲和力的很小，这主要是因为疏水性强的氨基酸中的原子间仅靠非极性共价键相连，所以，这类氨基酸分子缺少与水分子共同作用的基础。而与疏水性氨基酸相对应的是亲水性氨基酸，这些氨基酸中的原子存在极性的共价键，从而可以与水互相溶解。,根据氨基酸的亲水或疏水，也可以生成一个矩阵，称为疏水矩阵，它的设计思想是：如果一个氨基酸残基取代另一个氨基酸残基后，疏水性没有发生太大的变化，就打分高些；反之，如果替换后，疏水性发生了较大的变化，打分就低些。如下图所示:,蛋白质疏水矩阵示意图,（iii）GCM矩阵生命是不断进化的，在研究分子水平的进化时，常常用到GCM矩阵，它可以方便地描述分子的进化距离，并可以用来绘制

15、进化树。但在蛋白质比对中较少直接用到。GCM矩阵的设计思想是：计算一个氨基酸残基转变成另一个氨基酸残基所需的密码子变化的次数，将变化的次数作为对应矩阵的元素的值。如果一个氨基酸的残基只要有一个碱基发生变化，那么这两个氨基酸的替换代价即为1；如果是发生了两个碱基的变化，则为2，其它依此类推。,iv）Dayhoff突变数据矩阵（PAM矩阵）,一个PAM的进化距离定义为每100个氨基酸中发生一个点突变的概率。在这个矩阵中，大于0的值表明发生的突变的可能性较大，等于0是中性的（随机突变），小于0的则表示发生突变的可能性较小。一个PAM就是一个进化的变异单位，即1%的氨基酸发生改变，但实际上并不可能说经

16、过100次变化，每个氨基酸都会发生变化。PAM有一系列的的替换矩阵，每个矩阵用于特定的进化距离的序列。但是一般说来，只有当置换速率通过至少具有85%一致性的序列对位排列才能获取。,PAM250矩阵,V）模块替换矩阵（BLOSUM矩阵）Henikoff(1992)首先从BLOCKS数据库的对位排序列块中导出了一级置换矩阵，称为BLOSUM矩阵。它是从蛋白质序列块（短序列）比对而推导出来的，它用关系较远的序列来获取矩阵元素；而低阶BLOSUM矩阵更多是用来比较亲缘较远的序列。,BLOSUM62矩阵图,小结:（I）基于“等价矩阵”的记分 这种记分方法，只考虑序列是否匹配，匹配的位点记正分（通常为1）

17、，非匹配的位点记0分。这种方法的优点是：简单明了，适用于高度相似性序列；这种方法的缺点是：没有考虑非匹配位点间的不等价问题，在对相似性较低的序列进行对位排列时，效果尤差。,（II）基于“化学相似性”的记分方式 该方法是对一致性记分方法的局部改进。例如，Mclachlan（1972）和Feng et al。(1984)结合氨基酸的性质（如极性、电荷、大小和结构特征），对不同的氨基酸进行了加权。这种方法的优点是考虑了氨基酸和蛋白质的结构与性质；缺点是并非所有的蛋白质的结构与功能的改变都可以用简单的记分描述。,（III）基于“遗传密码”的记分 该方法考虑到当一个氨基酸转换成另一个氨基酸时，在基因组水

18、平上碱基变化的最小数目。这种方法的优点是它充分考虑到了在分子水平上的变化，具有一定的分子生物学基础。但是，它忽略了随机因素，例如：碱基变化的数目并不是氨基酸序列间相似性的惟一决定因素。,（IV）基于“实验观察”的记分 这种方法考虑了对位排序中所实际观察的频率，从而更有助于解释序列间的进化关系。Dayhoff和BLOSUM矩阵就属于这样的矩阵。Dayhoff矩阵基于进化的突变模型基于蛋白质家族进化过程中从一个共同祖先分化的蛋白质的首次变化的。而BLOSUM矩阵忽略近端和远端的关系，这称为蛋白质进化的星状模型。,Dayhoff对相关序列中所有氨基酸位置进行计分，而BLOSUM矩阵则是基于区块中置换

19、和保守位置。因而，Dayhoff模型可用于寻找蛋白质的进化起源，而BLOSUM模型用于发现蛋白质的保守域。,计算机在生物序列比对处理中起到的作用,计算机在生物序列比对中起到的作用是显著的:1.比对算法是比效率高低的重要基础全局比对和局部比对各有其相应的算法2.数据存储的形式和数据压缩三角形矩阵,稀疏矩阵还有序列的压缩算法可以节省空间,降低大量数据存放时要占用的大量空间,5212 序列的两两比对在生物学中，对各种生物功能分子的序列进行分析是一件非常基本的工作。在遗传物质长期的演化过程中，一些序列在进化的过程中不免发生一些变化。在进行比对时，这些序列就不能进行精确的匹配，但是他们具有一定的相似性。

20、我们应该如何判定序列之间的这种相似程度？对于这种情况，生物学家提出了一种用来评定序列相似性的方法，称为记分函数的方法。,1、两两比对的基本算法 进行序列的两两比对最直接的方法就是先生成两条待比较序列的所有可能比对，然后分别计算得分函数的值，在这些结果中寻找一个值最大的比对（也就是代价最小的比对）。,生物序列比对算法实际上常常用到的算法是著名的N-W算法与S-W算法，它们都是动态规划算法。其中，N-W算法常用于序列的全局比对，S-W算法常用于序列的局部比对。,（1）N-W算法 1970年，Needleman和Wunsch提出了著名的Needleman-Wunsch算法，简称为：N-W算法。Nee

21、dleman-Wunsch算法是一种整体联配(global alignment)算法，最佳联配（两条蛋白质序列具有最多匹配残基）中包括了全部的最短匹配序列。这一算法是为氨基酸序列发展的，,算法最初寻求的是使两条序列间的距离最小。尽管这类距离的元素是以一种特定的方式定义的，但该算法的良好特性在于它确定了最短距离。这是一个动态规划(dynamic programming)的方法。,该算法可以用代数形式加以描述。设有两个序列S和T，Si和Tj（0iLength(S)，0jlength(j)，length表示求序列的长度）都属于某个字符集，这两个序列间的距离可以用记分函数(S,T)表示。通过评价序列S

22、中的前i个位置和序列T中的前j位置的距离(Si,Tj)，递归得到距离(S,T)。由于S和T的长度为m=Length(S)和n=Length(T)，所以它的期望距离是(Sm,Tn)。,在单元(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）对角线移动，相当于增

23、加Si与Tj使得相似序列延伸，即：S序列的Si由T序列的Tj取代所得。这一事件的权重记为W_（Si,Tj）；所以，单元（i,j）的距离可以看作是三个相邻单元的距离和相应的权重的和的最小者。,初始条件为:(S0,T0)=0,S-W例题 将待比较的两条序列放在矩阵的两个维上，并按照公式对矩阵进行初始化打分。第一行分别表示S序列的前缀空位与T序列的前面连续j个字符组成的前缀的比对得分；第一列则表示T序列的前缀空位与S序列的前面连续i个字符组成的前缀的比对得分，如下图示：,待比较序列,在这里规定，当不匹配时分数为0，匹配时的分数为1，产生空位时分数为-1。表中的一个单元可以从(至多)三个相邻的单元达到

24、。我们把到右下角单元距离最大的方向看作相似序列延伸的方向。等距离时意味着存在两种可能的方向。将这些方向记录下来，并在研究了所有的单元之后，沿着记录的方向就有一条路径可从右下角(两个序列的末端)追踪到左上角(两个序列的起点)，由此所产生的路径将给出的最优序列联配，本例中的路径如下图中的箭头方向所示。,这里，对角线表示匹配或替换发生的情况；水平线表示插入；垂直线表示删除。则本例的路径可以让我们得到如下的序列比对，如图所示,我们可以看出，N-W算法是一种动态规划算法。这种算法是在打分矩阵的基础上进行推导的，得分值表示序列间的相似程序，它是一种全局性的比对算法。对于两条序列的比对采用N-W算法时，序列

25、的长度也有着很大的影响。,设MARK(S,T)表示两个长度各为m和n的序列的相似性打分，如果MARK(S,T)=99，则两条序列共有99个字符是一致的，如果m=n=100的话，说明这两条序列是很相似的；反之，如果m=n=1000，则仅有10%的字符相同。所以，在实际序列比较时，使用相对的长度得分就更加的有意义了，可以定义如式：用Sim(s,t)作为衡量序列相似性的指标。,（2）S-W算法Smith和Waterman在Needleman-Wunsch算法的基础上进行改进，提出序列局部比对算法；后来其他人又进一步改进，形成改良Smith-Waterman算法，该算法将寻找多种最好的但不相互交叉的比

26、对方式作为结果。,对于两个序列S和T，Si和Tj（0iLength(S)，0jlength(j)，length表示求序列的长度）都属于某个字符集，对于中的任何元素和空符号，它们之间都有一个记分值，用记分函数(x,y)表示，F(i,j)表示序列S的前缀S1S2Si-1Si和序列T的前缀T1T2。Tj-1Tj之间的最优相似性比较得分，则有如下公式,Smith-Waterman算法先用迭代方法计算出两个序列的所有可能相似性比较的分值，然后通过动态规划的方法回溯寻找最优相似性比较，从而我们最终可以找出i*和j*，使得F（i*,j*）=maxF(i,j),例如有如下问题：例 设有S=“a b c x d

27、 e x”，T=“x x x c d e”，其对应的记分函数(x,y)分别如下：发生匹配时：(x,x)=2，不匹配或产生空位：(x,y)=(x,-)=(-,y)=-1。试求解S和T的最优局部子序列。,初始化矩阵图,最终，可以反推出它的最佳路径，结果是：S=“a b c x d e x”，T=“x x x c d e”的局部最优联配是：c x d e 和 c-d e或 x-d e 和 x c d e,（3）MUMmer算法 MUMmer算法是Delcher于1999年提出的，它是一种基于后缀树的数据结构的比对算法。MUM的意思是最大唯一匹配（Maximal Unique Match）。,（4）P

28、attenHunter算法 2002年Bin Ma等人提出了序列搜索的PatternHunter算法，该算法创建了一个新颖的匹配模型，不仅提高了匹配的敏感度，而且大大降低了同源搜索的匹配时间,2序列两两比对的启发式算法,（1）BLAST算法BLAST 是由美国国立生物技术信息中心（NCBI）开发的一个基于序列相似性的数据库搜索程序。它是“局部相似性基本查询工具”(Basic Local Alignment Search Tool)的 缩写。它包含了很多个独立的程序，这些程序是根据查询的对象和数据库的不同来定义的。比如说查询的序列为核酸，查询数据库亦为核酸序列数据库，那么就应该选择blastn程

29、序。,主要的BLAS程序,BLAST算法的基本思想是：通过产生数量较少的但质量更好的匹配片段来提高速度其算法描述如下：首先是在数据库中找出与查询序列相同的匹配片段(也叫命中片段HIT)，且这一局部片段中不含空位，并建立查询表记录下该片段的位置；一个匹配字串选中后，程序会进行没有空位的局部延伸，根据匹配情况计算分值，当比对延伸时遇到不匹配片段则赋予负分，使得比对的分值下降，直到用动态规划算法得到某个局部最大分值为止，也即高分片段对HPS(high sequence pairs)；设定一个统计显著性阀值E，统计显著性大于E的HSP将被舍弃，剩下的HSP即为高质量的匹配片段对。,BLAST算法流程图

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

31、空位后的序列，|S|=|T|=l，Wg为开放一个空位的罚分。,(II)仿射空位处罚模型：这是最常用的一种罚分规则。空位处罚函数依赖于空位中空格的数量：用一个附加的罚分比例去乘空位的长度，其中有两个参数，Wg表示空位开放处罚，Ws表示空位延伸处罚。仿射处罚函数可表示为：Wg+qWs，q表示某一个空位的长度。这样比对的相似度：其中S和T分别为S和T加入空位后的序列，|S|=|T|=l。实际上空位权值恒定模型是仿射空位处罚模型的一个特例，即Ws=0。,空位处理的算法初始条件：V(0,0)=0;V(i,0)=E(i,0)=Wg+iWs;V(0,j)=F(0,j)=Wg+jWs;递归条件：V(i,j)=

32、max G(i,j),E(i,j),F(i,j);G(i,j)=V(i-1,j-1)+(Si,Tj);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。,公式E(i,j)可以理解为从以下两项中取最大值：在已存在的空位后面添加一个空格或者重新开放一个空位。公式F(i,j)的表示与此相似。从算法里可以看出，利用动态规划计算序列最优联配的算法的复杂度分析：时间复杂度为O(nm),空间复杂度为O(n+m)。,多序列比对有时用来区分一组序列之间的差异，但其主要用于描述一组序列之间的相似性关系，以便对一个

33、基因家族的特征有一个简明扼要的了解。与双序列比对一样，多序列比对的方法建立在某个数学或生物学模型之上,三个序列的最佳比对,利用标准动态规划算法，则每个节点的计算量为2k-1,多序列比对时每个节点计算量的示意图,（1）渐进比对算法多序列比对的绝大多数方法都是基于渐进比对（progressive alignment）的概念。渐进比对的思想依赖于使用者用作比对的蛋白质序列之间确实存在的生物学上的或者更准确地说是系统发生学上的相互关联。渐进比对是最常用的多序列比对方法，其基本思想是：要比对的序列是进化相关的，因此可以按着序列的进化顺序，由近至远将序列或子比对结果按双重比对(pairwise align

34、ment)算法逐步进行比对，重复这一过程直到所有序列都加入为止这类算法的主要优点是：简单、快速；缺点是：在比对初期引进的空位插入错误无法在比对后期因加入其它序列而改正，易于陷入局部最优解,（I）CLUSTAL算法CLUSTAL算法是一个最广泛使用的多序列比对程序，已经有十多年的历史。CLUSTAL算法所提供的是全局序列比对算法，这种算法同最初的启发式算法有所不同。CLUSTAL W是这个算法较新的的应用软件系统,CLUSTAL X则提供了图形用户界面，便于用户使用。,下面是CLUSTAL W算法的大至步骤对所有序列进行两两比对，并由此计算出距离矩阵；基于距离矩阵，利用NJ（neighbour-

35、join-method）方法构建系统先导树；依据指导树的分支顺序，由关系最近的两个序列开始进行比对，出现在比对中的空位保持固定不变；由近至远，逐步添加序列，直到所有序列全部加入为止，从而构成一个系统发育树。,Clustal W 对于亲缘关系较近的序列比对效果较好，但是对于分歧较大的序列，比对的准确率明显降低,（II）TCoffe算法TCoffee是另一个有代表性的渐进比对算法，它的主要特点是将序列的两两局域及全局比对结果收集在一起，做成一个扩展比对信息库再利用扩展比对信息库中提取的信息取代替代矩阵进行渐近比对，使得在每一步渐近比对过程中用到的是所有序列之间的关系信息，而不只是仅考虑当前要比对的

36、序列信息，从而在一定程度上提高了比对准确率，尤其是对于存在大量空位插入的情况，效果更为明显,T-coffee算法中最关关键的两个因素是：构建扩展比对信息库和优化。它的算法示意图如下：,其中，基本库是建立在一系列待比较序列的两两比对的基础上的（这种比对有可能是全局的比对，也有可能是局部的比对）。每种比对结果在基本库中的权重是不同的，我们需要对所得的比对结果进行分析，并对每种结果给出一个权重。T-coffee的时间复杂度大至在O（N3L）（其中，L是序列的平均长度）,（III）DIALIGN算法DIALIGN算法 是基于片断一片断的局域多序列比对算法，它首先找出无空位的保守片段对(相当于点矩阵中的

37、对角线)；然后为每一保守片段对赋予一个权重w 用以评价其生物意义，并找出具有最大加权总和的相容片断对搜集(consistent collection of diagonals)，这些片段都满足相容性准则，即这些片段对可以被排序，而不会相互重叠；利用贪婪法将对角线依据分值高低逐步联配(assemble)成多序列比对；在序列中加入空位直到所有对角线相关的残基都被适当安置由于以保守片断作为考虑问题的出发点，自然形成比对的空位位数及空位位置，从而避免了序列比对中的一个最为困扰的问题：空位罚分的设定,（I）基于遗传算法的多序列比对SAGA算法基于遗传算法的多序列比对SAGA算法 将序列集中不等长的序列以

38、两端加空位方式补齐，构造初始群体中的个体；共设有交叉，加空位，移动空位等22个遗传算子，并根据上一代算子所起的作用，给其以一定的权值，根据权值的大小动态决定这一代是否使用该算子；选用WSP度量作为适应度函数该算法的优点是：可以对任意多个序列同时比对，而不会受到限制主要缺点是速度慢，易于陷入局域优化解,（II）Prrp迭代比对算法 Prrp这是一个著名的迭代比对算法，其基本思想是：将一个序列集随机地分为两组，然后用双重动态规划比对算法再将这两组序列合并起来对于不同的随机分组重复这种两组比对过程，直到满足终止条件为止具体算法为：从一个多序列比对开始(这一比对可以由任意简单方法而得到，并做为这个算法

39、的种子)，以该比对中任意两个序列的距离构造一棵系统发育树，并计算所有序列的的权重；以WSP分值优化两组比对；再以该比对作为种子重复进行上述过程，直到权重w 收敛为止,（III）Muscle算法Muscle算法 以系统发育树作为分组依据，使得分组迭代更为合理，该算法主要由三部分组成)：首先初步、快速地利用渐进比对算法构建一个多序列比对结果MSA1；然后以这个比对为基础，计算两两序列的距离，重新用渐进比对算法构建多序列比对MSA2；最后根据指导树的分支点，将序列分为两组(profile)，通过重新比对这两个profile，构建一个新的多序列比对MSA3，若该比对的SP分值有改善则保留，否则删除该比

40、对结果；重复执行第三部分，直到满足事先规定的结束条件为止由于有导向的分组，使得Muscle算法的准确率高于Prrp。,53分子生物学信息中心及其数据库,近20年来，有关分子生物学的大规模研究合作项目（如HGP等）在世界范围内开展起来。这些跨单位，跨地区甚至跨国的科研协作均要求在保证实验数据可靠性与完整性的前提下，及时进行信息的共享。,分子生物学数据库中数据的增长速度是十分迅速的,作为分子生物学的数据库，应当要满足以下的特点：时间性注释 支撑数据 数据质量 集成性,生物分子数据库可以分成一级数据库和二级数据库两大类：一级数据库：数据库中的数据直接来源于实验获得的原始数据，只经过简单的归类整理和注

41、释 二级数据库：对原始生物分子数据进行整理、分类的结果，是在一级数据库、实验数据和理论分析的基础上针对特定的应用目标而建立的。,1、世界上主要的分子生物学信息中心与它们的数据库介绍现阶段建立的分子数据库种类繁多，内容广泛；并且随着网络技术的普及，分子生物学信息系统大都实现了网络化；数据库中的信息量也呈爆炸性的增长；数据库的相关数据操作算法也不断增加。,（1）欧洲分子生物学实验室EMBL(The European Molecular Biology Laboratory)EMBL的主页：如图示：,EMBL主页,EMBL的数据库主要是EMBLEBI，EBI是一个非营利性的学术机构，它是Europe

42、an Molecular Biology Laboratory（EMBL）组成的一部分。BI的网址是：http:/，它的主页如图示,EBI 数据库,(2)美国国立生物技术信息中心（National Center for Biotechnology In-formation,NCBI）网址:http:/,Ncbi主页,NCBI的主要数据库是GeneBank,它由美国卫生与人类服务部注册。在1992年10月，NCBI承担起对GenBank DNA序列数据库的责任。NCBI受过分子生物学高级训练的工作人员通过来自各个实验室递交的序列和同国际核酸序列数据库（EMBL和DDBJ）交换数据建立起数据库。,

43、GeneBank中的EnterZ主页,（3）日本国立遗传研究所（National Institute of Genetics,NIG）日本国立遗传研究所作为一所日本国内进行遗传多样性研究的中央研究机构始建于1949年。,国立遗传研究所还逐渐成为日本国内遗传学（如突变研究、克隆，致病菌等）的信息资源中心，而且，还是著名的核酸数据库DDBJ的开发与维护单位。它的主页是：http:/,日本国立遗传研究所主页,日本国立遗传研究中最著名的数据库当属DDBJ（DNA Data Bank of Japan），它的主页是：http:/,DDBJ数据库主页,54 计算机在HGP中的应用,541有关基因的概念 从

44、分子生物学的角度出发，基因指的是负载特定生物遗传信息的DNA分子片段，基因在一定条件下能够表达这种遗传信息，产生特定的生命功能。,（1）基因的分类：基因的分类根据不同的划分标准可以划分成不同的种类。按照基因的功能分，可以将基因分成：结构基因（可被转录形成mRNA，并进而翻译成多肽链，构成各种结构蛋白质、催化各种生化反应的酶和激素等）调控基因（可调节控制结构基因表达的基因）只转录而不翻译的基因（如rRNA基因、tRNA基因）,（2）人类基因的结构：一般认为，人类结构基因的结构包括4个区域：外显子（在转录时，一些被转录形成RNA的序列叫外显子）；内含子（在转录时，基因中一些间隔序列的转录物在RNA

45、成熟过程中被切除了；前导区（位于编码区上游，相当于mRNA5端非编码区（非翻译区）；调节区（包括启动子和增强子等基因编码区的两侧，也称为侧翼序列）；,人类基因结构示意图,542 HGP（人类基因组计划）简介1984年，正式启动了人类基因组计划，也就是HGP（Human Genome Project）。有关HGP发展的情况大致如下：,1984.12 犹他州阿尔塔组织会议，初步研讨测定人类整个基因组DNA序列的意义1985 Dulbecco在Science撰文“肿瘤研究的转折点:人类基因组的测序”美国能源部(DOE)提出“人类基因组计划”草案1987 美国能源部和国家卫生研究院（NIH）联合为“人

46、类基因组计划”下拨启动经费约550万美元1989 美国成立“国家人类基因组研究中心”，Watson担任第一任主任1990.10 经美国国会批准，人类基因组计划正式启动,HGP的最初目标是通过国际合作，用15年时间(19902005)至少投入30亿美元，构建详细的人类基因组遗传图和物理图，确定人类DNA的全部核苷酸序列，定位约10万基因，并对其它生物进行类似研究，研究的结果是得到4张图：遗传图、物理图、序列图、基因图。,HGP的终极目标是：阐明人类基因组全部DNA序列；识别基因；建立储存这些信息的数据库；开发数据分析工具；研究HGP实施所带来的伦理、法律和社会问题。,人类基因组组成示意图,一般认

47、为功能基因组研究的核心问题有：基因组的多样性；基因组的表达及其时空调节；模式生物基因组研究伦理学问题等,543基因芯片的简介 基因芯片（又称 DNA 芯片、生物芯片）指将大量（通常每平方厘米点阵密度高于 400）探针分子固定于支持物上后与标记的样品分子进行杂交，通过检测每个探针分子的杂交信号强度进而获取样品分子的数量和序列信息。,该技术应用领域主要有基因表达谱分析、新基因发现、基因突变及多态性分析、基因组文库作图、疾病诊断和预测、药物筛选、基因测序等。,1 基因芯片的主要类型芯片种类较多，制备方法也不尽相同，但基本上可分为两大类：一类是原位合成；一种是直接点样。原位合成适用于寡核苷酸；直接点样

48、多用于大片段DNA，有时也用于寡核苷酸，甚至mRNA。原位合成有两种途径，一是光刻法；一是压电打印法。,样品的准备及靶基因的杂交检测待分析基因在与芯片结合探针杂交之前必需进行分离、扩增及标记。根据样品来源、基因含量及检测方法和分析目的不同，采用的基因分离、扩增及标记方法各异。由于灵敏度所限，多数方法需要在标记和分析前对样品进行适当程序的扩增,可在一个样品中同时对数以万计的 DNA 片段进行克隆，且无需单独处理和分离每个克隆,基因芯片技术的主要应用 可同时、快速、准确地分析数以千计基因组信息的本领而显示出了巨大的威力。这些应用主要包括基因表达检测、突变检测、基因组多态性分析和基因文库作图以及杂交

49、测序等方面。此外，基因芯片技术还被广泛地应用于临床疾病诊断、药物筛选和新药开发、环境保护、农业和畜牧业、军事和司法等领域。,基因芯片技术的研究方向及当前面临的困难困难:技术成本昂贵、复杂、检测灵敏度较低、重复性差、分析泛围较狭窄等问题,研究方向:(1)加强基因芯片的特异性；(2)进一步简化样品制备和标记操作；(3)提升芯片信息检测的灵敏度；(4)高度集成化与自动化的样品制备、基因扩增、核酸标记及检测仪器的研制和开发。,我国基因芯片的研究现状 军事医学科学院、清华大学、中科院上海冶金所等单位已在这方面取得了较大突破 国家级经费到2003年时共投入约700万元人民币，全国范围内用于生物芯片研发的民

50、间风险资本投入约为1.6亿元人民币,基因芯片的数据流程图,对于一个具体的高密度基因芯片研究或应用而言，主要的信息学工作包括确定芯片待检测的目标序列、芯片设计、检测结果分析和数据管理。,1、确定待检测的目标序列2、高密度基因芯片设计3、基因芯片检测结果分析及数据管理,544基因芯片中的计算机应用1、基因芯片中的信息处理现有的信息分析方法主要有：已经发展得比较成熟的算法是聚类分析（cluster）,包括自组织图（SOM）,k-means cluster，多维排列（multi-dimensional scaling，MDS）等等。另外还有主成分分析（PCA），Support Vector Machi