藥物分子對接動態(tài)任務遷移優(yōu)化

董悅麗，郭 權，孫 斌，康 玲

（大連東軟信息學院，遼寧 大連116023）

0 引 言

隨著人類基因組計劃的完成、結構生物學和蛋白質純化技術的快速發(fā)展，適合于受體分子的靶標急劇增加。同時，商業(yè)小分子數(shù)據(jù)庫也在不斷更新。這就為利用計算技術進行優(yōu)化提供了空間和必要性。計算機輔助藥物分子設計［1］可以對分子對接對象集進行聚焦，也就是進行藥物分子篩選，包括預處理、分級打分等環(huán)節(jié)。常用的計算機輔助藥物設計方法有：定量構效關系（Quantitative structure activity relationship，QSAR）方法、藥效團（Pharmacophore）模型方法、分子對接（Molecular docking，MD）方法等。然而，藥物分子對接所對應的搜索空間非常巨大，即便只考慮配體小分子的柔性的同時假定受體大分子為剛性的情況，粗略估計對接所涉及的搜索空間也至少包含1030個解，需要耗費大量的計算時間。各類計算機及優(yōu)化技術大都集中在算法優(yōu)化方面，如：蒙特卡羅算法［2］、模擬退火算法［3］、遺傳算法［4］等大量的智能優(yōu)化算法被應用到分子對接軟件中。目前，比較成熟的分子對接軟件DOCK［5］對接一個小分子的計算時間需要1～3min左右，如果要對包含235 000個小分子的分子庫進行篩選，即使假設1min對接一個小分子，也需要3917h（約163天）。

分子對接應用面臨高計算強度和快速計算的挑戰(zhàn)。主流的分子對接軟件可以運行在大型機、工作站或集群，但由于計算資源昂貴，因此在不同地理位置分布的、不同機型的虛擬計算資源構成的網(wǎng)格環(huán)境，在藥物分子對接領域得到廣泛應用［6］。分子對接任務具有計算量大、執(zhí)行時間長的特點，當計算結點的可靠性下降時，有必要對結點機實施任務遷移。

考慮到分子對接的安全性、效率以及負載均衡等問題，進行動態(tài)任務遷移優(yōu)化方案研究就顯得很重要。藥物分子對接在線遷移要求考慮同步內存和CPU 狀態(tài)以及對接數(shù)據(jù)，而在線遷移要求該同步過程中花費較短的停機時間［7］，因此如何解決較短時間內同步大量數(shù)據(jù)，是藥物分子對接在線遷移面臨的一個關鍵問題。本文提出了任務遷移優(yōu)化策略，通過分析各結點中斷事件發(fā)生次數(shù)的數(shù)學期望和方差，計算結點的可靠性因子，并在結點可靠性降低至臨界值后實施動態(tài)增量式遷移過程。

本文在KVM［8］虛擬機平臺上實現(xiàn)了在線遷移優(yōu)化機制的原型系統(tǒng)，并搭建了實驗環(huán)境。通過在具有1177個小分子的分子庫中尋找受體為環(huán)氧合酶－2的配體小分子，驗證了在線任務遷移優(yōu)化策略的高效性和可用性。實驗結果表明，在保證計算效率的前提下，該策略進一步提高了分子對接計算過程的安全性。

1 相關工作

藥物分子對接即配體小分子和受體（蛋白質）大分子的結合是個復雜過程，包括受體與配體的去溶劑化、受體（主要是活性位點處的殘基）與配體的構象變化和兩者之間的相互作用等。在受體的活性位點（Active site）處，配體小分子尋找其合理的取向（Orientation）和構象（Conformation）。配體和受體的相互作用是一個綜合平衡的過程［9］，并且配體小分子必須取得一定構象，以“適應”受體結合部位的“空腔”（Cavity）形狀和構象變化。

配體小分子和蛋白質大分子對接的部位是位于大分子受體靶點的某幾個氨基酸殘基［10］。分子對接過程主要遵循互補匹配原則：幾何形狀、靜電作用互補匹配，氫鍵、疏水相互作用互補匹配，即鎖匙原理。

