这里介绍一种基于序列与结构比对的最优线索化算法。令s1,s2,.sn为蛋白质序列S的n 个元素,C1,C2,,Cm为数据库中核心折叠C的m个核心区域。每一个核心区域由若干个氨基 酸残基构成。令C为第个核心区域第j个氨基酸位置。假设核心折叠C中所有重要的相互作 用都体现在各个C之间的两两作用,利用图这样的数据结构来表示这些相互作用。用图中的 顶点表示C,如果C1和C之间存在相互作用,则在图中画一条从C所在顶点到Cy所在顶 点的边。设t是一个从序列到核心折叠的线索,那么说明了序列S的哪些元素s,s,sk,代表核 心区域C1,C2C3的起始位置。这实际上是一种从序列S到核心折叠C的比对,但是在这样 的比对中序列元素内部没有空位,但是序列元素之间存在空位,这些空位将序列元素分割开 来。令λ代表核心折叠C中的环到序列S中空位的映射,显然λ是通过线索化而确定的。令f(t) 是进行序列与结构比对的得分函数,其形式定义如下 ft=g(v, t)+ g(u,v, t)+g(A, t) 其中g1(v)评价各个氨基酸残基v所处的位置;g2(uv,t)评价各残基对u和v的相对位置,如 果u和ⅴ键合,则得分高;g3(λt)评价环区,根据环区的大小进行打分 完成上述概念定义之后,可以非常简单地描述线索化问题:对于给定的序列S和核心折叠C, 选择一个线索t,使得ft)的值最小,即寻找一从S到C的最佳映射。虽然问题的描述非常 简单,但是要解决这个问题却非常复杂,这是一个NP完全问题。准确地求解需要巨大的运 算量,在实际应用中,需要采用分支约束方法压缩搜索空间,或采用近似或启发式的方法进 行求解,以提高算法的执行效率。 943从头预测方法 在既没有已知结构的同源蛋白质、也没有已知结构的远程同源蛋白质的情况下,上述两 种蛋白质结构预测的方法都不能用,这时只能采用从头预测方法( Ab initio),即直接根据 序列本身来预测其结构。在1994年之前,还没有一个从头算方法能够预测蛋白质的空间结 构。从那以后,人们陆续提出一些方法,表明了今后进一步研究可能的方向。有些研究小组 运用距离几何方法得到了非常有希望的结果。将简化的力场与动态优化策略相结合,虽然得 到的结果不算太精确,但很有意义,表明这样的工作非常有希望突破。从头预测方法一般由 下列3个部分组成:(1)一种蛋白质几何的表示方法。由于表示和处理所有原子和溶剂环 境的计算开销非常大,因此需要对蛋白质和溶剂的表示形式作近似处理,例如,使用一个或 少数几个原子代表一个氨基酸残基。(2)一种能量函数及其参数,或者一个合理的构象得 分函数,以便计算各种构象的能量。通过对已知结构的蛋白质进行统计分析,可以确定蛋白这里介绍一种基于序列与结构比对的最优线索化算法。令s1, s2,…, sn为蛋白质序列S的n 个元素，C1, C2,…, Cm为数据库中核心折叠C的m个核心区域。每一个核心区域由若干个氨基 酸残基构成。令Cij为第i个核心区域第j个氨基酸位置。假设核心折叠C中所有重要的相互作 用都体现在各个Cij之间的两两作用，利用图这样的数据结构来表示这些相互作用。用图中的 顶点表示Cij，如果Cij和Ci’j’之间存在相互作用，则在图中画一条从Cij所在顶点到Ci’j’所在顶 点的边。设t是一个从序列到核心折叠的线索，那么t说明了序列S的哪些元素si,sj,sk,…代表核 心区域C1, C2,C3,…的起始位置。这实际上是一种从序列S到核心折叠C的比对，但是在这样 的比对中序列元素内部没有空位，但是序列元素之间存在空位，这些空位将序列元素分割开 来。令λ代表核心折叠C中的环到序列S中空位的映射，显然λ是通过线索化而确定的。令f(t) 是进行序列与结构比对的得分函数，其形式定义如下： 其中g1 (v,t) 评价各个氨基酸残基v所处的位置；g2 (u,v,t) 评价各残基对u和v的相对位置，如 果u和v 键合，则得分高；g3 (λ,t)评价环区，根据环区的大小进行打分。 完成上述概念定义之后，可以非常简单地描述线索化问题：对于给定的序列 S 和核心折叠 C， 选择一个线索 t，使得 f(t)的值最小，即寻找一从 S 到 C 的最佳映射。虽然问题的描述非常 简单，但是要解决这个问题却非常复杂，这是一个 NP-完全问题。准确地求解需要巨大的运 算量，在实际应用中，需要采用分支约束方法压缩搜索空间，或采用近似或启发式的方法进 行求解，以提高算法的执行效率。 9.4.3 从头预测方法 在既没有已知结构的同源蛋白质、也没有已知结构的远程同源蛋白质的情况下，上述两 种蛋白质结构预测的方法都不能用，这时只能采用从头预测方法（Ab initio），即直接根据 序列本身来预测其结构。在 1994 年之前，还没有一个从头算方法能够预测蛋白质的空间结 构。从那以后，人们陆续提出一些方法，表明了今后进一步研究可能的方向。有些研究小组 运用距离几何方法得到了非常有希望的结果。将简化的力场与动态优化策略相结合，虽然得 到的结果不算太精确，但很有意义，表明这样的工作非常有希望突破。从头预测方法一般由 下列 3 个部分组成：（1）一种蛋白质几何的表示方法。由于表示和处理所有原子和溶剂环 境的计算开销非常大，因此需要对蛋白质和溶剂的表示形式作近似处理，例如，使用一个或 少数几个原子代表一个氨基酸残基。（2）一种能量函数及其参数，或者一个合理的构象得 分函数，以便计算各种构象的能量。通过对已知结构的蛋白质进行统计分析，可以确定蛋白