心得 : PepNovo De Novo Peptide Sequencing via Probabilistic Network Modeling(2005)

本篇Paper方法概述:
使用機率網路的方式來進行最佳Peptide的計分, 這些機率值表示出peptide fragmentation裡面化學和物理的規則 ; 不僅如此 , 這篇Paper也利用假設檢定的方式來查看出現的Peak是根據fragmentation model還是亂數引起的

M代表
(1) 如果針對的是Prefix Sequence
M=p1,...pi所有AA的mass總和

(2) 如果針對的是Suffix Sequence
M=Pi+1...Pn


說明:

沒有括弧的數字代表該種fragmen在我們所定義的"可見"spectrum裡面出現的機率; 有括弧的數字代表該種fragment在我們所定義的"全部"spectrum裡面出現的機率;

***這篇Paper沒有說怎麼算出這樣的機率,我在想是不是用出現的位置總數除以spectrum的數字總數
Sherenga的演算法利用以下兩者model一起說明出現的Peak :
1. 利用統計的model(peptide fragmentation)來解釋觀察到的Peak
2. 利用亂數模型來解釋出現的Peak

注意: 這個地方提到的m(Pi),其中Pi指的是每個AA之最基本的結構,如果要把這些AA的最基本結構結合起來變成peptide要再加上H2O

在CID的過程裡面, 通常會沿著peptide backbone切一刀, 我們可以分為prefix fragment(p1...pi)和suffix fragment(pi+1...pn) ,

尚未切之前的整個peptide叫做, precursor peptide, 如果precursor peptide又帶電者,稱為precursor ion

切完以後的結果有些會遺失一些東西,比如H2O和NH3

Sherenga Algorithm的作法:
(1)先假定共有K個ion type,並且定義出他們的offset(d1...dk)
(2)我們可以假定某種ion type的mass 是Si, 如此如果我們在Peak中出現Si+d1...等Peak, 我們就產生一個vertex, 如果兩個vertex的值很相近者,我們就將他們合併,因為他們來自於相同的cleavage site

這個Paper方法的前置步驟 :

(1) 對於m的各種ion計算intensity

這個Paper定義某個mass m的intensity之方法如下:

利用m左右兩邊差距為delta內的強度當作是mass m的最大強度者 ;
我們令Bm是m所有可能的範圍(如果切出來的AA之總和為m), 因此考慮到其可能的ion就會有以下的列式:
Bm={[b-d,b+d] , [y-d,y+d]...},
因此m根據Bm算出來的Intensity就是I=

有些Peak可能Intensity很高, 但是沒有被標註者, 很可能代表沒有被這裡的model考慮到或者根本就是污染物, 這裡會把這些沒有標註的Peak當做noise, 這些noise與Peak的ion之position相match的機率是 0.1, 當然有些intensity比較小者, 雖然會被noise蓋過去,但是我們可以藉由其他的ion來卻確認其機率
再來, 這個方法主要是利用relevance score的方法來Cite出Prefix masses,使這個方法其可以用Prefix mass(Spectrum中的node)來推測最後的結果 ; 因此, 推測的方法如下:

假設檢定的方式:利用

(1) Pcid(I|m,S) : 假設切出來的AA總和是m , 且為spectrum S, 則Pcid(I|m,S)代表可以出現I的機率

(2) Prand(I|m,S): 亂數造成I的機率

在這裡使用到的fragmentation rule,(決定何種ion fragment跟peak intensity比較容易被觀察到) ; 有三種因素影響到fragmentation rule:

(1)介於ion type之間的相依性和相關性 : 各種ion type彼此的關係 (圖1的一般箭頭)
(2) 切的位置也會有影響(圖1的虛線箭頭位置)
(3) 如果切的位置為N-terminal或者C-terminal端也會有影響 (圖1的粗線位置)

心得: 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的相似性

心得:On de novo interpretation of tandem mass spectra for peptide identification(2003)

說明:
通常最常見的fragment是a,b,y, 而高能的儀器通常會產生除了其他種的ion,例如, internal ion等

一般來說,目前用來分析tandem mass資料的軟體都有以下三個模組:

(1)Interpretation(預備資訊):
輸入:
MS/MS spectrum
輸出:
詮釋過後的MS/MS data, 可能包括了parent peptide mass, partial 或者complete sequence tag或者combination of sequence tag和molecular massed

(2) Filtering (找出可能的peptide):
輸入:
詮釋過後的MS/MS data 和peptide sequence database
輸出:
可能產生MS/MS spectrum的peptide

(3)Scoring(開始算分):
輸入:
可能的peptide和MS/MS spectrum
輸出:
將peptide計分並且排序,並給予一個p-value(該計分分數可以被隨機達到的機率)