在線遷移是指在整個遷移過程中，虛擬機暫停時間非常短，虛擬機上運行的服務能夠響應用戶的請求。分子對接任務的動態(tài)遷移是將某時間點的運行狀態(tài)通過計算機網(wǎng)絡在計算結點之間進行高效復制［11］，包括CPU 狀態(tài)、相關寄存器狀態(tài)、內存狀態(tài)以及外部資源設備狀態(tài)等。目前，沒有針對藥物分子對接領域在線任務遷移的研究。理論上存在如下兩種遷移方式：預知性中斷遷移［12］和動態(tài)任務遷移［13］。

（1）預知性中斷遷移

相當于停機遷移，在對接前可以對配體小分子庫設置斷點，源結點機停機后，要將其CPU 各寄存器、內存以及外部資源設備的當前狀態(tài)等全部復制到目的結點機中，在目的結點機正確加載狀態(tài)參數(shù)后，啟動目的結點機進行后續(xù)的分子對接任務。

（2）動態(tài)任務遷移

進行在線任務遷移，并最大限度地縮小源結點機的停機時間。在第一輪遷移過程中，復制源結點機的寄存器、全部內存以及外部資源設備的狀態(tài)到目的結點機；進行若干輪的相關狀態(tài)數(shù)據(jù)的增量遷移；如果剩余增量狀態(tài)數(shù)據(jù)小于設定閾值或迭代次數(shù)大于預設的閾值，終止迭代，停止源結點機，將剩余的全部增量狀態(tài)數(shù)據(jù)遷移到目的結點機。

陳陽等［14］結合內存推送復制以及按需復制方式，提出了基于內存混合復制方式的在線遷移機制。但沒有對結點遷移時機進行判定，也沒有對遷移目的結點進行選擇。本文結合源結點的狀態(tài)，通過對目的結點可靠性因子的比較，選擇合適的遷移時機并確保目標結點運行任務的可靠性和安全性。

2 任務遷移優(yōu)化策略

造成結點安全性低的因素有很多，包括設備因素、人為破壞、環(huán)境因素等。本文重點關注發(fā)生頻率最高同時也是變化性最強的一種因素，也就是由于結點處理本身（除被分配的對接事件之外）事件的頻率和強度發(fā)生變化所造成的結點計算安全性下降，從而不能在計劃的時間內完成相應的分子對接任務［15］。

2.1 可靠性因子

建立分子對接任務結點集P｛P0，P1，…，Pj，…｝，其中P0為執(zhí)行當前分子對接任務的源結點，P1，P2，…是可作為分子對接任務遷移的目的結點機。

為了衡量結點本身事件的頻率和強度的變化，采用中斷事件出現(xiàn)次數(shù)的數(shù)學期望值和均方差來進行量化比較，并得出可靠性因子，將其加入到任務遷移策略的考慮因素之中。

結點機Pj∈P 在執(zhí)行任務Ti的過程中，若共有S（S ≥0，S ∈I）次中斷，則任務Ti在結點Pj的執(zhí)行時間為Aij＝X1＋Y1＋X2＋Y2＋…＋Xs＋Ys＋Xs＋1。其中，Xi代表子任務的計算時間，Yi代表源結點本身用于自身事務執(zhí)行的中斷時間。令ω＝X1＋X2＋…＋Xs＋Xs＋1，則ω代表分子對接任務自身在Pj結點所需要的計算時間。

結點計算安全性的判定基于如下兩種假設：

（1）分子對接任務應被分配到負載較輕的結點上。

（2）結點本身的任務到達次數(shù)符合泊松分布。

利用如上假設及M／G／1 排隊系統(tǒng)相關理論［16］，可以得到如下命題：

命題：結點的任務符合排隊系統(tǒng)M／G／1，中斷時間到達率為λ，分子對接任務自身所需要的計算時間為ω，則結點自身的中斷事件的發(fā)生符合參數(shù)為λ＊ω 泊松分布。

其概率表述如下：

根據(jù)上述命題，結點Pj自身中斷事件發(fā)生次數(shù)的數(shù)學期望值計算如下：

式中：ρ表示結點Pj的利用率。結點Pj自身中斷事件發(fā)生次數(shù)的方差計算如下：

式中：θ 為服務參數(shù)；μ 為服務接受率參數(shù)。在M／G／1隊列系統(tǒng)中，可令θ＝1，則式（3）化簡為：

