[發(fā)明專利]一種面向基因調控網絡的可達概率查詢方法

有效

• 申請?zhí)枺?/td>: 202010500098.2
• 申請日: 2020-06-04
• 公開（公告）號: CN111462824B
• 公開（公告）日: 2023-08-08
• 發(fā)明（設計）人: 王之瓊;丁子恒;張釗源;劉可伊;汪翰文;王煒祎祺
• 申請（專利權）人: 東北大學
• 主分類號: G16B50/00
• 分類號: G16B50/00;G16B20/00;G16B5/20;G16B40/00;G06N7/01
• 代理公司: 沈陽東大知識產權代理有限公司 21109
• 代理人: 李在川

1.一種面向基因調控網絡的可達概率查詢方法，其特征在于，包括如下步驟：

步驟1：利用貝葉斯網絡構建基因間的調控網絡，得到一個有向無環(huán)不確定圖，其中頂點表示基因，邊表示兩個基因之間的相互作用，邊權值表示基因之間存在相互作用的可能性；

步驟2：對不確定圖進行縮減；

步驟3：生成可能世界圖與圖搜索并行的可達查詢；

所述步驟2包含3個縮減過程，分別為：

圖縮減過程1：去除所有出度為0的非目標、非源節(jié)點；

圖縮減過程2：去掉所有入度為0的非目標、非源節(jié)點；

圖縮減過程3：去掉所有出入度均為1的非目標、非源節(jié)點；

所述3個縮減過程合并使用或者分別獨立使用；

所述圖縮減過程1的步驟如下：

S1.1：遍歷不確定圖，找到所有出度為0的非目標、非源節(jié)點；

S1.2：將這些節(jié)點及其鄰邊從不確定圖中刪除；

S1.3：若由于S1.2中的刪除操作，使得有其他節(jié)點的出度變?yōu)?，則繼續(xù)將這些節(jié)點按照S1.2處理；

S1.4：重復S1.2和S1.3，直至沒有出度為0的非目標、非源節(jié)點；

所述圖縮減過程2的步驟如下：

S2.1：遍歷不確定圖，找到所有入度為0的非目標、非源節(jié)點；

S2.2：將這些節(jié)點及其鄰邊從不確定圖中刪除；

S2.3：若由于S2.2中的刪除操作，使得有其他節(jié)點的入度變?yōu)?，則繼續(xù)將這些節(jié)點按照步S2.2處理；

S2.4：重復S2.2和S2.3，直至沒有入度為0的非目標、非源節(jié)點；

所述圖縮減過程3的步驟如下：

S3.1：遍歷不確定圖，找到所有出入度均為1的非目標、非源節(jié)點；

S3.2：將這些節(jié)點及其鄰邊從不確定圖中刪除，建立新邊或與已有邊進行合并，代替這些節(jié)點及其鄰邊；

S3.3：計算并更新上述新邊或已有邊的存在概率；

S3.4：若由于S3.2中的刪除操作，使得有其他節(jié)點的出入度均變?yōu)?，則繼續(xù)將這些節(jié)點按照S3.2和S3.3處理；

S3.5:重復S3.2至S3.4，直至沒有出入度均為1的非目標、非源節(jié)點；

所述步驟3的過程如下：

步驟3.1：輸入縮減后的圖，設定抽樣次數(shù)為N，記搜索成功次數(shù)為M，M初始化為0；

步驟3.2：從源點出發(fā)開始搜索，采取廣度或深度優(yōu)先遍歷，遍歷節(jié)點與它的鄰接點之間的邊，生成0-1之間的隨機數(shù)；

步驟3.3：比較隨機數(shù)與邊的存在概率，若存在概率大于隨機數(shù)則邊存在，將存在邊的相關節(jié)點納入廣度或深度優(yōu)先遍歷的待搜索節(jié)點集中；若存在概率小于隨機數(shù)則認為邊不存在，忽略該邊以及該邊的相關節(jié)點；

步驟3.4：重復步驟3.1和步驟3.3，若目標節(jié)點被納入待搜索節(jié)點集，則記為搜索成功一次，M＝M+1，該步驟結束；若尚未搜索到目標節(jié)點且待搜索節(jié)點集為空，則認為搜索失敗，該步驟結束；

步驟3.5：重復步驟3.1至步驟3.4N次，計算查詢結果為可達概率