說明:
如果我們能夠知道一個Peak是屬於何種ion type,則我們就可以猜出這個sequence的前段部分之質量, 例如: 在圖2中, 一個peptide的mass是925, 如果我們切成b和y-ion兩部分,則如果我們找到633這個peak是y-ion的話, 則我們可以推對b-ion(前段部分)的mass就是SGF

SHERENGA的作法 :

Dancik 提出spectral graph的概念:

每個peak都對應到幾個node, 每個node都代表了一種ion type, 如果某個node u可以連到V且差距為某個AA,將其連起來, 其中找到最長的path就是該sequence

缺點: 這種方法會造成最長的path裡會連到許多是來自於同一個peak的node

這篇Paper方法的主要概念:

(1)會針對大部分常見的ion type,不僅是a, b, y, 也包含neutral loss

(2) 針對強度高的noise進行扣分,針對interpreted peak和被指定的ion type進行加分

(3) 利用dynamic programming找出sub-optimal的interpretation, 包含core-interpretation(指與optimal interpretation同樣對某些peak指定相同的ion)

概念:
(1.)盡量找出對應到同一個amino-acid的mass數目,並使其最大化
(2.)由於有可能peptide斷的時候不完全,因此有的時候不會對到, 我們將一些已經對到的peak最大化,並利用沒有對到的peak來作為扣分的基礎

方法概述:
(1) 找出一些Peak,這些Peak之間進行排序,R1,...Rm, 假設ri=Ri-Ri-1, 如果r1+r2....rm可以等於一個Parent mass,則我們取出這些Peak的組合

像這樣Peak組合可以有很多個, 我們用以下的步驟來選出比較好的Peak組合

(2) 這些Peak如果可以轉換成某種ion Type, 在Paper中的THEOREM 2中, 如果這樣的Peak不能轉換成某種ion type, 則我們會對這樣的Peak組合進行扣分, 但是Peak如果轉換後, 分成 小於 M/2和大於 M/2兩部分(我們都會看看轉換成ion type後, 何者的分數會比較高, 如果是轉換成<> M/2比較強, 就使用 > M/2, 就跟Ting Chen的paper是一樣的, 對於一個ion, 我們一次只選M/2的右邊或者左邊)


至於在5.1提到Suboptimal interpretation, 則是利用將演算法方法裡加一個參數可以記錄前幾個比較好的Peak組合, 如此就可以List所找出的答案

除此之外, 如果把S當成forward score (由上往下),則這裡又定義一個backward score, 如果把forward中和backward中的分數加總如果是最大的,則稱找到的Peak組合是core interpretation

心得: PEAKS Powerful Software for Peptide De Novo Sequencing by MS MS(2003)

Peaks有四個步驟:
(1) 對原始資料前處理
(2) 對於給定的ion計算前10000最有可能的ion
(3) 重新評定選出來的10000條sequence
(4) 計算被評定最高的sequence之confidence

其中每個步驟分述如下:

(1)對原始資料前處理:
包括noise filtering, Peak centering和deconvolution(尚未在paper描述方法); 這個部分很重要, 因為這篇paper發現如果在這個部分處理的好,準確率往往會提高;可是如果我們使用儀器廠商所附的軟體,出來的結果往往會差很多

(2) 對於給定的ion計算前10000最有可能的ion

想法: 如果一個sequence的ion跟高強度的Peak相符數量越多的話,則出來的結果越有可能是正確的sequence

作法:(針對a,b,c,x,y和b/y-17/18)
產生所有可能的peptide,並依照理論值推論出可能的ion質量位置 , 例如,我們從某個peptide推出的B-ion,如果恰巧有個mass m很靠近的話,則我們進行算分動作

算分方法:

如2338頁的公式(1)-->針對y-ion, 其中h是欲定y-ion的強度, m'-m是跟預定的mass相比較的誤差, 至於h, h1, h2, h3分別指y-ion, X, y-H2O, Y-NH3的強度, 意即我們用這些ion的強度跟y-ion相比,並以此作為輔助說明Y-ion的存在程度, 我們可以從公式看到, 如果這些ion跟Y-ion強度越相近,則代表Y-ion越有可能存在的 (但是對於b-ion而言, 就要a ,c, b-H2O, B-NH3), 然後從裡面選出分數最高的10000條

(3)重新評定選出來的10000條sequence
重新評定的方法: 將mass error tolerance訂的更嚴苛, 並且將immonium ion和internal cleavage ion也考慮進去(為了效率並沒有在第二步驟的時就考慮進去)(至於怎麼算的,並沒有在裡面說清楚-->因為Peaks是商業軟體)