令可靠性因子Rk，i為結點自身中斷事件發(fā)生次數(shù)的數(shù)學期望和方差的二元函數(shù)，即任務Ti在結點Pj上的即時可靠性因子可表示為：Rk，i＝φ（Ek（Ti），σk（Ti）），且Ek（Ti）、σk（Ti）越 大，則Rk，i 值 越大。

當結點Pj的利用率參數(shù)ρ ＝0，即對任意一個任務Ti，根據(jù)式（2）（4）可得出其數(shù)學期望值Ek（Ti）＝ω，方差σk（Ti）＝0時，該結點可靠性取得最優(yōu)值，即Rk，i＝0。

2.2 分子對接遷移目標結點機選取算法

綜合考慮各候選結點的可靠性因子和網(wǎng)絡擁塞因素，提出了遷移目標結點機的選取算法，如算法1所示。

算法1 遷移目標結點機選取算法

Function Node＿Selection（P，T，R0，ε）

輸入：P是結點機集合；T 是分子對接任務集合；R0是源結點的可靠性因子；ε為考慮網(wǎng)絡擁塞等因素的差值。

輸出：通過判斷任務Ti在結點Pj上的即時可靠性因子Rk，i以及結點Pj自身中斷事件發(fā)生次數(shù)的數(shù)學期望Ek（Ti），得到目標結點機。

｛

result＝P0；

R［j］←1；

For all j∈P do

｛

For all i∈T do

｛

計算任務Ti在結點Pj上的即時可靠性因子Rk，i；

計算結點Pj自身中斷事件發(fā)生次數(shù)的數(shù)學期望Ek（Ti）；

｝

｝

For（j＝1，j＜＝n，i＋＋）

｛

If Rj為結點集P－｛P0｝中可靠性最好（可靠性因子值最?。┑慕Y點and Rj≤R0－ε

Result＝Pj；

｝

Return Result；

｝

對任意結點Pj∈P｛P0，P1，…，Pj，…｝，計算其可靠因子。當同時滿足如下兩個條件時，向結點Pj執(zhí)行任務遷移。

條件1：Rk，i為結點集P－｛P0｝中可靠性最好（可靠性因子值最?。┑慕Y點。

條件2：Rk，i≤Rk，0－ε；其中，Rk，0為源結點的可靠性因子，ε為考慮網(wǎng)絡擁塞等因素的差值。

2.3 藥物分子對接動態(tài)遷移算法

在藥物篩選過程中，借助計算機輔助藥物分子設計軟件，可以減少用于實驗環(huán)節(jié)的候選小分子集合，大大縮短成藥時間。其中，藥物分子對接軟件（如：DOCK），通過考慮與大分子對接過程中所產生的能量值，對可能成藥的小分子進行篩選。具體做法是借助能量打分值進行綜合評判，能量值越低則成藥的可能性越大。通常，對接結果將返回所有小分子按照能量從低到高的排序集合。結合實際經驗，在進行分子對接動態(tài)遷移過程中，考慮遷移效率，對完成對接的小分子集合，可根據(jù)實際情況進行設置，比如：選取能量值較低的前20%作為目標小分子集合。根據(jù)分子對接這一特點，在數(shù)據(jù)遷移之前，對已完成對接的小分子、正在對接的小分子和未進行對接的小分子，分別考慮數(shù)據(jù)遷移。動態(tài)遷移算法如算法2所示。

算法2 藥物分子對接動態(tài)遷移算法.

Function DynamicMigration（P0，CurrenLigandNumber，TotalNumber）

輸入：源結點機編號P0，當前正在對接的小分子編號CurrenLigandNumber，總共需要對接的小分子數(shù)TotalNumber；

輸 出：目 標 小 分 子 集 合 Result［SequenceNo，LigandNo，EnergyScore］，SequenceNo 是 能 量 值 序 號，LigandNo為小分子編號，EnergyScore為對接產生的能量打分值；

｛

Pj＝Node＿Selection（P，T，R0，ε）；／／確定遷移目標結點機

Num＝getNumberofligand（CurrenLigandNumber）；／／獲取循環(huán)次數(shù)，可根據(jù)需要設置

