[發(fā)明專利]基于專家知識(shí)與拓?fù)湎嗨频泥従觾?yōu)先生物分子子網(wǎng)搜索方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210358669.9
• 申請(qǐng)日: 2012-09-25
• 公開(kāi)（公告）號(hào): CN102902896A
• 公開(kāi)（公告）日: 2013-01-30
• 發(fā)明（設(shè)計(jì)）人: 謝江;譚軍;馬進(jìn);張武;文鐵橋
• 申請(qǐng)（專利權(quán)）人: 上海大學(xué)
• 主分類號(hào): G06F19/24
• 分類號(hào): G06F19/24
• 代理公司: 上海上大專利事務(wù)所(普通合伙) 31205
• 代理人: 何文欣

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)領(lǐng)域，提出了基于專家知識(shí)與拓?fù)湎嗨频泥従觾?yōu)先生物分子子網(wǎng)搜索方法。

背景技術(shù)

生物分子網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)。在復(fù)雜網(wǎng)絡(luò)中搜索與目標(biāo)子網(wǎng)最相似的子網(wǎng)是一個(gè)局部網(wǎng)絡(luò)比較問(wèn)題，涉及到大量的計(jì)算，已被證實(shí)是一個(gè)NP完全問(wèn)題（Non-deterministic?Polynomial的問(wèn)題，也即是多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題）。目前，研究人員普遍采用圖來(lái)表示復(fù)雜網(wǎng)絡(luò)，并以圖論的方法來(lái)研究它們。對(duì)于生物分子網(wǎng)絡(luò)而言，圖中的節(jié)點(diǎn)表示生物分子，邊表示生物分子之間的調(diào)控、相互作用等各種關(guān)系。

由于生物分子網(wǎng)絡(luò)特有的生物學(xué)意義，僅用圖論的方法來(lái)研究它們是不夠的，其搜索還面臨著更多的問(wèn)題，主要包括：（1）每個(gè)生物分子都有其生物學(xué)意義，要明確一個(gè)網(wǎng)絡(luò)中的某個(gè)生物分子和另外一個(gè)網(wǎng)絡(luò)中的哪個(gè)生物分子最相似，不僅要考慮生物分子本身的序列，還要考慮它在網(wǎng)絡(luò)中的拓?fù)湮恢茫唬?）無(wú)論是國(guó)際公開(kāi)的數(shù)據(jù)庫(kù)中的數(shù)據(jù)，還是自己通過(guò)生物實(shí)驗(yàn)獲得的數(shù)據(jù)都存在假陽(yáng)性和假陰性現(xiàn)象，目前只能通過(guò)這些不完全準(zhǔn)確和不完整的數(shù)據(jù)研究生物分子網(wǎng)絡(luò)；（3）對(duì)于要研究的不同的具體問(wèn)題，網(wǎng)絡(luò)中各個(gè)分子的地位并不是完全平等的，計(jì)算過(guò)程中要合理利用專家知識(shí)，以貼近生物學(xué)的實(shí)際應(yīng)用背景。

目前，已有一些研究小組在進(jìn)行這方面的研究，也開(kāi)發(fā)了少量的工具。這些方法各有其優(yōu)點(diǎn)，但也各有其局限性，無(wú)法滿足系統(tǒng)生物學(xué)的需要。而這些局限性主要體現(xiàn)在對(duì)具有相對(duì)復(fù)雜的拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)搜索上，對(duì)于生物分子網(wǎng)絡(luò)而言，為了能獲得不同物種間的最相似網(wǎng)絡(luò)，計(jì)算的準(zhǔn)確度必須得到提高。同時(shí)，考慮到生物分子網(wǎng)絡(luò)的進(jìn)化和變異，不同物種的網(wǎng)絡(luò)雖然不同，卻有一定的保守性，算法應(yīng)能在變異后的網(wǎng)絡(luò)中找到原始的保守信息，能較好地體現(xiàn)網(wǎng)絡(luò)拓?fù)涞淖兓闆r，且具有較高的穩(wěn)定性。

