心得: Sequence optimization as an alternative to de novo analysis of tandem mass spectrometry data(2004)

GA的方法:
一開始的GA採用亂數產生的sequence, 並且利用這些sequence來進行重組, 選擇和突變; 計分的方法則如下

GA的Scoring function:

一般來說 , 如果要比較Experimental Spectrum跟predicted Spectrum的相似度, 我們通常利用以下三個作為評定相似度的標準
(1)理論上要出現(推測的sequence)且有對到實際spectrum的Peak
(2)理論上要出現(推測的sequence)但沒對到實際spectrum的Peak
(3)推測的sequence之質量跟實際spectrum之質量差距

實際上, 這樣的方式如果用在GA上會有很大的錯誤, 例如: 如果實際情形有一個sequence : GAP 的圖譜(就b-ion來說)應該是(58,129,226); 但是如果我們猜出來的是如果是GSP, 其圖譜就是(58,145,242),我們可以發現,GAP和GSP就差了一個AA, 其中圖譜的差異就如此大, 這如果用在GA的計分方法裡是十分不合理的 , 這樣無法讓GA有效地找到答案, 因此, 在這一篇paper提到一個新的方式來進行,敘述如下:
(1)
假設我們得到experimental spectrum是S={s1,s2...sm}

我們預估出來的spectrum是
P={p1,p2,...pn}

(2)將S的每個peak跟P的每個peak進行m/z的相減, 因此可以得到一個mXn的矩陣

要如何觀察這個矩陣, 我們用一個例子來解釋, 如果P和S是完全Match的話,則在矩陣中大部分的數值都是0, 但是實際的spectrum和預測出來的spectrum差了一個AA的話,則我們可以藉由加了一個數值, 而使得矩陣的許多元素變為0, 例如剛剛舉過的例子:
p1 p2 p3
-------------------
e1| 0 -87 -184
e2|71 -16 -113
e3|168 81 -16

我們只要加上S(71.04)和S(87.03)的差距16就可使得矩陣裡面的元素變為0

感想: 這種方法雖然有效, 但是我在想如何決定加入多少的數值或者多少的差異才算真正差很多,其實可能不容易

Pevzner在2000年提出了一篇Paper,主要是利用dynamic programming來判斷sequence的modification site,但這種方法只能用在b ion, 如果使用在b跟y同時發生的情況,結果就很容易錯

在scoring function裡面第四項的意義:

由上可以知道, 如果在矩陣裡相異的值越多的話,就越不容易藉由單純加幾個值就可以使其轉換, 因此也越不相似 , 因此本篇paper針對這個矩陣來提出相似性的算法, 稱為similarity index, 計算方法就是在D中不相同值的數目除以在D中element的數目 , 因此, 我們可以瞭解如果最後一個值要增加, 就是要至少兩個Peak進行轉換後可以對到 (也就是說加上某個轉換的值)


圖2說明:

這四個圖的X軸代表在一個矩陣定義出來相同數值的Peak數目,也就是說如果有D如果有兩組數目是相同的,但分別有30個和20個,則X軸就是20和 30,並且在Y軸上都記1, 簡單地說, X 軸代表一組內介於例如一組內有40~49個相同數值, Y軸代表其總共數量 (記得, 如果以圖1來看, 考慮B和Y-ion則會有12X12的矩陣 )

我們可以看到亂數產生的sequence大部分會有一組30個或更少的相同值(相同值越多越好)

圖b分別代表將LFSQVGK故意替換一個AA得到的模擬Spectrum(不是亂數產生的),因為每個位置都可以替換,所以其實sequence雖然有7種變化,但是矩陣12X12也很龐大

圖C代表替換兩個的情形,由於替換的情形更多了,所以數目自然也增多了

圖d是替換三個的情形

我們可以看到在d的時候(替換三個, 是替換整個sequence的42%, 其實是非常多的),幾乎跟亂數產生的sequence很像, 因此可以說, 第四項的計分可以有效辨別實驗sequence和Prediction sequence的相似性