For（i＝1；i＜＝Num；i＋＋ ）

Result［SequenceNo，LigandNo，EnergyScore］＝getLigand（DockingResultSet）；／／從當前對接結果中，經過能量排序得到能量值較低的小分子集合

NumberofDocking＝TotalNumber－CurrenLigandNumber；／／目前未對接的小分子數(shù)

Increment＝100；／／增量單位

IncrementalDataMigration （P0，Pj，Increment，NumberofDocking，bestLigandNo）；／／按照小分子編號順序遷移，每次傳遞數(shù)量為Increment

Copy the CPU and memory status for the current ligand；／／暫停源虛擬機，同步臟內存頁以及當前CPU 狀態(tài)等

Restart Pjand run docking from CurrenLigandNumber to the last ligand；／／啟動目標結點Pj的對接程序

Rank the EnergyScore to get the final ligand result set；／／通過比較，得到最終目標小分子集合

Return（Result）；

｝

具體動態(tài)遷移過程分為如下6階段：

（1）確定目標結點

根據(jù)遷移目標結點機的選取算法，綜合考慮可靠性因子和網(wǎng)絡擁塞情況，得到目標結點機。

（2）傳遞中間結果

針對已經完成對接的小分子集合，僅對能量值排序位于前20%的目標小分子集合實施在線遷移，傳遞其小分子編號及能量信息，這就避免了復雜的信息傳送。

（3）增量數(shù)據(jù)預遷移

對于未對接的小分子，首先根據(jù)編號得知未對接小分子數(shù)量，將未對接小分子總數(shù)傳送到目的主機，再按照編號順序實施增量式遷移。增量單位通常為10，即一次遷移100個小分子，避免因大量數(shù)據(jù)同步而造成停機時間過長。

（4）停機拷貝

針對正在進行對接的小分子，實施停機遷移，暫停源虛擬機，同步臟內存頁以及當前CPU 狀態(tài)等。

（5）目標結點對接執(zhí)行

按照恢復后的狀態(tài)啟動對接程序，繼續(xù)完成計算任務。

（6）得到對接結果

目標結點對接完成后，通過比較能量打分值，得到最終目標小分子集合。

通過算法1，能夠選取最優(yōu)的遷移目標機，之后再借助算法2，完成了藥物分子對接任務的動態(tài)任務遷移，這就保證了遷移后，計算任務能夠繼續(xù)在目標機執(zhí)行，并結合源結點的計算結果，得到最終的目標小分子集合。

3 實驗結果及分析

3.1 實驗環(huán)境

硬件環(huán)境：7臺在不同子網(wǎng)的宿主機結點，結點間帶寬設置為100 MB／s，包括一臺源結點機P0，配置為Xeon E5504CPU，8GB RAM，任務遷移目的機包括6 臺PC 機：P1，P2，P3，P4，P5，P6，配置均為Xeon E5504CPU，4GB RAM。搭建了局域網(wǎng)環(huán)境下的網(wǎng)格平臺，共3個子網(wǎng)，子網(wǎng)1中有P0和P1，子網(wǎng)2中有P2，P3，P4，子網(wǎng)3中有P5和P6，子網(wǎng)之間通過千兆交換機連接。

軟件環(huán)境：KVM 宿主機軟件環(huán)境為Ubutun Server 10.04 TLS，內核版本2.6.32－24，KVM版本kvm－88，分子對接軟件為DOCK6.2，參數(shù)使用默認值。

實驗選擇的受體：選取環(huán)氧合酶－2 作為受體，它的PDB編號是4COX，其大分子結構如圖1所示。

圖1 環(huán)氧合酶－2受體大分子Fig.1 An Enzyme Called Cyclooxygenase－2receptor

實驗使用的配體小分子庫：配體小分子庫中有1177個小分子。

結點性能因素：受體為環(huán)氧合酶－2 時，對接花費時間在0.1s至12s范圍內。如果只在P0運行對接程序，對接執(zhí)行10 次的平均時間為206 375s。如果只在P1至P6運行對接程序，對接執(zhí)行10次的平均時間為247 788s。從以上結果可以看出，當任務從P0向目標結點（P1至P6）中的某個結點進行遷移時，因結點性能因素，對接執(zhí)行的總體時間會增加約20%。

