藥物分子對接動態任務遷移優化

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

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

0 引 言

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

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

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

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

1 相關工作

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

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

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

（1）預知性中斷遷移

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

（2）動態任務遷移

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

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

2 任務遷移優化策略

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

2.1 可靠性因子

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

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

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

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

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

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

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

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

其概率表述如下：

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

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

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

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

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

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

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

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

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

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

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

｛

result＝P0；

R［j］←1；

For all j∈P do

｛

For all i∈T do

｛

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

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

｝

｝

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

｛

If Rj為結點集P－｛P0｝中可靠性最好（可靠性因子值最小）的結點and Rj≤R0－ε

Result＝Pj；

｝

Return Result；

｝

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

條件1：Rk，i為結點集P－｛P0｝中可靠性最好（可靠性因子值最小）的結點。

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

2.3 藥物分子對接動態遷移算法

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

算法2 藥物分子對接動態遷移算法.

Function DynamicMigration（P0，CurrenLigandNumber，TotalNumber）

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

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

｛

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

Num＝getNumberofligand（CurrenLigandNumber）；／／獲取循環次數，可根據需要設置

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

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

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

Increment＝100；／／增量單位

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

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

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

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

Return（Result）；

｝

具體動態遷移過程分為如下6階段：

（1）確定目標結點

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

（2）傳遞中間結果

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

（3）增量數據預遷移

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

（4）停機拷貝

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

（5）目標結點對接執行

按照恢復后的狀態啟動對接程序，繼續完成計算任務。

（6）得到對接結果

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

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

3 實驗結果及分析

3.1 實驗環境

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

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

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

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

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

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

3.2 實驗過程

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

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

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

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

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

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

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

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

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

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

4 結論與展望

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

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

本文提出的動態任務遷移優化策略已經應用到網絡環境下藥物分子對接平臺，下一步，希望能夠對云計算環境動態任務遷移出現的新特性，比如：數據安全性、多任務遷移等進行研究，從而實現云環境下的藥物分子對接任務遷移。

［1］陳凱先，蔣華良，嵇汝運.計算機輔助藥物設計——原理、方法及應用［M］.上海：上海科學技術出版社，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］張彬彬，羅英偉，汪小林，等.虛擬機全系統在線遷移［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－hua.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］郭權，王希誠.網格環境下具有可靠性的任務調度策略［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.