利用二級質(zhì)譜自動進行聚糖結(jié)構(gòu)解析的從頭開始算法

董 梁，石 冰，李艷博，王 冰

(1.山東大學(xué)計算機科學(xué)與技術(shù)學(xué)院，山東 濟南 250101；2.中國科學(xué)院計算技術(shù)研究所，北京 100190)

?

利用二級質(zhì)譜自動進行聚糖結(jié)構(gòu)解析的從頭開始算法

董 梁1，石 冰1，李艷博2，王 冰2

(1.山東大學(xué)計算機科學(xué)與技術(shù)學(xué)院，山東 濟南 250101；2.中國科學(xué)院計算技術(shù)研究所，北京 100190)

關(guān)于不借助數(shù)據(jù)庫，根據(jù)質(zhì)譜自動地從頭開始解析聚糖結(jié)構(gòu)(包括單糖組成、排列信息和單糖之間的連接信息)已有多年研究，然而，如何快速準確地得到結(jié)果仍然面臨諸多挑戰(zhàn)。為了降低時間復(fù)雜度，現(xiàn)有的方法要么采用貪心法或者啟發(fā)式算法，這些算法本身就是不精確的，難以保證得到結(jié)果的準確性；要么采用剪枝法或者動態(tài)規(guī)劃之類的精確算法，但是這類算法不僅時間復(fù)雜度較高，而且其中大量使用的假設(shè)和理想化模型忽視了許多對結(jié)果有影響的實驗細節(jié)。諸如打分函數(shù)中對不同候選結(jié)構(gòu)重復(fù)使用相同譜峰進行評分的問題，先前的精確算法常常選擇回避和無視，這些被忽視的細節(jié)最終導(dǎo)致結(jié)果的不準確。本工作提出了基于迭代增長的方法“自底向上”地利用譜圖解析聚糖結(jié)構(gòu)的算法。與以往迭代方法不同，該算法中增長的單位不再是單糖，而是在算法中產(chǎn)生的子結(jié)構(gòu)，這使得算法的運行速度大大加快。在將各種實驗細節(jié)納入算法流程的基礎(chǔ)上，通過對20種聚糖的二級質(zhì)譜圖解析以及與先前算法的比較，證實了該算法具有較高的準確性(75%聚糖的正確結(jié)構(gòu)被算法解析為第一)。

二級質(zhì)譜；聚糖；結(jié)構(gòu)解析；從頭開始預(yù)測；動態(tài)規(guī)劃算法

生物信息學(xué)是利用應(yīng)用數(shù)學(xué)、信息學(xué)、統(tǒng)計學(xué)和計算機科學(xué)的方法來研究生物學(xué)問題的一門學(xué)科。在生物信息學(xué)中，核酸、蛋白質(zhì)和糖被并稱為三種重要的生物大分子，對構(gòu)成生物組織、調(diào)控生命活動起著至關(guān)重要的作用，一直是科學(xué)研究的重點，而聚糖常常作為修飾連接在蛋白質(zhì)和脂質(zhì)上，可能是自然界中結(jié)構(gòu)最為復(fù)雜的大分子之一[1]。與核酸、蛋白質(zhì)的研究相比，人們對于與糖相關(guān)的規(guī)律知之甚少，糖組學(xué)發(fā)展的滯后不利于與之交叉的蛋白質(zhì)組學(xué)、基因組學(xué)的進一步深入研究。

