今天要寫的是《A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment》。該文将多重序列比對問題模組化為多目标優化問題，并提出了H4MSA算法（基于文化基因算法）來解決。
-
何為多重序列比對（Multiple Sequence Alignment，MSA）問題？
多重序列比對是指對三個以上的生物學序列比對，如：蛋白質序列、DNA序列、RNA序列。一般來說，輸入時一組假定擁有眼花關系的序列。其主要目的是反映序列間的生物學關系。- 序列集合: S = { s 1 , s 2 , ⋯   , s k } S = \{s_1,s_2,\cdots,s_k\} S={s1,s2,⋯,sk}，序列 s i s_i si的長度為 ∣ s i ∣ |s_i| ∣si∣
-
字母表: Σ \Sigma Σ
例如：核苷酸字母表為 Σ n u c l e o t i d e s = { A , C , G , T } \Sigma_{nucleotides} = \{A,C,G,T\} Σnucleotides={A,C,G,T}；
氨基酸字母表為
Σ a m i n o a c i d s = { A , C , D , E , F , G , H , I , K , L , M , N , P , Q , R , S , T , V , W , Y } \Sigma_{aminoacids} = \{A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, Y\} Σaminoacids={A,C,D,E,F,G,H,I,K,L,M,N,P,Q,R,S,T,V,W,Y}
MSA問題為NP完全問題。假設待比對的序列有 k k k條，其中最長的序列的長度為 L L L，則MSA問題的計算複雜度為 O ( k 2 k L k ) O(k2^kL^k) O(k2kLk)
為了求解的友善，需要對序列做等長處理，即在序列中加入額外的間隔符( − - −)。MSA要做的無非就是通過增加’ − - −'的數量以及改變其位置得到一個序列比對結果，充分挖掘序列間的關系。
A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment 于是序列集合和字母表變為：
A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment
根據實驗經驗，有 maxLength = ⌈ 3 2 ∗ max ( ∣ s 1 ∣ , ∣ s 2 ∣ , … , ∣ s k ∣ ) ⌉ \operatorname{maxLength}=\left\lceil\frac{3}{2} * \max \left(\left|s_{1}\right|,\left|s_{2}\right|, \ldots,\left|s_{k}\right|\right)\right\rceil maxLength=⌈23∗max(∣s1∣,∣s2∣,…,∣sk∣)⌉。雖然我們可以通過增加’ − - −'得到無限長的序列，但這沒有意義。我們通過基于種群的随機搜尋算法來解決這個問題，那麼每個個體就是一個 k × ∣ s ′ ∣ k\times|s'| k×∣s′∣的矩陣，對于不同的個體 k k k值是相同的， ∣ s ′ ∣ |s'| ∣s′∣卻不一定相同的，但 ∣ s ′ ∣ < = maxLength |s'|<= \operatorname{maxLength} ∣s′∣<=maxLength序列集合： S ′ = { s 1 ′ , s 2 ′ , ⋯   , s k ′ } S' = \{s'_1,s'_2,\cdots,s'_k\} S′={s1′,s2′,⋯,sk′}，每個的序列長度 ∣ s ′ ∣ = ∣ s 1 ′ ∣ = ⋯ = ∣ s k ′ ∣ |s'| = |s'_1| =\cdots=|s'_k| ∣s′∣=∣s1′∣=⋯=∣sk′∣
字母表： Σ ′ = Σ ∪ { − } \Sigma' = \Sigma \cup\{-\} Σ′=Σ∪{−}
-
編碼方式
考慮一個個體（一種可能的配對）傳統的編碼方式采用二進制編碼，其中0代表 Σ \Sigma Σ裡的字母，1代表’ − - −'符号，下為上面個體所對應的編碼。顯然這種編碼方式所需的存儲空間與序列長度成正相關。 A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment 為了降低編碼所需的存儲空間， 本文采用了一種新的編碼方式 A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment 其中 g i g_i gi表示第 i i i條序列 g a p gap gap的數目； ip i , j \text{ip}_{i,j} ipi,j表示第 i i i條序列第 j j j個 g a p gap gap的起始位置； sp i , j \text{sp}_{i,j} spi,j表示第 i i i條序列第 j j j個 g a p gap gap的空格數（the number of spaces）；為将 ip i , j \text{ip}_{i,j} ipi,j與 sp i , j \text{sp}_{i,j} spi,j差別開來， sp i , j \text{sp}_{i,j} spi,j使用負數表示。所謂的gap和spaces如圖所示 A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment 是以上述個體采用本文的新編碼方式得到的編碼結果為 A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment 其中第四條序列的第三個gap中沒有space，是以 sp i , j = 0 \text{sp}_{i,j}=0 spi,j=0，在編碼時省略不寫。 A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment -
目标函數
前面說到MAP就是在通過增加’ − - −‘的數目和移動’ − - −'的位置來完成比對，其對應的也就是gaps的數目，初始位置以及每個gap中的spaces數。那麼如何判定是否獲得了一個好的配對方案呢？這就靠目标函數來衡量了，每種配對方式都會對應一個函數值。在本文中采用了兩個目标函數，且兩個目标函數的值均為越大越好。下面将分别介紹兩個目标函數
-
The weighted sum-of-pair with affine gap penalties f 1 f_1 f1
f 1 : W S P ( S ′ ) = ∑ l = 1 A L S P ( l ) − ∑ i = 1 k AGP ( s i ′ ) f_1 : \mathrm{WSP}\left(S^{\prime}\right)=\sum_{l=1}^{\mathrm{AL}} \mathrm{SP}(l)-\sum_{i=1}^{k} \operatorname{AGP}\left(s_{i}^{\prime}\right) f1:WSP(S′)=l=1∑ALSP(l)−i=1∑kAGP(si′)
這個函數分為兩個部分：
1） The weighted sum-of -pair : S P ( l ) = ∑ i = 1 k − 1 ∑ j = i k W i , j × δ ( s i , l ′ , s j , l ′ ) \mathrm{SP}(l)=\sum_{i=1}^{k-1} \sum_{j=i}^{k} W_{i, j} \times \delta\left(s_{i, l}^{\prime}, s_{j, l}^{\prime}\right) SP(l)=∑i=1k−1∑j=ikWi,j×δ(si,l′,sj,l′)
δ \delta δ為取代矩陣，生物學概念。
W i , j = 1 − LD ( s i , s j ) max ( ∣ s i ∣ , ∣ s j ∣ ) W_{i, j}=1-\frac{\operatorname{LD}\left(s_{i}, s_{j}\right)}{\max \left(\left|s_{i}\right|,\left|s_{j}\right|\right)} Wi,j=1−max(∣si∣,∣sj∣)LD(si,sj)為兩序列之間的權重， LD ( s i , s j ) \operatorname{LD}\left(s_{i}, s_{j}\right) LD(si,sj)表示Levenshtein距離，又稱編輯距離，指的是兩個字元串之間，由一個轉換成另一個所需的最少編輯操作次數。許可的編輯操作包括将一個字元替換成另一個字元，插入一個字元，删除一個字元。
2) The affine gap penalties : AGP ( s i ′ ) = ( g o × # gaps ) + ( g e × # spaces ) \operatorname{AGP}\left(s_{i}^{\prime}\right)=\left(g_{o} \times \# \text { gaps }\right)+\left(g_{e} \times \# \text { spaces }\right) AGP(si′)=(go×# gaps )+(ge×# spaces )
g o g_o go表示增加一個gap的權重，本文取6； g e g_e ge表示增加一個space的權重，本文取0.85； # gaps \#\text{gaps} #gaps和 # spaces \#\text{spaces} #spaces分别表示該序列中的gaps數和spaces數。
-
The number of totally conserved columns score f 2 f_2 f2
之前說過，一個配對方式（一個個體）就是一個矩陣，這個目标函數的就是在計算這個矩陣中隻包含一種字元(’ − - −'不算)的列的數目，也就是說完全比對上的列數。這個個體中标 ∗ * ∗的列完全比對上了，一共有8列，是以 f 2 = 8 f_2=8 f2=8 A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment
-
變異過程
變異過程（mutation process）主要包含四個步驟：1. Move a Block; 2. Merge Two Groups; 3. Divide a Group; 4. Compact Alignment. A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment 除此之外，還采用了Kalign2算法做局部搜尋（論文中沒有描述Kalign2算法，詳見參考文獻[1]）
局部搜尋的步驟如下：
1）從序列中任選一個區域（總長的5%-25%）
2）将選擇部分中的所有’ − - −'符号删掉 A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment 3）使用Kalign2重新比對選中部分 A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment 4）将生成的比對結果放回原序列中 A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment
PS ： 文化基因算法算法在此就不叙述了。
參考文獻
[1] T. Lassmann, O. Frings, and E. L. L. Sonnhammer, “Kalign2: High-performance multiple alignment of protein and nucleotide sequences allowing external features,” Nucl. Acids Res., vol. 37, no. 3, pp. 858–865,2009.
此僅為本人閱讀論文時的筆記，若有了解有誤的地方還請批評指正。