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

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

?

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

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

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

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

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

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

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

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

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

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

1 實(shí)驗(yàn)方法

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

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

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

表1 單糖名稱和表示

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

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

表2 單糖支持的連接方式

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

1.2 算法流程

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

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

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

(1)

(2)

2 實(shí)驗(yàn)部分

2.1 主要儀器和試劑

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

2.2 樣品制備

實(shí)驗(yàn)中用到的聚糖提取自人體血清和牛胰腺，來(lái)自牛胰腺的聚糖樣本使用Saba等[17]給出的方法進(jìn)行處理。血清樣本按以下步驟處理：用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次。對(duì)凝膠進(jìn)行干燥處理，用加入50 μL濃度為0.1 u/mL PNGase F (Roche)[18]的碳酸氫鈉溶液(pH 7.2)浸泡凝膠5 min來(lái)分離聚糖和多肽。用200 μL蒸餾水反復(fù)清洗凝膠3次，再各用200 μL乙腈和蒸餾水進(jìn)行清洗1次，收集洗脫的N糖，進(jìn)行干燥處理，即得到粗多糖樣品。將多糖樣品溶于少量蒸餾水中，采用DEAE-52纖維素柱(1.6 cm×20.0 cm),依次用蒸餾水和0.1～2.0 mol/L碳酸氫鈉溶液進(jìn)行洗脫，采用苯酚-硫酸法檢測(cè)，收集相應(yīng)成分，透析脫鹽，濃縮后用 Sephadex G-100凝膠柱(1.6 cm×80.0 cm)進(jìn)一步分離純化，0.02 mol/L Tris-HCl(pH 7.2)溶液洗脫，收集洗脫液，冷凍干燥，備用。取部分實(shí)驗(yàn)聚糖樣本，用2AB聚糖標(biāo)記試劑盒進(jìn)行標(biāo)記，用乙腈洗去多余的2AB，氨水將標(biāo)記過(guò)的N糖洗脫，經(jīng)過(guò)干燥處理后，即可再次溶解于一定量的蒸餾水來(lái)進(jìn)行HPLC分析。使用帶2475熒光檢測(cè)器的Waters Alliance 2695高效液相色譜儀進(jìn)行分析，一系列外切糖苷酶，包括NANI唾液酸酶、ABS等協(xié)助分析，并與多糖數(shù)據(jù)庫(kù)GlycoBase進(jìn)行匹配以得到聚糖組分的單糖組成、連接信息和拓?fù)湫蛄行畔ⅰ?shí)驗(yàn)中使用的所有聚糖列于表3。

2.3 實(shí)驗(yàn)條件

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

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

表3 實(shí)驗(yàn)所用到的聚糖

續(xù)表3

3 結(jié)果與討論

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

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

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

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

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

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

4 結(jié)論

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

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

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

注：真實(shí)結(jié)構(gòu)排名越靠近1解析結(jié)果越準(zhǔn)確圖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算法 對(duì)20種聚糖解析實(shí)驗(yàn)的速度比較Table 5 Structure assignment speed comprison of BUP and StrOligo algorithm

聚糖編號(hào)BUP算法耗時(shí)/sStrOligo算法耗時(shí)/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

時(shí)間：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