心得: SHERENGA: De novo peptide sequencing via tandem mass spectrometry(1999)

這一篇很不錯 , 提到許多實作上會遇到的問題和困難

目前De novo sequencing的問題:1.目前的演算法都是針對演算法作者特殊的ion type, 並無一個嚴謹的方法來定義ion type和intensity的高度
2. spectrum Graph:當peptide切的不完全的時候, spectrum graph會切成不連續的component,這時候就無法找出正確的sequence
3. 算分的方法: 對於spectrum graph中並無一個嚴謹的方法來定義路徑的分數
4. 由於Spectrum中可能包含了同一個peptide, 但是帶了不同數量的正電,因此在spectrum就會表現在不同的位置,因此,如果沒有消除這種狀況就會把同一個ion重複計算的情形
第一步: 列出所有可能的ion type, 令D=delta={d1,d2..dk}, 其中集合理面的元素代表了這個元素與原始的peptide質量差, 例如: 一個b-ion在這個集合的數值應該是y-ion, 因為b-ion和y-ion加起來是一個peptide,所謂的d-ion代表P'中的partial sequence,因此, m(d-ion)=m(P')-d代表了d-ion的質量
因此, 一個peptide的theoretical spectrum就是將peptide的mass減去D集合,因此, 會產生k個peptide,例如, 最常發生的ion有b, a, b-H2O, b-NH3(D={1,-27,-17,16})***注意: 這篇paper把切完後的C-terminal ion當作是peptide,所以,等等s+d的部分也是C-terminal ion 的mass
第二步: 將spectrum轉成spectrum graph
**由於一個peptide中包含了N-terminal 和 C-terminal, 為了方便說明和解釋, 這篇paper主要假定大部分的ion是N-terminal ion因此要把每個peak針對D進行轉換,並化成node, 因此每個peak(以S表示)可以有V(S)={s+d1, ...s+dk}, 所以一個spectrum的端點集合為: V(S1)U V(S2)...U V(Sm)**注意: s+d是指m(p')
第三步: 如果任兩個node之間的質量差距是某個AA, 我們就建立一條連接線
定義: 由於peptide P可能可以切成n種不同subsequence, 為P1,...Pn,則如果spectrum圖中包含了每個P1..Pn中至少一個ion type,則我們稱這個spectrum是complete
各種不同的儀器對於產生各種不同type的ion會有不同的習性,因此這篇paper利用學習各種儀器的ion來瞭解儀器的習性並介紹了offset frequency來定義特殊質譜儀的ion-type習性
定義及假設條件:1. 設S={S1,..Sm}為一個spectrum, sj表示其中的一個peak
2. 設有一peptide為Pi(為P切出來的)
3.則 Pi 與 Sj 的質量偏移值是m(Pi)-sj 並且表示成xij , 就是第i個peptide和第j個peak的mass偏差量
4. 假設我們給予一個spectrum, 偏差量的值X, 和準確度e(對於一個mass精確值可容忍的範圍), 我們定義H(X,S) 是指對於1到n-1個peptide和1到m個peak來說其Xij恰巧為使用者定義的X值(誤差值e)的個數 , 這句話講白話一點就是對於一個圖中找出所有的peptide,設其中一個為 Pi與所有peak差距恰巧為X的數量
5. 我們定義H(X)為offset frequency function, 對所有spectra算出peak mass和Pi 偏差值為X的之總和個數圖四就是針對所有sample所得到的結果
以往的方法都是事先設定一個threshold但是並沒有考慮到intensity有時候是ion type不同就會有所不同
因此, 這一篇paper考慮到如何根據offset frequency function訂出threshold:
第一步: 我們依照intensity高低排出順序;第二步: 每k個peak為一組,並把第一組排序為1,第二組排序為2...等第三步: 根據排序的結果畫出offset frequency function的圖(如圖6),就可以很清楚的看到用什麼樣的intensity就可以分辨出一些ion
圖形 6 說明:Rank>=1/Rank<1是表示在中線以上畫出來的是排名大於1者之Offset frequency function,中線以下是排名小於1者;
由這個圖形可以發現第一個圖跟第二個圖之間中線以上的intensity減少了(原因是把Rank為1者的部分挪到下面了)
漸漸地可以發現, Intensity越高者,通常越可以區分出各樣的ion;
這時候就可以找出用何種intensity會比較適合做threshold
Merge的方法: 利用Greedy Algorithm
方法:如果兩個node的質量差距在e內,則利用Greedy Algorithm將他們合併起來; 合併的方法利用兩個node所對應的peak之intensity作為權重進行加權平均
有一種情況會發生:就是轉換到Spectrum的node之質量差異沒有在某個AA內(誤差=0.5),但是在peak的mass上卻是相差在AA內(誤差=0.5)(會有這種情況就是我們會把peak的mass利用D轉換成圖中的node),表示這樣的差距對於兩個peak來說可能也有某種資訊存在,為了不讓這樣的資訊流失, 因此我們有以下的結論:
如果在u跟v之間相差某個AA,則以某個AA連接他們, 要不如果在mass peak上相差某個AA的質量,我們用bridge edge連接他們
例如: 設在圖中有100和157兩個peak, D={-1,27},則我們可以分別對應到{99, 127}和{156, 184}, glycine=57.02, 因此,可以連結的是(99, 156), (127, 184)但是我們可以連上bridge edge的是(99, 184)和(127, 156), 藉由bridge edge可以連上其他可能可以適用的
查看Parent的Mass是否正確:
說明: 正確Parent Mass在de novo中是決定Sequence很重要的一個指標,我們用以下來判斷做出來的Parent Mass是否正確:
定義:設S={S1,...Sm}是一個peptide的spectrum,則我們可以定義S的reflection S'={S1',...Sm'} 如下:Si'=m(P)-Si-d (也就是peptide減去peak mass, 就是y-ion, 但是要考慮由b-ion轉成y-ion的差異值,所以要扣掉)d=m(y-ion)-m(b-ion)m(y-ion):y-ion的offsetm(b-ion):b-ion的offset所以, Si'=m(P)-Si-d=m(P)-Si-m(y-ion)+m(b-ion)(要從b-ion轉成y-ion先把扣掉的b-ion之offset先加回來,再扣掉y-ion的offset),
因此理論上P的S'(b-ion轉成y-ion)要跟Pi-是同樣的element,我們可以用這兩個算出peak list進行alignment, 決定Parent mass正確的程度
實際上, S'(X)={S1'...Sm'}, Si'=x-Si-d如果如果我們把X設為m(P),則可以發現S'中的值很多是相同的,因為在實際情況裡, b-ion跟y-ion是混在一起的,因此, 當我們將裡面的b-ion轉成y-ion的時候就會發生有許多peak的值是相同的,因為許多b-ion已經轉成相對應的y-ion了,但是裡面又有y-ion了
因此, 選擇的方法如下:1. 令C[S, S'(X)]代表si-sj'可以在容許範圍內的數目
2.選出一個X可以使得C[S, S'(X)]達到最大
3. 屆時一定會選出許多X,下一步就是拿出這些總和這些X內
任意指定S'(X)2. 計算Si-Sj',並且加總si-sj'是最小的,並拿出X作為要使用的parent mass
圖7就是可以明顯地看到改善parent mass的程度很大
定義p(P,S): peptide P可以產生S的機率S: spectrum因此, 就是要找出一個peptide可以使p(P,S)為最大
D={d1,...dk},假設p(di)為第i個ion產生的機率;設質譜儀產生Random Noise的機率是qR, 因此在di-ion所對應的位置產生的機率是 qi=p(di)+[1-p(di)]qR
ion理論上會在某些位置產生intensity, 一般我們只會看Match,對於一些遺失的沒有match不會懲罰,這篇paper主要強調如果我們把Missing的也加進去,可以提高正確率;
***這種方法用在辨識GG/N, AG/GA或者K/Q是很不錯的
詳細方法請詳見 334頁~335頁, 裡面的方法概述如下:
1. 設定一個ion出現在某位置的機率,但是這個位置也有可能是其他亂數產生的Peak所造成的
2.計分時把對應到的Peak算進去也要把沒有對應到或者亂數產生的也要考慮進去
75%的case是perfect case和good case, SHERENGA在圖10中對於一個perfect data可以達到完全猜對,而在Good case中也只有1~3個錯誤, 而在圖10中也顯示了Bad case也僅會有一小片段的錯誤
定義: Ladder Difference目的: 用Ladder Difference來評定出來的結果
想法: 如果對於以N-terminal為基礎來切的會產生n+1種mass,如果不考慮沒切到的和最後完整的peptide,則有n-1種切法
範例: Real : TPVSEHVTKPred : TPVSCYVTK
我們先拿Real Peptide來說好了,如果要切的話就會有 P1=T; P2=TP;P3=TPVS...因此, 可以切出n-1種結果, 我們也把Pred這樣切, 也會有n-1種結果, Ladder Difference就是把這兩個n-1種結果進行比較, 因此會有不同的地方, 注意: 如果切在E和C後面,則Real和Pred會差距26, 但是下一個切在H和Y(相差-26)之後就又會拉回來了,因此, 切在TPVS之後和切在VTK前的都沒問題, 切在C和Y之間的會有問題
false positive: 正確答案沒有, 但是找出來的有
false negative: 正確答案有, 但是找出來的沒有
因此, 這篇paper定義false positive: L(Ppred)-L(Preal) false negative: L(Preal)-L(Ppred)
(我是覺得這樣出來的意義好像不容易看出sequence有什麼樣太大的不同, 例如: 我如果一開始的AA就錯了, 那後面不是都不一樣了,所以false negative也多, 反而後面錯的false negative就少? 這樣好像不是很合理 )