(4)計算被評定最高的sequence之confidence
由於第三步驟算出來的是尚未normalize的分數,無法在不同組別之間將這樣的分數拿出來進行比較,因此我們會根據score的分佈圖進行選擇最佳的sequence, 為X=exp(cx), c是由Peaks從spectrum測定過來的(沒有說怎麼做的)
最後,這篇paper也會針對每個AA的信心程度進行運算,告訴使用者每個AA的存在可能性

用average signal intensity來判定一個圖譜的好壞:

average signal intensity=s/m; s: 所有abundance超過2之peak的abundance總和
m : precursor ion的mass

因此, 如果mass越大者, 則就不容易辨別, 理論上需要的abundance的總和也要越大, 跟此公式相符

心得: 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就少? 這樣好像不是很合理 )

心得:Automated Interpretation of High-Energy Collision-Induced Dissociation Spectra of Singly-Protonated Peptides by SeqMS a Software Aid for De(SeqMS)

SEQMS
這一篇Paper的作法:

這一篇方法並不複雜 , 主要是考慮到許多化學的特性在裡面, 因此利用這些特性(包含各種特性出現的機率)來算出正確的Sequence

主要方法流程:

全部轉成b-ion的Graph, 根據轉換前的ion-type之機率累加在圖論中各個連接線之間的分數(如何算出分數詳見裡面的公式-->P1869中的 scoring method
和利用Table 1的轉換表和機率表); 最後選出分數最高的sequence

附註:
因 為有一些immonium ions是在b-和y-ion會同時發生, 例如: 在m/Z 72出現的時候, 我們可以說是val的immonium ion(因為immonium ion中是會把CO都切掉,但是切掉後會帶一個正電,因此,會是= Total AA mass+ H -CO=S-27)或者N-terminus帶有Ala的peptide所引起的(如果b-ion只有Ala, 則算法=Ala mass+1=72.04); 為了避免有以上的情況,就是相衝的情形,因此,我們把b和y-ion的最小值設在129和147(這個不知道為何這樣設)

P1869中的 scoring method

列出符號所代表的意思:
P: 代表在table中出現的機率(Probability)
B: 代表在table中出現的Bounus
Xr: 代表對於在圖論中推論出每個residue之比重因子(列於table 2: 注意! 這個table對各種AA的各種ion的各種type都有不同的比重)
Mr: 表示在圖論中推論出的residue(為一個AA)之mass

藉 由實際上應該得到side-chain的ion數目跟理論上得到的數目進行比較,來為side-chain進行比重; 也就是說, 實際上對於某個由圖論上所得到的AA來說,如果實際上得到的side chain越多,則越可以證實是這個side-chain,自然比重也越多

心得: Sequence database searches via de novo peptide sequencing by tandem mass spectrometry(LuteFisk V.1)

Paper:

Taylor, J. A. and R. S. Johnson (1997). "Sequence database searches via de novo peptide sequencing by tandem mass spectrometry." Rapid Commun Mass Spectrom11(9): 1067-75.

方法概述:
這一篇Paper主要利用de novo sequencing做出來的東西去做peptide identification，裡面的de novo sequencing的方法可以拿出來使用

第一步:將CID的Data匯入到程式:

基本上,Data可以分為兩種,
1.centroided bar plot(有中心點的直方圖)

2.profile data(可以說是原始資料)

如果是屬於第二類的話,則我們要進行以下步驟

1. 五個點的smoothing

2.設定某個local Window(Window大小可以由使用者或者解析度決定),如果local window中的最大點大於所訂的值,則我們可以可以根據weight(沒有說怎麼算)對每個ion訂出M/Z值

如果儀器有測量錯誤的,也可以藉由使用者的設定調校回去

第二個步驟:利用一些對應的表格將ion轉成可能b-ion,並表示出這個轉換好的b-ion mass(這個paper利用N-和C-terminal的evidence list, evidence list就是包含可能的b-ion mass)

理論上,我們不會知道哪些ion會出現在spectrum裡面,因此我們要對於每一個出現在spectrum的ion假設成所有可能的ion type(例如: a,b,c,x,y,z...)

第一步:先將所有的ion假設是b-ion,因此,在圖2中的155,173,184,201,783,800都被假設是b-ion,因此,在N-terminal的evidence list圖(都是要用來表示b-ion)中對於這幾個位置的intensity先給予1或其他加權的值

第二步驟:針對轉換表中b-17和b-18進行轉換