生物體中的蛋白在生成之后大多要進行糖基化，糖基化不僅能增強被修飾的蛋白對蛋白酶的抵抗能力，促成許多蛋白之間的相互作用，還參與細胞分化、細胞內(nèi)環(huán)境調(diào)節(jié)、免疫功能等生命活動[2-3]。 聚糖結(jié)構(gòu)分析是糖蛋白研究不可或缺的部分，對糖結(jié)構(gòu)的深入研究將極大地促進目前一些疑難疾病的治療。 但是，由于聚糖結(jié)構(gòu)有分支的特性，與多肽的直鏈結(jié)構(gòu)相比，確定聚糖的結(jié)構(gòu)要復(fù)雜得多，比如，4種氨基酸只能構(gòu)成24種肽段，而4種單糖卻能構(gòu)成200種以上的聚糖。這是因為要完整地描述一種給定的聚糖，至少應(yīng)該給出以下信息：單糖組成、單糖序列拓撲結(jié)構(gòu)以及單糖兩兩之間的連接信息。目前，用于聚糖結(jié)構(gòu)解析的技術(shù)主要有質(zhì)譜法、凝集素抗體陣列法(lectin and antibody arrays，LAA)、糖陣列法(glycan array，GA)等。與其他技術(shù)相比，利用質(zhì)譜法進行聚糖結(jié)構(gòu)解析只需要很少的實驗材料，而且速度快、靈敏度高[4]，已經(jīng)成為高通量自動聚糖解析的主流方法[5]。但是，它不能像LAA 方法那樣直觀的顯示聚糖的拓撲結(jié)構(gòu)，也不能顯示單糖之間的連接情況，這給解析聚糖結(jié)構(gòu)帶來了困難。在質(zhì)譜圖中，環(huán)內(nèi)斷裂產(chǎn)生的離子峰能夠提供大量信息[6-10]。由于跨環(huán)斷裂比糖苷鍵斷裂需要更強的能量，在低能量的PSD(post-source decay)譜中，環(huán)內(nèi)斷裂離子峰出現(xiàn)較少；而在高能量的CID(collision-induced dissociation)譜中，可以很容易地觀察到環(huán)內(nèi)斷裂形成的離子峰。隨著質(zhì)譜技術(shù)的離子化方法的發(fā)展，如電噴霧電離(ESI)、基質(zhì)輔助激光解吸電離質(zhì)譜(MALDI-MS)等，給聚糖結(jié)構(gòu)解析帶來了方便。但是，就像其他生物信息學(xué)中的應(yīng)用問題一樣，通過質(zhì)譜技術(shù)得到的譜圖包含了大量的嘈雜信息，如何使用計算機有效地分析、處理，充分利用高能量譜圖中的譜峰信息來實現(xiàn)聚糖結(jié)構(gòu)的準確自動解析，仍然是糖組學(xué)領(lǐng)域的重點和難點問題。

目前，利用質(zhì)譜進行糖解析的方法可以分為兩大類，其中一類是只利用實驗質(zhì)譜從頭開始解析聚糖結(jié)構(gòu)，而如何充分利用質(zhì)譜信息是得到準確解析結(jié)果的關(guān)鍵。Gaucher等[11]提出了STAT 工具，通過遍歷所有滿足條件的聚糖結(jié)構(gòu)，返回與實驗譜圖最相似的結(jié)構(gòu)，這種方法的解空間會隨著聚糖聚合度的增加而呈指數(shù)增加，不具備實際價值。Tang 等[12]提出了動態(tài)規(guī)劃算法自動解析聚糖結(jié)構(gòu)，但是該算法更傾向于產(chǎn)生線性而非分支的結(jié)構(gòu)，而且給出的打分函數(shù)非常簡單。 Mizuno等[13]最早將關(guān)系樹運用于聚糖結(jié)構(gòu)解析。在此基礎(chǔ)上，Ethier等[4]提出了基于StrOligo算法進行聚糖結(jié)構(gòu)的自動解析，能夠在2 min之內(nèi)解析出一個聚糖的結(jié)構(gòu)(包括算法運行和輸入輸出的時間)，但是他們使用了只適用于N糖的經(jīng)驗規(guī)則，而沒有考慮A/X 碎片離子。An等[14]提出了能對N 糖和O糖進行解析的方法，但是操作復(fù)雜，不適合聚糖的自動解析。Shan等[15]證明了從頭生成解析聚糖結(jié)構(gòu)的是NP-Hard，并采用了一種啟發(fā)式算法來降低求解問題的時空開銷。但是，啟發(fā)式算法非常依賴于經(jīng)驗參數(shù)的選擇，且只能求得近似的最優(yōu)解。