發(fā)明內(nèi)容

本發(fā)明的目的在于，為了解決上述問(wèn)題而提供基于專家知識(shí)與拓?fù)湎嗨频泥従觾?yōu)先生物分子子網(wǎng)搜索方法，該方法能在復(fù)雜的生物分子網(wǎng)絡(luò)中搜索到與目標(biāo)子網(wǎng)最相似的結(jié)果子網(wǎng)，避免了以往算法不能合理利用專家知識(shí)而帶來(lái)的計(jì)算的盲目性，并降低因原始信息缺失帶來(lái)的誤差，從而具有較高的穩(wěn)定性。隨著生物分子網(wǎng)絡(luò)的進(jìn)化和變異，該方法較少受到Gap的影響，從而可以搜索得到更多的保守邊和節(jié)點(diǎn)，而變異的邊數(shù)往往與未匹配邊數(shù)一致，即方法能較好地體現(xiàn)拓?fù)涞淖兓闆r。

為達(dá)到上述目的，本發(fā)明的構(gòu)思是：首先結(jié)合生物分子的序列特征及其在網(wǎng)絡(luò)中的拓?fù)湎嗨铺卣?，?jì)算各個(gè)生物分子之間的相似系數(shù)，其中拓?fù)湎嗨铺卣髦饕紤]目標(biāo)生物分子的鄰居/非鄰居分子之間的平均相似性，以降低原始信息缺失和不準(zhǔn)確帶來(lái)的誤差，并提高其穩(wěn)定性；然后根據(jù)具體問(wèn)題和專家知識(shí)字典，將目標(biāo)子網(wǎng)中的生物分子分類，確定K類分子的最相似分子；最后，根據(jù)生物分子之間的關(guān)系特點(diǎn)，如“與相似的蛋白質(zhì)發(fā)生相互作用的那些蛋白質(zhì)之間往往具有更高的相似度”，對(duì)N類分子采用鄰居優(yōu)先的策略進(jìn)行搜索，獲得結(jié)果子網(wǎng)。

根據(jù)上述發(fā)明構(gòu)思，對(duì)于網(wǎng)絡(luò)A（G_A）、網(wǎng)絡(luò)B（G_B）及網(wǎng)絡(luò)A中的目標(biāo)子網(wǎng)T（G_t），本發(fā)明采用下述技術(shù)方案：

A、?計(jì)算G_t和G_B的初始相似矩陣????????????????????????????????????????????????：根據(jù)生物分子的序列特征，構(gòu)建網(wǎng)絡(luò)T（G_t）和B（G_B）中生物分子的初始相似矩陣，其中的每個(gè)元素表示節(jié)點(diǎn)和節(jié)點(diǎn)之間的序列相似系數(shù)；

B、?計(jì)算G_t和G_b的相似矩陣S：根據(jù)生物分子在各自網(wǎng)絡(luò)中的拓?fù)湎嗨铺卣?，?jì)算生物分子的相似矩陣S，矩陣中的每個(gè)元素為節(jié)點(diǎn)和節(jié)點(diǎn)之間的相似系數(shù)；

C、??構(gòu)建專家知識(shí)字典：字典中包含了網(wǎng)絡(luò)T（G_t）和B（G_B）中由專家確定的最相似的生物分子對(duì)；

D、??采用鄰居節(jié)點(diǎn)優(yōu)先策略進(jìn)行網(wǎng)絡(luò)搜索：利用專家知識(shí)，基于相似矩陣S，以鄰居優(yōu)先策略進(jìn)行搜索，獲得結(jié)果子網(wǎng)；

E、??計(jì)算結(jié)果子網(wǎng)（G_r）與目標(biāo)子網(wǎng)（G_t）的相似得分；

F、??計(jì)算p值，分析目標(biāo)子網(wǎng)的統(tǒng)計(jì)學(xué)意義；

G、?結(jié)果子網(wǎng)（G_r）可視化。