轉換的方法:將所有的ion假設為b-17和b-18, 然後轉換成b ion的質量,如果有出現在原來的spectrum,則將轉換後的b-ion mass寫進或累加到N-terminal的evidence list裡,例如: 如果我們把155.0假設成b-18,則找到的b-ion就是173,而173也確實出現在原始spectrum裡面,則我們要把173(注意! 不是155.0,因為轉換後的才是b-ion,而N-terminal evidence list就是要找b-ion)寫進去N-terminal evidence list並且給予分數(增加intensity); 又例如: 173.1如果是假設成b-17或b-18,轉換成b-ion的質量是190和191,都沒有出現在原始spectrum中,則我們不會把190和191加入N-terminal evidence list中

最後一個步驟:

將N-terminal 和 C-terminal evidence list結合在一起,也就是將圖2中的b 和C結合在一起,X軸就是m/Z,如果在同一個m/z有值的,就累加起來 ; 但是, 有那種切在0的位置或切在最後的位置(就是都沒被切到的)(C- and N-termini者),他們在m/z中的intensity就任意指定

加分步驟:

這個程式會對於某些b-ion(可以與C-terminus差距在某些AA質量的和) 的intensity進行加分

因為對於一個連續的ion series(就是中間可以差距某些AA的質量和)來說, 比較可能是單純從N-terminus接起來或單純從C-terminus接起來的機會比是在N-或C-terminus間一直跳動的機會要來的大很多,因此,有這樣連續的情形我們會考慮為是單純從C-或N-terminus接起來

註明:

我們可以從N-terminal開始取下一個一個AA(或者dipeptides),取到最後的長度可以由使用者決定, 由於我們可能取下很多subsequence(這些subsequence的分數可以由他們b-ion的intensity總和來得到),根據他們的分數(分數也代表這個sequence的可能性)來決定選取或丟棄

如果找出的subsequence符合peptide的mass,則完整的sequence就會拿來做排名

目標 : 將Paper的方法讀熟 , 並且將每一篇Paper的方法寫下來

預計一個禮拜內將所有Paper的方法都整理出來 , 願上帝保守

Paper List of de novo sequencing

List of De novo sequencing Paper:

[1997]
Taylor, J. A. and R. S. Johnson (1997). "Sequence database searches via de novo peptide sequencing by tandem mass spectrometry." Rapid Commun Mass Spectrom 11(9): 1067-75.

[1998]
Fernandez-de-Cossio, J., J. Gonzalez, et al. (1998). "Automated interpretation of high-energy collision-induced dissociation spectra of singly protonated peptides by 'SeqMS', a software aid for de novo sequencing by tandem mass spectrometry." Rapid Commun Mass Spectrom 12(23): 1867-78.

[1999]
Dancik, V., T. A. Addona, et al. (1999). "De novo peptide sequencing via tandem mass spectrometry." J Comput Biol 6(3-4): 327-42.

[2000]
Fernandez-de-Cossio, J., J. Gonzalez, et al. (2000). "Automated interpretation of low-energy collision-induced dissociation spectra by SeqMS, a software aid for de novo sequencing by tandem mass spectrometry." Electrophoresis 21(9): 1694-9.

[2001]
Chen, T., M. Y. Kao, et al. (2001). "A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry." J Comput Biol 8(3): 325-37.

Taylor, J. A. and R. S. Johnson (2001). "Implementation and uses of automated de novo peptide sequencing by tandem mass spectrometry." Anal Chem 73(11): 2594-604.

[2002]
Olaf Lubeck, Christopher Sewell, Sheng Gu, Xian Chen, and D. Michael Cai, Proc. IEEE 90(12):1868–1874, Dec 2002

[2003]
Tabb, D. L., A. Saraf, et al. (2003). "GutenTag: high-throughput sequence tagging via an empirically derived fragmentation model." Anal Chem 75(23): 6415-21.

Lu, B. and T. Chen (2003). "A suboptimal algorithm for de novo peptide sequencing via tandem mass spectrometry." J Comput Biol 10(1): 1-12.

Ma, B., K. Zhang, et al. (2003). "PEAKS: powerful software for peptide de novo sequencing by tandem mass spectrometry." Rapid Commun Mass Spectrom 17(20): 2337-42.

Bafna and Edwards (2003) "On de novo interpretation of tandem mass spectra for peptide identification" [RECOMB]

[2004]
Heredia-Langner, A., W. R. Cannon, et al. (2004). "Sequence optimization as an alternative to de novo analysis of tandem mass spectrometry data." Bioinformatics 20(14): 2296-2304.

Frank, A. and P. Pevzner (2005). "PepNovo: De novo peptide sequencing via probabilistic network modeling." Analytical Chemistry 77(4): 964-973.