另一類方法是通過與特定的多糖數(shù)據(jù)庫進行比對來解析實驗聚糖的結(jié)構(gòu)，這類算法一般要執(zhí)行數(shù)據(jù)庫搜索和相似性比較兩個步驟，并返回數(shù)據(jù)庫中與實驗聚糖最相似的結(jié)構(gòu)。如果數(shù)據(jù)庫中沒有與實驗聚糖相近的結(jié)構(gòu)，得到的結(jié)果將與真實結(jié)果產(chǎn)生較大的差距。采用這種方法的代表性工作有當前廣泛使用的搜庫工具GlycosidIQ，這些工具通過對GlycoSuiteDB、SweetDB等聚糖數(shù)據(jù)庫的搜索以實現(xiàn)糖結(jié)構(gòu)解析，并得到較好的結(jié)果。然而，當前聚糖數(shù)據(jù)庫中的數(shù)據(jù)還不完整，因此采用從頭開始的方法進行聚糖解析仍然非常重要。

到目前為止，能兼顧解析速度與準確性的算法比較少見，而且大多存在重復(fù)利用譜峰對候選結(jié)構(gòu)進行打分的問題?？紤]到從質(zhì)譜解析聚糖結(jié)構(gòu)處理噪聲信息和其他細節(jié)，本工作給出了一個包含數(shù)據(jù)預(yù)處理和候選結(jié)構(gòu)篩選步驟的算法，它不使用糖數(shù)據(jù)庫作為參考,而是基于迭代思想從頭進行糖結(jié)構(gòu)的快速解析。此外，在對候選結(jié)構(gòu)進行模擬打碎產(chǎn)生理論譜的過程中，本工作給糖苷鍵斷裂和環(huán)內(nèi)斷裂以不同的概率，在相似性打分函數(shù)中考慮譜峰豐度的信息。并通過對20種從人體血清中提取的聚糖進行解析實驗，來證實該算法的準確性。

1 實驗方法

1.1 單糖結(jié)構(gòu)的表示方法

本工作用到的單糖主要是高等動物體內(nèi)常見的聚糖組成單位，命名為集合G。單糖的名稱和圖標列于表1。

把由n個單糖組成的聚糖結(jié)構(gòu)看作一個具有n個結(jié)點的有向無環(huán)圖，其中的頂點代表表1中列出的某種單糖，一條有向邊由一個二元組(m1，m2)表示，意義是該邊由頂點m1指向頂點m2。在本工作中，默認的方向是從聚糖的非還原端指向還原端。在一個子圖中，最靠近聚糖非還原端的頂點被稱為子圖的頭頂點，而遠離還原端的頂點被稱為尾頂點。算法中將聚糖結(jié)構(gòu)的每個單糖都視作一個子結(jié)構(gòu)，即一個子圖，并用Si(1≤i≤n)表示。一條有向邊的連接信息可以是1-2，1-3，1-4或者1-6，被記作集合L。任意一條邊都是由它的頂點集合二元組以及連接信息共同表示的。

表1 單糖名稱和表示

注：1) 己糖相對分子質(zhì)量為180.06，這里將每個單糖看作一個完整殘基，由于實驗中對殘基進行甲基化，并添加加合物Na，因此質(zhì)量標為217.13，這對于表中其他單糖也適用。

圖1 聚糖殘基離子示例Fig.1 An example of representation of glycan ions

表2 單糖支持的連接方式

注：1) P表示該單糖支持相應(yīng)的連接方式，N表示不支持

1.2 算法流程

