想法整理及注意事項

1. 要考慮Spectrum Quality嗎? 用Intensity，Peak密集度或者考慮Random Peak?

2. 要用b-ion或者y-ion或者所有ion算分？如果要用b-ion，要用transformation table或者其他方法？

3. Scoring Function（用來比較Predicted Spectrum和Experimental Spectrum）

A. 僅利用b-ion或y-ion或用全部可能的ion

B. 加入Intensity的概念

C. 加入Random Peak的概念

D. 利用機率對每個AA進行投票（Google概念）

E. 沒有match到的要扣分嗎？（一般要，但GA適合嗎？）（跟IR一樣，如果有not的時候要去掉嗎？）

F. 利用Alignment比較圖譜之間的相似（比較Peak之間差異值的相似性）

G. 利用段與段之間的差異值來跳過某些被跳過的片段

H. 延伸部分tag，中間用GA接

4. 結合不同的方法做出來的結果如果有ambiguity的地方，用GA或其他方法解決

想法整理

想法整理：

1. 利用b-ion（要先判定）跟y-ion的強度決定de novo 出來的Quality（利用Si’=X-Si-d），見JCB的SHERENGA: De novo peptide sequencing via tandem mass spectrometry(1999)。

2. 利用這種b-ion轉成y-ion後出現類似peak的數量增強scoring function。

3. 將Random Peak的概念加入GA-based de novo sequencing。

4. 會不會最好的分數不一定會代表原來的sequencing。

(Ans: 1. 有可能，所以Ting Chen提出suboptimal，2. 可能代表你的scoring function不好)。

5. 利用Google的Rank方式來找出最有可能的Peptide(de novo)。

6. 將Intensity的資訊考慮進去GA model。

7. 想出一個方法來解決GA中一個sequence如果差異一個AA，整個圖譜就會差異很大的狀況。是不是可以每個圖譜之間的Peak之difference進行match

例如: 1. A B C D (假設之間的差距用d1, d2, d3表示) 2.A’B’C’D’ (假設之間的差距用d1’, d2’, d3’表示)，我們可以利用d1, d2, d3來align(與GA paper方法不太相同，GA是A’-A利用相減來得到)

8. 最好出來能夠reporducible

9. 另外，沒有match到的要扣分？（一般都要，但適合在GA嗎？跟IR一樣，如果有not者要去掉嗎？）

10. 如果用GA paper第四項的方法，就不容易判斷是否相似，例如：

Experiment: GAP (58, 129, 226)

Predication: GSP (58, 145, 242)

P1 P2 P3

------------------

E1|0 -87 -184

E2|71 -16 -113

E3|168 81 -16

如果照GA的方法，不容易看出加什麼樣的值，如果多個的話又更不容易了

但是如果使用GAP，GSP之sequence差，就可以看出：

例如：

58 129 226 à 58, 71, 97

58 145 242 à 58, 87, 97

利用這種相同差異的方式可以更容易判斷相似性，且要有相似性à可以考慮用Blast或其他alignment的方式進行（要考慮GAP的狀況）

11. 或者可以考慮GAPAPG，其中GAPAPG跟APG可以取中間段與段之間的方式就可以跳過不符合者。

12. 利用LuteFisk跟GA（或其他方法）進行混合，可以看出兩個相似的sequence在哪，並解決ambiguity的地方。

13. 先計算一次自己的作法實驗是否合理，自己可以先用筆算(用alignment)的方式（可以利用GA Paper裡面的資料）。

14. 如果要算GA的scoring function，可以先將experimental之b-ion(利用各種ion加強b-ion分數找出後)，再進行match(alignment或者GA)。

15. 查我們所用的MS是High-Energy 或者Low Energy，並查這兩者的不同。

16. 是不是可以將PepNovo和GA的方法結合，因為PepNovo是找出P(S|P)，這個部分似乎可以採用GA，目前的方法是因為search space過大，不容易找出答案，因此我們可以用GA+PepNovo

17. 將各種ion相依性考慮在系統內

18. 利用密度判定品質的好壞（GA可以進行score），太密集者，雜訊過多，可能代表noise多，要扣分。

19. 利用一次延伸一個的作法，中間無法接的，用GA

產生b-ion是否跟著要產生y-ion

心得: Algorithms for de novo peptide sequencing using tandem mass spectrometry(2004)

使用de nov sequencing的六個理由:

(1) 對於有興趣的protein之sequence可能不存在資料庫裡
(2) Gene-finding的程式可能有錯, 因此即使資料庫裡面有這樣的資料, 也會找不出來
(3) 有些科學家可能在學習基因體學之前想先學習蛋白質體學, 此時就沒有sequence database可以用
(4)Gene經過alternative splicing或者SNP後可能會有新的protein
(5)de novo sequencing對於找mutation和modification的AA會有幫助
(6)當database search的結果有ambiguous的時候,可以利用de novo sequencing來做驗證

目前提過的方法有下列幾種:

(1) 產生所有可能的sequence並且產生理論的spectrum, 並與實際的spectrum進行比較-->計算量過大

(2) 一次延伸一個, 這裡的問題在於中途如果有比較不好的data就不容易皆起來

(3) 利用使用者繪圖的介面來表示資料, 這種方法對於實際的問題沒有太大的幫助,但是可以幫助使用者很快地瞭解資料

(4)使用graph theroy

SeqMS的作法:
(1) 將ion type對上每個可能的機率
(2) 每個peak根據(1)轉換成spectrum graph
(3)藉由兩個node之間的差距進行連結
(4) 從N-terminal到C-terminus找最短路徑

Sherenga的演算法:
(1) 從一大堆的已知的spectrum學習ion type的特性
(2) 利用這些ion的特性將S轉化成spectrum(一個S可能可以轉換成k種ion), 因此, 1個ion在spectrum graph裡面就有k個點, 我們計算兩個點之間的差距來得出可能AA, 要找出最長的距離, 這樣的方法可能會找到許多不符合現實狀況的sequence

心得 : 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的總和也要越大, 跟此公式相符