[發(fā)明專利]基于距離判定的蛋白質(zhì)復(fù)合物識(shí)別方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 200810030832.2
• 申請(qǐng)日: 2008-03-18
• 公開(kāi)（公告）號(hào): CN101246520A
• 公開(kāi)（公告）日: 2008-08-20
• 發(fā)明（設(shè)計(jì)）人: 王建新;李敏
• 申請(qǐng)（專利權(quán)）人: 中南大學(xué)
• 主分類號(hào): G06F19/00
• 分類號(hào): G06F19/00
• 代理公司: 中南大學(xué)專利中心
• 代理人: 龔燦凡

1.一種基于距離判定的蛋白質(zhì)復(fù)合物識(shí)別方法，其特征在于包括以下步驟：

(1)建立蛋白質(zhì)相互作用無(wú)向圖：輸入一組蛋白質(zhì)相互作用數(shù)據(jù)，設(shè)置允許的蛋白質(zhì)頂點(diǎn)之間的最短距離的最大值D_in為2，和一個(gè)大小在(0，1)之間的閾值T_in，過(guò)濾重復(fù)的相互作用和自相互作用，建立無(wú)向圖；

(2)計(jì)算頂點(diǎn)權(quán)重，對(duì)頂點(diǎn)進(jìn)行排序：將無(wú)向圖中邊權(quán)重定義為邊的兩個(gè)頂點(diǎn)的公共鄰居頂點(diǎn)個(gè)數(shù)，頂點(diǎn)權(quán)重定義為其連接的邊的權(quán)重之和；計(jì)算圖中所有頂點(diǎn)的權(quán)重，并根據(jù)權(quán)重對(duì)這些頂點(diǎn)按從大到小進(jìn)行排序，放入一個(gè)候選種子隊(duì)列S_q中；如果兩個(gè)頂點(diǎn)的權(quán)重相同，或頂點(diǎn)的權(quán)重為0，則根據(jù)頂點(diǎn)度對(duì)頂點(diǎn)進(jìn)行排序；

(3)生成簇并輸出，輸出的每個(gè)簇即為一個(gè)蛋白質(zhì)復(fù)合物，具體過(guò)程為：

選擇種子：若所述候選種子隊(duì)列S_q不為空，將隊(duì)列S_q的首個(gè)頂點(diǎn)，即權(quán)重最大的頂點(diǎn)作為種子，并初始化為一個(gè)簇，將該種子作為識(shí)別的蛋白質(zhì)復(fù)合物的初始狀態(tài)進(jìn)行擴(kuò)充；

擴(kuò)充過(guò)程為：根據(jù)簇的所有鄰居頂點(diǎn)對(duì)簇進(jìn)行擴(kuò)充；所述簇的鄰居頂點(diǎn)指與簇內(nèi)的頂點(diǎn)有直接相互作用且不在簇內(nèi)的頂點(diǎn)；簇的每個(gè)鄰居頂點(diǎn)都擁有一個(gè)被擴(kuò)充的優(yōu)先權(quán)，由該鄰居頂點(diǎn)與簇內(nèi)頂點(diǎn)連接的邊數(shù)以及邊的權(quán)重之和決定；首先考慮優(yōu)先權(quán)最高的鄰居頂點(diǎn)作為候選的擴(kuò)充頂點(diǎn)，候選的擴(kuò)充頂點(diǎn)是否會(huì)被擴(kuò)充需要調(diào)用擴(kuò)充判斷子過(guò)程對(duì)其進(jìn)行判斷，符合擴(kuò)充條件的候選擴(kuò)充頂點(diǎn)才能被加入簇；一旦有一個(gè)新的候選擴(kuò)充頂點(diǎn)被加入簇，簇的鄰居頂點(diǎn)就進(jìn)行更新，并重新計(jì)算其優(yōu)先權(quán)；

所述擴(kuò)充判斷子過(guò)程為：判斷一個(gè)候選的擴(kuò)充頂點(diǎn)是否符合兩個(gè)條件：

1)SP(v，u)≤D_in，u∈C；2)IN_vC≥T_in，若符合就將其加入該簇，并調(diào)用所述擴(kuò)充過(guò)程對(duì)該簇作進(jìn)一步的擴(kuò)充；若不符合，且所有的鄰居頂點(diǎn)都已作過(guò)候選擴(kuò)充頂點(diǎn)被考察過(guò)，則對(duì)該簇的擴(kuò)充結(jié)束；若仍存在未被考察的鄰居頂點(diǎn)，則將下一個(gè)優(yōu)先權(quán)最高的鄰居頂點(diǎn)作為候選擴(kuò)充頂點(diǎn)；所述SP(v，u)表示蛋白質(zhì)頂點(diǎn)v和蛋白質(zhì)頂點(diǎn)u之間的最短距離，C表示蛋白質(zhì)復(fù)合物內(nèi)的蛋白質(zhì)頂點(diǎn)集；T_in越大，識(shí)別的蛋白質(zhì)復(fù)合物越稠密；所述IN_vC是指某個(gè)蛋白質(zhì)頂點(diǎn)v與蛋白質(zhì)復(fù)合物之間的作用概率，定義為：

INvC=|EvC||VC|,]]>

式中|V_C|表示蛋白質(zhì)復(fù)合物內(nèi)部蛋白質(zhì)頂點(diǎn)的數(shù)量，|E_vC|表示蛋白質(zhì)頂點(diǎn)v與蛋白質(zhì)復(fù)合物之間作用邊的條數(shù)；

每擴(kuò)充完一個(gè)簇，將該簇作為一個(gè)蛋白質(zhì)復(fù)合物輸出，并將該簇內(nèi)的頂點(diǎn)從隊(duì)列S_q中刪除，返回執(zhí)行選擇種子的步驟；隊(duì)列S_q為空時(shí)，整個(gè)識(shí)別過(guò)程結(jié)束。