算法的輸入是實驗聚糖的質(zhì)譜數(shù)據(jù)和母離子質(zhì)量mparent。質(zhì)譜數(shù)據(jù)格式為MALDI數(shù)據(jù).run(Shimadzu)，可以用Shimadzu Biotech MALDI-MS軟件打開并轉(zhuǎn)換成.mzXML格式，以便于BUP算法解析，對于其他格式的質(zhì)譜數(shù)據(jù)，可用工具Mascot Distiller將其轉(zhuǎn)換為.run格式的質(zhì)譜數(shù)據(jù)以實現(xiàn)兼容。算法依次執(zhí)行以下操作進行聚糖結(jié)構(gòu)的解析：

1) 首先，將實驗譜按每k個譜峰一組劃出若干窗口，較小的k值將產(chǎn)生更多的高分候選結(jié)構(gòu)，因為這會對譜峰重復(fù)打分；而較大的k值使得算法的運行時間更短，但是可能會遺漏重要的候選結(jié)構(gòu)。在本工作中，設(shè)置k=40。然后，分別計算每個窗口中譜峰豐度的均值和方差，并將豐度小于均值減去3倍方差的譜峰去除掉。再計算每個窗口中最高譜峰的豐度，把該窗口內(nèi)所有譜峰的豐度都除以最大豐度。最后，對質(zhì)譜進行同位素剝離去除所有非單一同位素峰，這樣實驗譜中需要處理的峰數(shù)將大大減少，也減少了譜峰發(fā)生隨機匹配的概率。

2) 假定已知子圖S(hseti,hli,inseti,inli,testi,tli)，根據(jù)基于概率的碎裂模式隨機打碎該子圖代表的子結(jié)構(gòu)來產(chǎn)生理論譜，用到的碎裂模式將在下面的處理步驟中詳述。那么，理論譜譜峰的豐度可以用來對子結(jié)構(gòu)與實驗結(jié)構(gòu)的相似度進行打分，打分函數(shù)為

(1)

(2)

2 實驗部分

2.1 主要儀器和試劑

AMIMA-QIT基質(zhì)輔助激光解吸電離-四極離子阱-飛行時間質(zhì)譜儀：日本Shimadzu公司產(chǎn)品；Waters Alliance 2695高效液相色譜儀，DEAE-52纖維素： 美國 Waters公司產(chǎn)品；Fast Flow色譜柱：瑞典GE Healthcare公司產(chǎn)品；Sephadex G-100凝膠：瑞典Phamacia 公司產(chǎn)品；2AB聚糖標記試劑盒：英國Ludger公司產(chǎn)品；PNGase F(分析純)，Tris(分析純)：美國Roche公司產(chǎn)品；10% SDS溶液，10%甲酸水溶液，四甲基乙二胺(分析純)：北京雷根生物技術(shù)有限公司產(chǎn)品；APS(分析純)：上海基星生物技術(shù)有限公司產(chǎn)品；DDT(色譜純)：上海江萊生物科技有限公司產(chǎn)品；其他試劑均為分析純。

2.2 樣品制備

