天天看點

《中國人工智能學會通訊》——8.25 基于演化優化的生物網絡配準

生物網絡配準是為了找到不同種群之間不同蛋白質網絡的相似子圖。生物網絡配準可以幫助我們預測蛋白質功能。網絡配準主要分為局部網絡配準和全局網絡配準兩種。局部網絡配準是為了比對網絡的局部區域,而全局網絡是為了比對網絡的所有節點。在全局網絡配準中,一個重要的問題是同時比對網絡結構和生物資訊。全局網絡配準被證明是一個 NP 完全問題。

目标函數

以前的算法主要是通過最大化網絡的拓撲相似度,實作生物網絡配準。學者提出了許多拓撲 相 似 度 函 數, 如 edge correctness、 inducedconserved structure 和 symmetric substructurescore。後來通過同時優化節點序列和拓撲相似度提高配準準确率[38] 。通常引入一個參數 α 來調節節點序列和拓撲相似度的權重,類似于下面的形式:

《中國人工智能學會通訊》——8.25 基于演化優化的生物網絡配準

其中, T s 表示網絡拓撲相似度;S s 表示節點序列相似度;α 是介于 0~1 之間的權重。

傳統算法中,需要反複實驗來确定 α 的值。文獻 [39] 的作者将網絡比對問題模組化成一個多目标優化問題,其中 T s 和 S s 作為兩個目标函數。

個體表示

給定兩個網絡 和 ,使得 。網絡 G 1 中的所有節點使用序列 标記。 對于網絡G 2 ,使用一個随機排列的序列

《中國人工智能學會通訊》——8.25 基于演化優化的生物網絡配準

表示。表示比對結果,它是由 中的前 n 1個元素組成。

遺傳算子

對于網絡比對問題,主要有兩種交叉操作。第一種基于 knuths 正則分解和循環分解算法[40] 。這種交叉操作産生的子代可以很好地繼承它們父代大部分的性質。另外一種交叉操作是均勻部分比對交叉。網絡比對問題中使用的變異操作一般都非常簡單,如文獻 [39] 中随機交換一個染色體的兩個元素。

局部搜尋

作為一個被廣泛采用的局部搜尋算法,爬山法也被用于網絡比對問題[39] 。在文獻 [39] 中,作者設計了兩種基于爬山法的政策來改善比對的種群并且增加了目标空間種群的多樣性。在文獻 [41] 中,作者設計了一種新的基于鄰域的局部搜尋算法。

繼續閱讀