3.2 實驗過程

如果沒有特別指出，同一組應用負載下遷移實驗重復10次，本節(jié)中實驗結果為10次結果的平均值。

每一組遷移實驗中，當P0計算結點對接計算任務執(zhí)行到100 000s左右，環(huán)氧合酶－2 受體分子對接執(zhí)行到第563號配體小分子時，對結點P0進行大量磁盤I／O 操作，從而導致其降低性能至臨界值，觸發(fā)遷移。各目標結點的可靠性因子變化趨勢如圖2所示。

圖2 目標結點的可靠性因子變化趨勢Fig.2 Trends of reliability factors of the target hosts

從圖2可以看出，P6結點的方差（抖動性）最小，表示結點負載相對穩(wěn)定，同時數(shù)學期望值最小，表示該結點負載較輕。受各目標結點負載及性能影響，從源結點向各個目標結點的遷移時間及在目標結點對接小分子庫中剩余的小分子的時間各不相同，具體時間花銷如表1所示。

表1 目標結點遷移時間和對接時間Table 1 Migration and docking time of the target hosts

綜合比較可靠性因子取值及變化趨勢，選擇P6結點作為目標結點實施在線遷移。在線遷移過程，向P6結點傳遞目標小分子集合，包括小分子編號及其能量值以及未對接小分子數(shù)量，并同步內存頁及CPU 狀態(tài)，按照增量方式傳遞小分子數(shù)據(jù)，重新啟動分子對接過程。其中，遷移所用時間為97.2s，遷移后，目標計算機能夠正確完成計算任務，所用時間為120 724.6s。這樣，利用在線遷移技術，在P0和P6所花費對接時間，再加上遷移所用時間為220 821.8s。對接花費時間與目標機器單獨計算花費時間接近，總體計算效率可以接受，并確保了分子對接計算的安全性。

實驗的最后，我們對比了實施增量式遷移前后的遷移性能，包括總遷移時間以及虛擬機停機時間，實驗結果如圖3所示。

圖3 總遷移時間和停機時間對比Fig.3 The comparison of total migration and shutdown time

從圖3中不難看出，實施增量式遷移之后大幅度縮短了遷移的總體時間。采用增量式遷移在對小分子數(shù)據(jù)實施遷移時，由于分子對接過程具有按照小分子編號順序對接的特點，因此以增量的方式將最近使用的小分子最早傳遞給目標結點，使對接過程及早啟動并持續(xù)執(zhí)行，大大提高了遷移時間。增量式遷移方式比KVM 遷移平均復制數(shù)據(jù)頁的迭代收斂速率高，在停機時臟頁面數(shù)較少。相反，KVM 遷移機制在停機時需要復制更多的臟頁面數(shù)，因此停機時間稍長，大約為286 ms，大于增量式遷移中的101ms平均時間。

通過上述對比可以看出，在總體遷移時間和虛擬機停機時間方面，運用在線增量式遷移機制進行藥物分子對接遷移效率明顯提升。

4 結論與展望

網(wǎng)格環(huán)境下分子對接應用計算量大，計算時間長，為提高其安全性及可靠性，本文提出了分子對接過程中的動態(tài)任務遷移優(yōu)化策略，該策略考慮目標結點的穩(wěn)定性和安全性，依據(jù)方差和數(shù)學期望確定可靠性因子，確定遷移目標結點，從而能夠使藥物分子對接計算在網(wǎng)格環(huán)境下并行計算，避免用戶因某個計算結點負載過重或者出現(xiàn)網(wǎng)絡中斷、斷電情況而造成的損失，確保了藥物分子對接任務的有效性和安全性。

同時，結合藥物分子對接過程的特點，提出了藥物分子對接動態(tài)遷移機制，在選擇安全穩(wěn)定的目標結點后，實施增量式數(shù)據(jù)預遷移，從而大大提高了對接效率。

本文提出的動態(tài)任務遷移優(yōu)化策略已經應用到網(wǎng)絡環(huán)境下藥物分子對接平臺，下一步，希望能夠對云計算環(huán)境動態(tài)任務遷移出現(xiàn)的新特性，比如：數(shù)據(jù)安全性、多任務遷移等進行研究，從而實現(xiàn)云環(huán)境下的藥物分子對接任務遷移。