實驗中用到的聚糖提取自人體血清和牛胰腺，來自牛胰腺的聚糖樣本使用Saba等[17]給出的方法進行處理。血清樣本按以下步驟處理：用0.625 mL Tris(pH 6.6)溶液，1 mL 10% SDS溶液和3.375 mL蒸餾水配制緩沖液，取5 μL血清樣本置于平底微孔板上，添加2 μL緩沖液、2 μL蒸餾水和0.5 μL 0.5 mol/L二硫代蘇糖醇(DDT)溶液，在65 ℃條件下培養(yǎng)15 min。向樣本中添加1 μL 0.1 mol/L碘化酰胺溶液，在室溫黑暗條件下培養(yǎng)30 min。將22.5 μL 1.5 mol/L Tris(pH 8.8)，1 μL 10% SDS，1 μL 10% APS溶液和1 μL四甲基乙二胺(TEMED)加入樣本，混勻成凝膠。將凝膠置入濾板，渦旋，用1 mL乙腈沖洗10 min，去除濾板中液體，用1 mL 0.2 mol/L碳酸氫鈉溶液反復(fù)清洗2次，再用1 mL乙腈沖洗1次。對凝膠進行干燥處理，用加入50 μL濃度為0.1 u/mL PNGase F (Roche)[18]的碳酸氫鈉溶液(pH 7.2)浸泡凝膠5 min來分離聚糖和多肽。用200 μL蒸餾水反復(fù)清洗凝膠3次，再各用200 μL乙腈和蒸餾水進行清洗1次，收集洗脫的N糖，進行干燥處理，即得到粗多糖樣品。將多糖樣品溶于少量蒸餾水中，采用DEAE-52纖維素柱(1.6 cm×20.0 cm),依次用蒸餾水和0.1～2.0 mol/L碳酸氫鈉溶液進行洗脫，采用苯酚-硫酸法檢測，收集相應(yīng)成分，透析脫鹽，濃縮后用 Sephadex G-100凝膠柱(1.6 cm×80.0 cm)進一步分離純化，0.02 mol/L Tris-HCl(pH 7.2)溶液洗脫，收集洗脫液，冷凍干燥，備用。取部分實驗聚糖樣本，用2AB聚糖標記試劑盒進行標記，用乙腈洗去多余的2AB，氨水將標記過的N糖洗脫，經(jīng)過干燥處理后，即可再次溶解于一定量的蒸餾水來進行HPLC分析。使用帶2475熒光檢測器的Waters Alliance 2695高效液相色譜儀進行分析，一系列外切糖苷酶，包括NANI唾液酸酶、ABS等協(xié)助分析，并與多糖數(shù)據(jù)庫GlycoBase進行匹配以得到聚糖組分的單糖組成、連接信息和拓撲序列信息。實驗中使用的所有聚糖列于表3。

2.3 實驗條件

2.3.1 質(zhì)譜條件 解吸電離(DI)離子源，基質(zhì)為2,5-二羥基苯甲酸，電子能量100 eV，質(zhì)量掃描范圍m/z40～5 000。

2.3.2 實驗平臺條件 BUP算法用java語言編程，運行在一臺處理器是Intel Pentium(R),2.8 GHz，內(nèi)存4 GB的計算機上，編譯器是JDK 1.6。在實驗中，用于比較的StrOligo算法運行于相同的計算機上，使用的編程環(huán)境是Borland C++ Builder 6.0。

表3 實驗所用到的聚糖

續(xù)表3

3 結(jié)果與討論

對表3中給出的20種聚糖進行解析實驗，這些聚糖的結(jié)構(gòu)都經(jīng)過了人工解析，因此可以被用于檢驗算法的準確性。實驗的總體結(jié)果示于圖2，而詳細結(jié)果列于表4。盡管一些錯誤的結(jié)構(gòu)也被列為第一，但是它們的數(shù)目并不大，而且與真實結(jié)構(gòu)相似。對被算法誤排名為第一的候選結(jié)構(gòu)進行分析，發(fā)現(xiàn)幾乎所有這些結(jié)構(gòu)都與真實結(jié)構(gòu)有相似的單糖組成，但是序列拓撲和某些連接關(guān)系卻不同，一些排名高于真實結(jié)構(gòu)的候選結(jié)構(gòu)，明顯不符合生物合成規(guī)則，這可能是因為不想引入過多生物學(xué)限制而影響算法的適用范圍，在該算法中沒有使用生物合成規(guī)則來限制候選結(jié)構(gòu)的生成，但相關(guān)的生物合成規(guī)則可以根據(jù)實際需要整合到算法流程中；此外，在生成理論譜的過程中給出的模型仍有較大地改進空間。總體來說，實驗結(jié)果證實了該算法具有較高的準確性。

