MT6.58120.482J 生物系统中的算法与计算技术基础 Bruce Tidor教授 ace的K.White教授 MT6.58120.482J句题集#1 2006.2.24,录期三，5pm 离散构象搜索 考虑一个有N个残基的系统，每个变量有M个可能的构象。我们用集合 {m}=m,m,m来表示系统中的任一构型，其中m是残基1的构象。则任意 给定构型的能量可由下式计算： -+2 (1) 能量可有多种计算方式，但在这个问圈中是预先给定的。在本间愿中，考思 一个具有5个变量位置的构型空间，每个变量采用306个可能的构象，prdt 文件是纯文本，以b键分隔的文件，以下列格式存储了能量矩阵： EWE性E…Ew 0 Emo E…Ew 0 0 E …E (2) 0 0 ① E 其中每个子矩阵E是一个M,×M,的矩阵，形式如下： E 0 0 0 0 0 0 0 Eany 0 (3) 0 0 0 E 每个子矩阵E四是一个M,×M,的矩阵，形式如下： E E E E E E Rur (4) E E E
MIT 6.581/20.482J 生物系统中的算法与计算技术基础 Bruce Tidor 教授 Jacob K. White 教授 1 MIT 6.581/20.482J 问题集 #1 2006.2.24，星期三，5pm 离散构象搜索 考虑一个有 N 个残基的系统，每个变量有 Mi 个可能的构象。我们用集合 {m}={m1, m2,…, mN}来表示系统中的任一构型，其中 mi 是残基 i 的构象。则任意 给定构型的能量可由下式计算： ∑ ∑ ∑ − = = = − + 1 1 1| , 1 { } N i N j i pair m m N i self m mi i j E E E (1) 能量可有多种计算方式，但在这个问题中是预先给定的。在本问题中，考虑 一个具有 5 个变量位置的构型空间，每个变量采用 306 个可能的构象。pair.dat 文件是纯文本，以 tab 键分隔的文件，以下列格式存储了能量矩阵： self N pair N self pair N self pair pair N self pair pair E E E E E E E E E E L M M M O M L L L 0 0 0 0 0 0 3 3, 2 2,3 2, 1 1,2 1,3 1, (2) 其中每个子矩阵 self Ei 是一个Mi × Mi 的矩阵，形式如下： self m self m self m self m M i i i i i E E E E L M M M O M L L L 0 0 0 0 0 0 0 0 0 0 0 0 3 2 1 (3) 每个子矩阵 pair Ei, j 是一个Mi × M j 的矩阵，形式如下： pair m m pair m m pair m m pair m m pair m m pair m m pair m m pair m m pair m m pair m m pair m m pair m m pair m m pair m m pair m m pair m m M j j M j j i M j j i M j j i M j i M j i j i j i j i j M j i j i j i j i j M j i j i j i j i j E E E E E E E E E E E E E E E E , , , , , , , , , , , , , , , , 1 2 3 3 3 1 3 2 3 3 2 2 1 2 2 2 3 1 1 1 1 2 1 3 L M M M O M L L L (4)
M1T6.58120.482J 生物系统中的算法与计算技术基 Bruce Tidor教授 acbK.White教授 注意，另有两个额外的文件pair-tiny.dat和pair-small.dat。前者描述了一个 有3个残基的系统，每个有135个可能的构象：后者是一个有4个残基的系统。 每个有216个可能的构象，Tiy文件也许能帮助你调试自己的代码。Sma1文件 供你在一个存储量有限的计算机或不能使用纯文本文件par,dt的时候使用，但 这种方式并不受推荐. 1.给定预先算好的E和E情况下，要估算每个构型的能量需要多少次 操作？计算该系统的可能构型的总数。通过枚举构型状态，需要多少次 操作才能找到全局最小构型？ 2.死路消除算法(D正)为降低离散搜索的复杂度提供了有力的工具。在其最 简单的形式下，DEE算法涉及到两个“消除力”，第一个力作用于单个个 体残基构象，而第二个力作用于残基构象对 个体消除标准：当对位置)的任意构象1≠年有下式成立时，在全局 最小解中不存在位置的给定构象刚： (5) 对消除标涵当对和位置1和1为)的任意构象对“≠s和v有下式成 立时，在全局最小解中位置和j了的给定构象对m,刷不能同时存在： (+)+min.() (6 (E时+E时+E)+max(E +E.】 DE正算法中每一次循环过程中一般都执行以下步翼： for i-1:iteration8 eliminate singles eliminate pairs end 单个残基和残基对在每次选代过程中都有所减少。选代次数则可以设为 一个周定值或采用he循环，直到没有单个或成对的残基为止。 在MATLAB或其他你自己选择的编程语言中实现DEE算法。将可能的 构象数目绘制为选代次数的函数。需要多少次选代才能使枚举剩余的构 象成为可能？枚举这些构象，找到其中具有全局最小能量值的构象。 3.另一种构象搜索问愿的解决方法是平均场方法。在这种方法中，同时考 2
MIT 6.581/20.482J 生物系统中的算法与计算技术基础 Bruce Tidor 教授 Jacob K. White 教授 2 注意，另有两个额外的文件 pair-tiny.dat 和 pair-small.dat。前者描述了一个 有 3 个残基的系统，每个有 135 个可能的构象；后者是一个有 4 个残基的系统， 每个有 216 个可能的构象。Tiny 文件也许能帮助你调试自己的代码。Small 文件 供你在一个存储量有限的计算机或不能使用纯文本文件 pair.dat 的时候使用，但 这种方式并不受推荐。 1. 给定预先算好的 self E 和 pair E 情况下，要估算每个构型的能量需要多少次 操作？计算该系统的可能构型的总数。通过枚举构型状态，需要多少次 操作才能找到全局最小构型？ 2. 死路消除算法(DEE)为降低离散搜索的复杂度提供了有力的工具。在其最 简单的形式下，DEE 算法涉及到两个“消除力”。第一个力作用于单个个 体残基构象，而第二个力作用于残基构象对。 个体消除标准：当对位置 i(i≠j)的任意构象 t≠s 有下式成立时，在全局 最小解中不存在位置 i 的给定构象 s mi ： ∑ ∑ = = + > + N j pair m m u self m N j pair u m m self m u j t i t i u j s i s i E E E E 1 , 1 , min( ) max( ) (5) 对消除标准：当对和位置 i 和 j (i≠j)的任意构象对 u≠s 和 v≠s 有下式成 立时，在全局最小解中位置 i 和 j 的给定构象对 s mi ， t mj 不能同时存在： ∑ ∑ = = + + + + + + + + > N k pair m m pair m m pair m m self m self m N k pair m m pair m m pair m m self m self m j v j i u i v j u i j j u i j t j i s i t j t i t j s i E E E E E E E E E E 1 , , , 1 , , , ( ) max ( ) ( ) min ( ) ω ω ω ω ω ω (6) DEE 算法中每一次循环过程中一般都执行以下步骤： 单个残基和残基对在每次迭代过程中都有所减少。迭代次数则可以设为 一个固定值或采用 while 循环，直到没有单个或成对的残基为止。 在 MATLAB 或其他你自己选择的编程语言中实现 DEE 算法。将可能的 构象数目绘制为迭代次数的函数。需要多少次迭代才能使枚举剩余的构 象成为可能？枚举这些构象，找到其中具有全局最小能量值的构象。 3. 另一种构象搜索问题的解决方法是平均场方法。在这种方法中，同时考
MT6.58120.482U 生物系统中的算法与计算技术基健 Bruce Tidor教授 aec动K.White教授 虑每个残基的所有构象状态，对每个状态的相关种群给出一个概率描述。 在这种模型中，系统的能量由下式给出： ,=2PmE+艺三(P(mi)P(m)E）m 其中Pm)是在构象s中找到残基í的概率. 算法的主要目的是是找到一个概率集来准确描述系统的低能量构型，有 一种算法使用自治场方法自洽平均场，SCMF)一首先给出一个初始概 率分布，接着使用这个起点循环的精炼这些概率值，直到达到某种程度 的收敛。每一次循环过程中的概率更新采用以下关系式： - Pm5)= (8) -40 其中E(刷)是残基(m)的构象多，在其他残基的所有构象“平均场”中 的能量。其值由下式计算： M E(m）=Ew ∑∑(P(m)E) (9吻 Aml cml 注意，能量的单位为kcal/mol,T应为开尔文摄氏度(K),波尔兹曼常数 =1.987X 10kcal/(mol.K). 给定这共方程，我们写出自洽平均场算法如下： select initial probabilites for i=1:iterations compute mean-field energies for each m(i,s) compute probability distribution end 实现自洽平均场算法求解概率分布和相应的能量。使用均匀分布 (Pm)=1/M,)作为初始的假设分布，初始祖度为298K。如果采用100K 或100K的温度，你的结果会怎样变化？（绘制每个温度的分布图） 4,相对于DEE算法的结果，只有在很低的温度下，SCMF算法才会给出一 个唯一的构型.通过持续降低温度的方法精炼在初始温度T=298K的情况 下得到的结果，以上次运行得到的最终概率作为初始条件。使用温度集 {298,100,10,1!K。绘制每种情况下的分布情况，并与DEE算法的结
MIT 6.581/20.482J 生物系统中的算法与计算技术基础 Bruce Tidor 教授 Jacob K. White 教授 3 虑每个残基的所有构象状态，对每个状态的相关种群给出一个概率描述。 在这种模型中，系统的能量由下式给出： ∑ ∑ ∑∑ ∑ ∑ − = = == + = = = + 1 1 1 11 , 1 1 ( ( ) ) ( ( ) ( ) ) N i M s N j i M t pair m m t j s i N i M s self m s eff i i j t j s i i s i E P m E P m P m E (7) 其中 ( ) s P mi 是在构象 s 中找到残基 i 的概率。 算法的主要目的是是找到一个概率集来准确描述系统的低能量构型。有 一种算法使用自洽场方法(自洽平均场，SCMF)——首先给出一个初始概 率分布，接着使用这个起点循环的精炼这些概率值，直到达到某种程度 的收敛。每一次循环过程中的概率更新采用以下关系式： ∑ = − − = i t i s i M t kT E m kT E m e s e i P m 1 ( ) ( ) ( ) (8) 其中 ( ) s E mi 是残基 i( ) s mi 的构象 s，在其他残基的所有构象“平均场”中 的能量。其值由下式计算： ∑ ∑= = = + N j M t pair m m t j self m s i j t j s i s i E m E P m E 1 1 , ( ) ( ( ) ) (9) 注意，能量的单位为 kcal/mol，T 应为开尔文摄氏度(K)，波尔兹曼常数 k=1.987×10-3kcal/(mol.K)。 给定这些方程，我们写出自洽平均场算法如下： 实现自洽平均场算法求解概率分布和相应的能量。使用均匀分布 ( ( ) 1/ )i s P mi = M 作为初始的假设分布，初始温度为 298K。如果采用 100K 或 1000K 的温度，你的结果会怎样变化？（绘制每个温度的分布图） 4. 相对于 DEE 算法的结果，只有在很低的温度下，SCMF 算法才会给出一 个唯一的构型。通过持续降低温度的方法精炼在初始温度 T=298K 的情况 下得到的结果，以上次运行得到的最终概率作为初始条件。使用温度集 {298，100，10，1}K。绘制每种情况下的分布情况，并与 DEE 算法的结
MT6.58120.482J 生物系统中的算法与计算技术基础 Bruce Tidor教授 ace的K.White教授 果相比较 备注 1.由于这个作业需要编写相当数量的程序，我强烈建议那些缺少编程经验 的人尽早开始。可采用matlab或任何你想使用的语言，请注意，由于mtab 循环的额外开销，用mab来实现死路消除算法（即便是在一个小的数 据集上)可能需要运行儿个小时，而C+程序只需要几秒钟的时问，另 一方面，使用matlab可以很方便的进行矩阵操作。如果你决定用matlab 来编程，可以采用较小的数据集来回答句题。 2.请通过MT的服务器上交所有工作成果。请用画和zp格式压缩相关文 件。强烈建议在你的资料中包含一个简单的README文件，说明你所提 交的文件列表。如果你对代码都加以文档说明并使用有意义的变量和函 数名的话，将会大大简化我们为你的作业打分的工作
MIT 6.581/20.482J 生物系统中的算法与计算技术基础 Bruce Tidor 教授 Jacob K. White 教授 4 果相比较。 备注 1. 由于这个作业需要编写相当数量的程序，我强烈建议那些缺少编程经验 的人尽早开始。可采用matlab或任何你想使用的语言。请注意，由于matlab 循环的额外开销，用 matlab 来实现死路消除算法（即便是在一个小的数 据集上）可能需要运行几个小时，而 C++程序只需要几秒钟的时间。另 一方面，使用 matlab 可以很方便的进行矩阵操作。如果你决定用 matlab 来编程，可以采用较小的数据集来回答问题。 2. 请通过 MIT 的服务器上交所有工作成果。请用 tar 和 zip 格式压缩相关文 件。强烈建议在你的资料中包含一个简单的 README 文件，说明你所提 交的文件列表。如果你对代码都加以文档说明并使用有意义的变量和函 数名的话，将会大大简化我们为你的作业打分的工作