基於距離判定的蛋白質複合物識別方法

2023-10-04 06:04:39 2

專利名稱：：基於距離判定的蛋白質複合物識別方法
技術領域：
：本發明屬於系統生物學領域，尤其涉及蛋白質複合物的識別。技術背景在後基因組時代，系統地分析和全面理解生物網絡拓撲及細胞內的生物化學進程成為一個非常重要的研究課題。細胞中的每個蛋白質並不是獨立完成被賦予的功能，而是通過與其它蛋白質相互作用形成大的複合物，在特定的時間和空間內完成特定的功能，而且有些蛋白質的功能只有在複合物形成後才能發揮出來。識別這些蛋白質複合物對預測蛋白質功能、解釋特定的生物進程具有重要作用。目前，用於識別蛋白質複合物的方法包括化學實驗測定方法、基於進化模型的物種比較方法、基於多信息集成的分析方法和基於蛋白質相互作用信息的聚類分析方法。化學實驗測定方法主要包括APMS(A伍nityPurificationtechniquesusingMassSpectrometry)、TAP(TandemAffinityPurification)、iTAP(TAP與RNAi)禾口HMS-PCI(High漏throughputMassSpectromicProteinComplexIdentification)等方法。通過化學實驗可以準確地測定某一環境下的蛋白質複合物，特別是那些比較穩定的複合物。但環境中仍存在一定數量的不穩定複合物，複合物內的蛋白質之間的相互作用是瞬時的，動態變化的，以實驗為基礎的研究方法很難捕捉到這些蛋白質複合物，而且實驗成本十分昂貴。基於進化模型的物種比較方法依據不同物種間的同源信息及進化過程中同一複合物內的蛋白質或集體保留或集體消失的機制，通過兩個或多個物種的比較分析識別那些在物種進化過程中保守的蛋白質複合物。這種基於進化模型的物種比較方法在一定程度上提高了識別的蛋白質複合物的可靠性，但該方法以蛋白質的同源信息為基礎，對兩個蛋白質的同源程度本身的把握就是一個難題，基於同源去識別蛋白質複合物就變得更加困難。基於多信息集成的分析方法則是依據已知資料庫中的蛋白質功能注釋、蛋白質結構、基因表達、亞細胞定位、蛋白質相互作用等信息在整個基因組規模上進行研究。ZoltdnDezso等人基於假定mRNA共表達的一組蛋白質可能調節相同功能的假說，通過分析mRNA共表達係數來識別蛋白質複合物。雖然基因表達和蛋白質相互作用之間的相互關係能夠揭示出這些數據內部之間的總體趨勢，但基因表達水平未必能夠真正代表蛋白質豐度，特別是高通量方法產生的蛋白質相互作用數據具有較高的假陽性，蛋白質相互作用信息和基因表達信息之間的關係非常複雜。目前，普遍的做法是基於蛋白質相互作用信息進行聚類分析，將蛋白質相互作用數據表示成一個無向圖，蛋白質複合物對應於其中的稠密子圖，應用各種聚類算法來識別這些稠密子圖(又稱為"簇/Cluster"，即蛋白質複合物)。已經提出的聚類方法主要有SPC方法、MCODE方法，RNSC方法、LCMA方法、DPClus方法、CFinder方法和STM方法等。SPC(SuperParamagneticClustering)是一種層次聚類法。SPC方法模擬鐵磁模型的物理特性，給每個蛋白質設定"spin"，每個spin可以存在多種狀態。對應連接的兩個頂點的spins之間互相影響，spins處於相同狀態時系統的能量最低。同一個高連通簇內的頂點對應的spins以關聯的方式進行浮動，可以通過識別關聯的spins來識別蛋白質複合物。根據Broh6e和Helden在BMCBioinformatics上給出的評估結果，SPC方法的敏感度和健壯性都較弱。MCODE(MolecularComplexDetection)是一種基於密度的局部搜索方法。MCODE方法首先根據每個頂點對應鄰居頂點的密度計算出所有頂點權重，並將權重最大的頂點作為種子，從種子頂點不斷地向外擴展，擴展的條件是被擴展的頂點權重大於給定閾值。但是，由於權重大的頂點彼此之間的連接並不一定稠密，MCODE方法並不能保證得到的簇是稠密的，對於那些稀疏的子圖還需要進一步處理。RNSC是一個基於成本的局部搜索方法。RNSC方法首先隨機地將蛋白質相互作用網絡分為若干個獨立簇，定義一個成本函數，然後不斷地將一個簇內蛋白質移至另一個簇來降低整體成本，直到這種移動次數超過事先設定的閾值而沒有使整體成本下降。RNSC方法的缺陷在於結果質量與方法開始生成簇的質量關係密切，此外每個蛋白質只屬於一個簇與蛋白質可能參與多個複合物的事實不符。LCMA是一個基於局部團合併的方法。LCMA方法首先將每個蛋白質頂點擴充成為一個團，再根據這些團之間的密切關係進行合併。DPClus和MCODE類似，也是一種基於密度的局部搜索方法。DPClus方法首先計算出可能的蛋白質複合物種子，然後從種子頂點開始不斷地向外擴展，被擴展的頂點需要滿足密度和簇性質的要求。CFinder是一種基於團滲透的方法，該方法將蛋白質複合物對應於圖中相互連通的若干k-團的集合。由於CFinder需要枚舉網絡中的所有極大團，所以對於規模比較大的網絡其效率成為難以克服的瓶頸。STM是一種流方法，首先計算出網絡中任意兩個頂點之間的最短路徑，並在此基礎上計算出任意兩個頂點之間的信號傳導關係，然後為每個頂點選擇一個簇表達，並在此基礎上進行初步聚類，最後對這些初步獲得的簇進行合併。在上述這些方法中，基於局部搜索和優化的聚類方法更適用於識別比較小的簇，而大多數蛋白質複合物都比較小，規模為5至25不等。基於局部搜索和優化的聚類方法的難點在於種子的選擇和擴充條件的制定，特別是擴充條件對產生蛋白質複合物的質量有很大的影響。
發明內容本發明基於對已知複合物內蛋白質之間的最短距離一般不超過2的發現，提出了一種基於距離判定的蛋白質複合物識別方法(IPCA)。該方法不需要其它任何輔助信息，只根據蛋白質相互作用數據就能夠較準確地識別大量具有生物意義的蛋白質複合物，解決了化學實驗方法很難識別動態蛋白質複合物的難題，而且節約了成本，並且一次可以預測出大量的蛋白質複合物。本發明的技術方案為建立蛋白質相互作用無向圖輸入一組蛋白質相互作用數據，設置允許的蛋白質頂點之間的最短距離的最大值A力，和一個大小在(o，i)之間的閾值r,",過濾重複的相互作用和自相互作用，建立無向計算頂點權重計算出網絡中每條邊的權重，邊權重定義為邊的兩個頂點的公共鄰居頂點個數；然後，將每個頂點連接的邊的權重求和，計算出網絡中所有頂點的權重，並根據權重對這些頂點按從大到小進行排序，放入一個候選種子隊列S,中；如果兩個頂點的權重相同，或頂點的權重為0,則根據頂點度對頂點進行排序；選擇種子若所述候選種子隊列&不為空，將隊列^的首個頂點，即權重最大的頂點作為種子，並初始化為一個簇，將該種子作為識別的蛋白質複合物的初始狀態進行擴充；每擴充完一個簇，隊列&中對應的該簇內的頂點被刪除；隊列&為空時，整個識別過程結束；擴充簇根據簇的所有鄰居頂點對簇進行擴充；所述簇的鄰居頂點指與簇內的頂點有直接相互作用且不在簇內的頂點；簇的每個鄰居頂點都擁有一個被擴充的優先權，由該頂點與簇內頂點連接的邊數以及邊的權重之和決定；首先考慮優先權最高的鄰居頂點作為候選的擴充頂點，候選的擴充頂點是否會被擴充需要調用擴充判斷子過程對其進行判斷，符合擴充條件的候選擴充頂點才能被加入簇；一旦有一個新的候選擴充頂點被加入簇，簇的鄰居頂點就進行更新，並重新計算其優先權；擴充判斷判斷一個候選的擴充頂點是否符合兩個條件1)SiYv，wj^A力,"ECV2)/iVv》7;，若符合就將其加入該簇，並調用擴充簇子過程對其作進一步的擴充；若不符合，且所有的鄰居頂點都己作過候選擴充頂點被考察過，則對該簇的擴充結束；若仍存在未被考察的鄰居頂點，則將下一個優先權最高的鄰居頂點作為候選擴充頂點；所述5P(v，w)表示蛋白質頂點v和蛋白質頂點"之間的最短距離，C表示蛋白質複合物內的蛋白質頂點集；4越大，識別的蛋白質複合物越稠密；所述/iV《是指某個蛋白質頂點v與蛋白質複合物之間的作用概率，定義為-formulaseeoriginaldocumentpage6式(1)中^d表示蛋白質複合物內部蛋白質頂點的數量，l&d表示蛋白質頂點V與蛋白質複合物之間作用邊的條數。本發明的方法對蛋白質相互作用大規模數據中普遍存在的比例較高的假陽性和假陰性具有很好的健壯性，能夠在蛋白質相互作用數據還不完善且具有較高噪聲的情況下有效地識別蛋白質複合物，為生物學家進行蛋白質複合物識別的實驗和進一步研究提供有價值的參考信息。圖l:兩個直徑小於等於2的拓撲結構圖；圖2:本發明IPCA的流程圖；圖3:不同匹配閾值下IPCA從酵母蛋白質相互作用網絡和隨機網絡中標識出已知複合物數量比較圖；圖4:IPCA的健壯性分析，其在隨機增加一定比例的邊後識別的蛋白質複合物與已知蛋白質複合物匹配結果比較圖(隨機增加邊的比例從10°/。到100%，按10個百分點間隔)；圖5:IPCA的健壯性分析，其在隨機刪除一定比例的邊後識別的蛋白質複合物與已知蛋白質複合物匹配結果比較圖(隨機刪除邊的比例從10%到90%，按10個百分點間隔)。具體實施方式一、統計分析己知蛋白質複合物的拓撲特徵目前研究最為廣泛的物種是酵母，而且已經具有一定數量的通過實驗手段測定的酵母蛋白質複合物。本發明從MIPS(MunichInformationcenterforProteinSequences)資料庫下載得到已知的酵母蛋白質複合物和酵母蛋白質相互作用網絡數據。將相互作用數據去除自相互作用和冗餘的相互作用，最終形成的蛋白質相互作用網絡包括4546個酵母蛋白質和12319對相互作用。整個網絡的平均聚集係數為0.4，網絡直徑為13，特徵路徑長度(即網絡內任意兩個頂點之間的最短路徑長度的平均值)為4.42。蛋白質複合物數據集去除只有一個蛋白質的複合物後共有216個，最小的複合物包括2個蛋白質，最大的複合物包括81個蛋白質，平均每個複合物包括6.31個蛋白質。216個複合物中共有118個是連通的，98個非連通，對連通的複合物和非連通的複合物內的連通部分分析其直徑和蛋白質間的平均最短路徑長度的結果如表1所示。表1酵母蛋白質相互作用網絡中複合物的直徑和複合物內蛋白質間的平均最短路徑長度tableseeoriginaldocumentpage7從表1可以看出，連通的複合物的直徑和非連通複合物的連通部分的直徑都遠小於其所在的網絡的直徑。在118個連通的複合物中直徑小於等於2的佔94.91%，蛋白質間的平均最短路徑長度小於等於2的佔99.15%。98個非連通的複合物的連通部分直徑小於等於2的佔82.66%，平均最短路徑長度全部小於2.5，其中小於等於2的佔93.88%。分析的結果表明複合物中的蛋白質頂點之間的距離具有顯著的統計特性，他們之間的距離一般不超過2。所以，本發明認為距離可以作為蛋白質複合物識別過程中一個非常重要的參數。二、識別蛋白質複合物的種子-擴充模型(IPCA)由於具有相同直徑或平均最短路徑長度的圖的稠密程度可能相差比較大。如圖1所示的兩個直徑小於等於2的圖的拓撲結構就相差甚遠。所以，本發明以作用概率/A/vc來進一步控制識別的蛋白質複合物的稠密程度。在擴充過程中，某個蛋白質頂點v與蛋白質複合物(Cluster)之間的作用概率/A^定義為其中，|&|表示蛋白質複合物內部蛋白質頂點的數量，l&d表示蛋白質頂點v與蛋白質複合物之間作用邊的條數。用於識別蛋白質複合物的種子擴充模型定義如下給定一個蛋白質頂點V與一個蛋白質複合物，蛋白質頂點V若屬於該蛋白質複合物則必須滿足如下兩個條件A"，WGC;2)/M^r,"。其中，S屍(V，")表示蛋白質頂點V和蛋白質頂點W之間的最短距離，C表示蛋白質複合物內的蛋白質頂點集，A。為允許的蛋白質頂點之間的最短距離的最大值，7^是給定的一個大小在(0,1)之間的閾值，7;越大，識別的蛋白質複合物越稠密。基於距離判定的蛋白質複合物識別方法IPCA的整個流程如圖2所示。先輸入一組蛋白質相互作用數據。用戶可以自己設置輸入參數A"和4的值。基於本發明對己知蛋白質複合物拓撲的統計分析，本發明將參數An的默認值設置為2。方法IPCA可以劃分為4個子過程計算頂點權重、選擇種子、擴充簇和擴充判斷。子過程l:計算頂點權重。方法IPCA首先計算出網絡中每條邊的權重，邊權重定義為邊的兩個頂點的公共鄰居頂點個數。然後，將每個頂點連接的邊的權重求和，計算出網絡中所有頂點的權重，並根據權重對這些頂點進行排序，放入一個候選種子隊列&中。如果兩個頂點的權重相同，或頂點的權重為O，則根據頂點度對頂點進行排序。計算出所有邊的權重的時間複雜度為o(iw問)，計算出所有頂點的權重，並將其按權重大小放入候選種子隊列&的時間複雜度為0(|W/ogW)。子過程2:選擇種子。若候選種子隊列&不為空，將隊列&的首個頂點，即權重最大的頂點，作為種子，並將該種子作為識別的蛋白質複合物(稱為"簇")的初始狀態進行擴充。候選種子隊列^的初始狀態為按權重從大到小排列的整個網絡圖中的所有頂點，每擴充完一個簇，隊列^中對應的該簇內的頂點被刪除。隊列&為空時，整個識別過程結束。子過程3:擴充簇。對簇進行擴充需要考慮簇的所有鄰居頂點。簇的鄰居頂點是指那些與簇內的頂點有直接相互作用且不在簇內的頂點。簇的每個鄰居頂點都擁有一個被擴充的優先權，由該頂點與簇內頂點連接的邊數以及這些邊的權重之和決定，連接的邊數越多，權重和越大，優先權越高。進行簇擴充時，首先考慮優先權最高的鄰居頂點作為候選的擴充頂點。候選的擴充頂點是否會被擴充需要調用擴充判斷子過程對其進行判斷，符合擴充條件的候選擴充頂點才能被加入簇。一旦有一個新的候選擴充頂點被加入簇，簇的鄰居頂點就進行更新，並重新計算其優先權。從簇的鄰居頂點產生候選擴充頂點的時間複雜度為0(|^||K—wl+IK—wllog|rLwll)，其中l^為簇內的頂點個數，IKjvl為簇的鄰居頂點個數。實際上，當一個新的候選頂點被加入簇後，簇的鄰居頂點及其優先權只需根據該頂點被加入簇引起的變化進行更新。簇的鄰居頂點更新的次數取決於該簇擴充終止時的規模。子過程4:擴充判斷。一個候選的擴充頂點是否被擴充需要判斷其是否符合種子-擴充模型中的兩個判斷條件，若符合就將其加入該簇，並調用擴充簇子過程對其作進一步的擴充；若不符合，且所有的鄰居頂點都已作過候選擴充頂點被考察過，則對該簇的擴充結束，若仍存在未被考察的鄰居頂點，則將下一個優先權最高的鄰居頂點作為候選擴充頂點。判斷一個候選擴充頂點是否滿足被擴充條件的時間複雜度為0(|^|2)。為了驗證方法IPCA的有效性，我們將方法IPCA應用於MIPS資料庫中的酵母蛋白質相互作用網絡和計算機生成的與該酵母網絡具有相同度分布的隨機網絡。首先，我們將參數A"設置為2，參數r,"設置從O.l到0.9，按0.1的間隔遞增，將方法IPCA分別應用於酵母蛋白質相互作用網絡和隨機網絡，並將識別的複合物與已知資料庫中通過實驗獲得的標準數據進行比較分析。識別出來的複合物(Pc)與已知複合物(i^)的匹配程度OS(Pc,Kc)的計算如下141X1^1(2)其中l&l和Fd分別表示識別複合物和己知複合物的規模，z'表示他們交集的規模。若兩個複合物的匹配程度OS(PC。超過給定的閾值，則稱這兩個複合物匹配。對於標準複合物數據集中的已知複合物，如果存在一個或多個算法識別出來的複合物與之匹配程度OS(戶c人c)超過給定閾值，則稱該已知複合物被標識，如果OS(屍c,尺c"l，則稱該已知複合物被完全標識。表2給出了不同匹配閾值下已知複合物被方法IPCA和其他方法標識出來的數量。表2不同匹配閾值下已知複合物被方法IPCA和其他方法標識出來的數量tableseeoriginaldocumentpage10從表2可以看出，在不同匹配閾值下，方法IPCA標識出來的己知複合物的數量都高於方法DPClus、CFinder、LCMA、MCODE、RNSC和STM標識出來的已知複合物的數量。圖3描述了不同匹配閾值下方法IPCA從酵母蛋白質相互作用網絡和對應的隨機網絡中標識出來的已知複合物數量。從圖3可以看出，方法IPCA在酵母網絡中標識出大量的已知複合物，但在隨機網絡中幾乎沒有已知複合物被標識出。這說明，方法IPCA識別的蛋白質複合物具有很強的生物意義。由於目前所能獲得的蛋白質相互作用數據都不可避免地具有較高的假陽性和假陰性，好的蛋白質複合物識別方法應該具有很好的健壯性。我們用隨機增加和刪除一定比例的邊來模擬蛋白質相互作用網絡的假陽性和假陰性。隨機增加邊的比例從10%到100%,按10個百分點間隔，產生了10組數據，從這些高假陽性的數據中進行蛋白質複合物識別，並將識別出來的結果與已知蛋白質複合物進行匹配，匹配的結果如圖4所示。從圖4可以看出，隨著假陽性的增強，方法IPCA能夠標識出來的已知蛋白質複合物數量幾乎沒有下降多少，說明其具有相當高的抗噪能力。隨機刪除邊的比例從10%到90%，也按10個百分點間隔，重複上面的工作，匹配結果如圖5所示。從圖5可以看出，只要刪除邊的比例小於50%，方法IPCA能夠標識出來的己知蛋白質複合物數量下降的很少。當刪除邊的比例大於50%時，標識出的數量開始下降。當刪除邊的比例大於80%時，標識出的數量有了十分明顯的下降。隨機增加和刪除一定比例邊的模擬實驗充分說明了方法IPCA對蛋白質相互作用網絡的假陽性和假陰性都具有相當高的健壯性。權利要求1.一種基於距離判定的蛋白質複合物識別方法，其特徵在於包括以下步驟(1)建立蛋白質相互作用無向圖輸入一組蛋白質相互作用數據，設置允許的蛋白質頂點之間的最短距離的最大值Din，和一個大小在(0，1)之間的閾值Tin，過濾重複的相互作用和自相互作用，建立無向圖；(2)計算出網絡中每條邊的權重，邊權重定義為邊的兩個頂點的公共鄰居頂點個數。然後，將每個頂點連接的邊的權重求和，計算出網絡中所有頂點的權重，並根據權重對這些頂點按從大到小進行排序，放入一個候選種子隊列Sq中；如果兩個頂點的權重相同，或頂點的權重為0，則根據頂點度對頂點進行排序；(3)選擇種子若所述候選種子隊列Sq不為空，將隊列Sq的首個頂點，即權重最大的頂點作為種子，並初始化為一個簇，將該種子作為識別的蛋白質複合物的初始狀態進行擴充；每擴充完一個簇，隊列Sq中對應的該簇內的頂點被刪除；隊列Sq為空時，整個識別過程結束；(4)擴充簇的過程為根據簇的所有鄰居頂點對簇進行擴充；所述簇的鄰居頂點指與簇內的頂點有直接相互作用且不在簇內的頂點；簇的每個鄰居頂點都擁有一個被擴充的優先權，由該頂點與簇內頂點連接的邊數以及邊的權重之和決定；首先考慮優先權最高的鄰居頂點作為候選的擴充頂點，候選的擴充頂點是否會被擴充需要調用擴充判斷子過程對其進行判斷，符合擴充條件的候選擴充頂點才能被加入簇；一旦有一個新的候選擴充頂點被加入簇，簇的鄰居頂點就進行更新，並重新計算其優先權；(5)所述擴充判斷的過程為判斷一個候選的擴充頂點是否符合兩個條件1)SP(v，u)≤Din，u∈C；2)INvC≥Tin，若符合就將其加入該簇，並調用擴充簇子過程對其作進一步的擴充；若不符合，且所有的鄰居頂點都已作過候選擴充頂點被考察過，則對該簇的擴充結束；若仍存在未被考察的鄰居頂點，則將下一個優先權最高的鄰居頂點作為候選擴充頂點；所述SP(v，u)表示蛋白質頂點v和蛋白質頂點u之間的最短距離，C表示蛋白質複合物內的蛋白質頂點集；Tin越大，識別的蛋白質複合物越稠密；所述INvC是指某個蛋白質頂點v與蛋白質複合物之間的作用概率。全文摘要本發明公開了一種基於距離判定的蛋白質複合物識別方法，基於對已知蛋白質複合物中蛋白質頂點之間的最短距離一般不超過2的發現，將蛋白質頂點之間的最短距離作為蛋白質複合物識別的一個重要參數，並利用蛋白質頂點與蛋白質複合物之間的作用概率來控制識別的蛋白質複合物的稠密程度。本發明實現簡單，能夠通過蛋白質相互作用網絡識別大量已知的具有生物意義的蛋白質複合物，對蛋白質相互作用大規模數據中普遍存在的比例較高的假陽性和假陰性具有很好的健壯性，有效地解決了化學實驗成本昂貴，單次識別數量少以及很難識別動態複合物的生物學難題。文檔編號G06F19/00GK101246520SQ20081003083公開日2008年8月20日申請日期2008年3月18日優先權日2008年3月18日發明者敏李,王建新申請人:中南大學