圖2 BUP算法對實驗聚糖正確結(jié)構(gòu)排名的分布Fig.2 Rank distribution of the real structures given by BUP algorithm表4 對20種聚糖解析實驗的詳細結(jié)果Table 4 Detailed assignment results of 20 experimental glycan

聚糖編號候選結(jié)構(gòu)數(shù)后處理步驟前后處理步驟后真實結(jié)構(gòu)排名11721112292132321426315164151642317403181971619322110392111278232124551134431145251151691511622321217329302181581811928728220394373

作為一個實例，給出了16號聚糖的二級質(zhì)譜圖，示于圖3，同時給出了對該聚糖進行解析的結(jié)果，示于圖4?？紤]到候選結(jié)構(gòu)數(shù)目較多，圖4中只給出了部分排名高于真實結(jié)構(gòu)的候選結(jié)構(gòu)(將真實結(jié)構(gòu)以及排名列在最后)。

本工作將BUP算法與StrOligo方法進行對比，對20種實驗聚糖進行解析，實驗結(jié)果示于圖5a。其中，BUP算法和StrOligo算法都正確地給出了15個實驗聚糖的解析結(jié)果，但是StrOligo算法將2個實驗聚糖的正確結(jié)構(gòu)列為第3名，而BUP算法表現(xiàn)出更好的穩(wěn)定性。從表5可以看到，StrOligo算法與BUP算法的運行速度相當，但是考慮到所用的編程語言不同，StrOligo算法本身的效率可能高于StrOligo算法。

值得注意的是，本工作的實驗聚糖都是N糖，因此又進行如下實驗，在算法中過濾掉所有不滿足N糖特有的“核心”結(jié)構(gòu)的候選結(jié)果(這個過濾條件可以根據(jù)具體實驗條件由研究者進行選擇)，并且使用了“核心”結(jié)構(gòu)作為初始子圖，實驗結(jié)果示于圖5b?？梢钥闯?，StrOligo算法的結(jié)果并無改進，而BUP算法正確解析出16個實驗聚糖，且將其他聚糖的正確結(jié)構(gòu)列為第2名，準確度有明顯提高。

4 結(jié)論

本工作提出了一種準確的、可擴展的算法用于以質(zhì)譜從頭開始解析聚糖結(jié)構(gòu)，無須與已知聚糖數(shù)據(jù)庫進行比照或者借助額外的生物學(xué)合成規(guī)則。通過將聚糖結(jié)構(gòu)看作是有向無環(huán)圖，并利用一個六元組來完整描述聚糖子圖，算法將迭代過程中產(chǎn)生的子結(jié)構(gòu)當作擴增單位“自底向上”地重構(gòu)完整的聚糖結(jié)構(gòu)，使得算法在考慮了大量實驗細節(jié)的前提下，保持了較高的運行速度。算法在產(chǎn)生理論譜給糖苷鍵斷裂和環(huán)內(nèi)斷裂以差異的碎裂概率，并在打分函數(shù)中同時考慮了譜峰的質(zhì)荷比和豐度信息。通過記錄支持特定候選結(jié)構(gòu)的實驗譜峰集合并引入限制條件，算法解決了重復(fù)對譜峰進行計算的問題。經(jīng)過后處理步驟，算法在保留正確結(jié)構(gòu)的前提下過濾掉了大量的候選結(jié)構(gòu)。通過對20種實驗聚糖進行解析實驗，驗證了算法具有較高的準確性和較快的運行速度。但是實驗也發(fā)現(xiàn)，對于具有復(fù)雜分支結(jié)構(gòu)和大分子質(zhì)量的聚糖，生物合成規(guī)則的輔助仍然非常有益，對于算法難以確定的復(fù)雜聚糖的拓撲結(jié)構(gòu)和連接關(guān)系，一方面可以根據(jù)需要引入相關(guān)的生物合成規(guī)則，比如N糖特有的“核心”結(jié)構(gòu)規(guī)律等，另一方面由于一些拓撲信息和連接信息無法從二級質(zhì)譜中得到，應(yīng)該借助于三級甚至四級質(zhì)譜圖來確定，這也將是下一步研究的方向。