［1］陳凱先，蔣華良，嵇汝運.計算機輔助藥物設計——原理、方法及應用［M］.上海：上?？茖W技術出版社，2000：25－33.

［2］Abagyan R，Totrov M，Kuznetsov D.ICM－a new method for protein modeling and design：applications to docking and structure prediction from the distorted native conformation［J］.J Comput Chem，1994，15（5）：488－506.

［3］Goodsell D S，Morris G M，Olson A J.Distributed automated docking of flexible ligands to proteins：parallel applications of autodock 2.4［J］.J Comput－Aided Mol Des，1996，10（4）：293－304.

［4］李純蓮，王希誠，趙金城.應用改進型遺傳算法進行藥物分子對接設計［J］.計算機工程與應用，2003，39（36）：31－33.Li Chun－lian，Wang Xi－cheng，Zhao Jin－cheng.Drug molecular design using a modified genetic algorithm［J］.Computer Engineering and Applications，2003，39（36）：31－33.

［5］Ewing T J，Makino S，Skillman A G，et al.DOCK 4.0：search strategies for automated molecular docking of flexible molecule databases［J］.J Comput Aided Mol Des，2001，15（5）：411－428.

［6］Baek S，Park S，Yand S，et al.Efficient server virtualization using grid service infrastructure［J］.J Inf Process Syst，2010，6（4）：553－562.

［7］張彬彬，羅英偉，汪小林，等.虛擬機全系統(tǒng)在線遷移［J］.電子學報，2009，37（4）：894－899.Zhang Bin－bin，Luo Ying－wei，Wang Xiao－lin，et al.Whole－system live migration mechanism for virtual machines［J］.Acta Electronica Sinica，2009，37（4）：894－899.

［8］Kivity A，Kamay Y，Laor D，et al.KVM：the Linux virtual machine monitor［C］∥Proceedings of the Linux Symposium，Ottawa，Ontario，Canada，2007：225－230.

［9］Tao Peng，Lai Lu－h(huán)ua.Protein ligand docking based on empirical method for binding affinity estimation［J］.Journal of Computer－Aided Molecular Design，2001，15（5）：429－446.

［10］康玲，李洪林，王希誠.一種考慮蛋白質柔性的分子對接方法［J］.大連理工大學學報，2008，48（2）：282－286.Kang Ling，Li Hong－lin，Wang Xi－cheng.A molecular docking method considering protein flexibility［J］.Journal of Dalian University of Technology，2008，48（2）：282－286.

［11］Rodriguez P，Biersack E W.Dynamic parallel access to replicated content in the Internet［J］.IEEE／ACM Transactions on Networking，2002，10（4）：455－465.

［12］Cully B，Lefebvre G，Meyer D，et al.Remus：High availability via asynchronous virtual machine replication［C］∥NSDI＇08Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation，Berkeley，CA，USA，2008：161－174.

［13］Hirofuchi T，Ogawa H，Nakada H，et al.A live storage migration mechanism over WAN for relocatable virtual machine services on clouds cluster computing and the grid［C］∥IEEE／ACM International Symposium on Cluster Computing and the Grid，Shanghai，China，2009：460－465.

［14］陳陽，懷進鵬，胡春明.基于內存混合復制方式的虛擬機在線遷移機制［J］.計算機學報，2011，34（12）：2278－2290.Chen Yang，Huai Jin－peng，Hu Chun－ming.Live migration of virtual machines based on hybrid memory copy approach［J］.Chinese Journal of Computer，2011，34（12）：2278－2290.

［15］郭權，王希誠.網(wǎng)格環(huán)境下具有可靠性的任務調度策略［J］.南京理工大學學報：自然科學版，2006，30（5）：592－598.Guo Quan，Wang Xi－cheng.Reliable and cost－considered task scheduling for grid computing［J］.Journal of Nanjing University of Science and Technology（Natural Science Edition），2006，30（5）：592－598.

［16］Topcuoglu H，Hariri S.Performance－effective and low－complexity task scheduling for heterogeneous computing［J］.IEEE Trans Parallel and Distributed Systems，2002，13（3）：260－274.