圖3 作為樣例的16號聚糖二級質(zhì)譜圖Fig.3 MS/MS of glycan No.16 as an example

注：真實結(jié)構(gòu)列在最后圖4 16號聚糖解析的詳細結(jié)果Fig.4 Detailed assignment results of glycan No.16 as an example

注：真實結(jié)構(gòu)排名越靠近1解析結(jié)果越準確圖5 引入生物規(guī)則之前(a)和之后(b)，BUP與StrOligo算法解析結(jié)果比較Fig.5 Structure assignment comparison of BUP and StrOligo algorithm before(a) and after(b) inducing an biosynthesis rule表5 BUP算法與StrOligo算法 對20種聚糖解析實驗的速度比較Table 5 Structure assignment speed comprison of BUP and StrOligo algorithm

聚糖編號BUP算法耗時/sStrOligo算法耗時/s108908520340413074062414815152692536201371731439884524249314320103353181156057112391340132953011428433215265233168128431774879118347372199199062011931164

[1] HART G W, COPELAND R J. Glycomics hits the big time[J]. Cell, 2010, 143(5): 672-676.

[2] LOHMANN K K, von der LIETH C W. GlycoFragment and GlycoSearchMS: Web tools to support the interpretation of mass spectra of complex carbohydrates[M]. Oxford University Press: Nucleic Acids Research, 2004.

[3] VOSSELLER K, WELLS L, HART G W. Nucleocytoplasmic O-glycosylation: O-GlcNAc and functional proteomics[M]. Biochimie: Biochimie, 2001.

[4] ETHIER M, SABA J A, SPEARMAN M, et al. Application of the StrOligo algorithm for the automated structure assignment of complex N-linked glycans from glycoproteins using tandem mass spectrometry[J]. Rapid Communications in Mass Spectrometry, 2003, 17(24): 2 713-2 720.

[5] SASAKI H, BOTHNER B, DELL A M. Fukuda carbohydrate structure of erythropoietin expressed in chinese hamster ovary cells by a human erythropoietin cDNA[J]. J Biol Chem, 1987, 262 (25):12 059-12 076.

[6] CHAPLIN M F, KENNEDY J F. Carbohydrate analysis[D]. New York: Oxford University, 1994: 221-289.

[7] LI D T, HER G R. Linkage analysis of chromophore-labeled disaccharides and linear oligosaccharides by negative ion fast atom bombardment ionization and collisional-induced dissociation with B/E scanning[J]. Anal Biochem, 1993, 211(2): 250-257.

[8] LI D T, SHEEN J F, HER G R. Structural analysis of chromophore-labeled disaccharides by capillary electrophoresis tandem mass spectrometry using ion trap mass spectrometry[J]. J Am Soc Mass Spectrom, 2000, (11): 292-300.

[9] CHAI W, LAWSON A M, PISKAREV V. Branching pattern and sequence analysis of underivatized oligosaccharides by combined MS/MS of singly and doubly charged molecular ions in negative-ion electrospray mass spectrometry[J]. Journal of the American Society for Mass Spectrometry, 2002, 13(6): 670-679.

[10]CHENG H L, HER G R. Determination of linkages of linear and branched oligosaccharides using closed-ring chromophore labeling and negative ion trap mass spectrometry[J]. Journal of the American Society for Mass Spectrometry, 2002, 13(11): 1 322-1 330.

[11]GAUCHER S P, MORROW J, LEARY J A. Stat: A saccharide topology analysis tool used in combination with tandem mass spectrometry[J]. Analytical Chemistry, 2000, 72(11): 2 331-2 336.

[12]TANG H, MECHREF Y, NOVOTNY M V. Automated interpretation of MS/MS spectra of oligosaccharides[J]. Bioinformatics, 2005, 21(Suppl 1): i431-i439.

[13]MIZUNO Y, SASAGAWA T, DOHMAE N, et al. An automated interpretation of MALDI/TOF postsource decay spectra of oligosaccharides. 1. Automated peak assignment[J]. Analytical Chemistry, 1999, 71(20): 4 764-4 771.

[14]AN H J, LEBRILLA C B. Structure elucidation of native N- and O-linked glycans by tandem mass spectrometry (tutorial)[J]. Mass Spectrometry Reviews, 2011, 30(4): 560-578.

[15]SHAN B, MA B, ZHANG K, et al. Complexities and algorithms for glycan sequencing using tandem mass spectrometry[J]. Journal of Bioinformatics And Computational Biology, 2008, 6(1): 77-91.

[16]DOMON B, COSTELLO C E. A systematic nomenclature for carbohydrate fragmentations in FAB-MS/MS spectra of glycoconjugates[J]. Glycoconjugate Journal, 1988, 5(4): 397-409.

[17]SABA J A, KUNKEL J P, JAN D C H, et al. A study of immunoglobulin G glycosylation in monoclonal and polyclonal species by electrospray and matrix-assisted laser desorption/ionization mass spectrometry[J]. Analytical Biochemistry, 2002, 305(1): 16-31.

[18]KüSTER B, WHEELER S F, HUNTER A P, et al. Sequencing of N-linked oligosaccharides directly from protein gels: In-gel deglycosylation followed by matrix-assisted laser desorption/ionization mass spectrometry and normal-phase high-performance liquid chromatography[J]. Analytical Biochemistry, 1997, 250(1): 82-101.

[19]CIUCANU I, KEREK F. A simple and rapid method for the permethylation of carbohydrates[J]. Carbohydrate Research, 1984, 131(2): 209-217.

Denovo Algorithm for Automated Glycan StructureAssignment by MS/MS

DONG Liang1, SHI Bing1, LI Yan-bo2, WANG Bing2

(1.DepartmentofComputerScienceandTechnology,ShandongUniversity,Ji’nan250101,China;2.InstituteofComputingTechnology,ChineseAcademyofScience,Beijing100190,China)

Determining denovo glycan structure automatically from MS/MS (including monosaccharide composition, sequencing topology and linkage between adjacent monosaccharide) has been studied for many years, but interpreting glycan structure from MS quickly and accurately is still a great challenge. Existing methods can be generally divided into two classes: greedy, heuristic to reduce time complexity, which are inexact by their nature; or exact methods such as dynamic programming or exhaustive method, which are slower than inexact methods and share common problems such as repetitive peak counting and crude scoring function in reconstructing candidate structure procedure. These unheeded details will lead to inaccuracy results. In this paper, a denovo algorithm we designed to accurately reconstruct the tree structure bottomed up from MS/MS with only some logical constrains, which can be applied to N-glycan or O-glycan equally. Different from previous iterative methods, the growing unit in this algorithm is not monosaccharide but substructure produced in the iterative procedure, thus improving the processing speed significantly. By taking unheeded details into consideration, experiments were conducted on 20 complex glycan structures extracted from human sperm, the results show that this algorithm has a high accuracy by ranking 15 real structure the first place.

MS/MS; glycan; structure assignment; denovo; dynamic programming

2014-05-16;

2014-09-03

董 梁(1991—)，男(漢族)，山東臨沂人，碩士研究生，生物信息學(xué)專業(yè)。E-mail: dl018@sina.com

時間：2015-01-30；

http:∥www.cnki.net/kcms/detail/11.2979.TH.20150130.1518.005.html

O657.63

A

1004-2997(2015)03-0206-11

10.7538/zpxb.youxian.2015.0004