基于本體的疾病關聯(lián)搜索方法的研究

梅 祎， 王亞東

(哈爾濱工業(yè)大學 計算機科學與技術學院， 哈爾濱 150001)

0 引 言

近年來，隨著醫(yī)療技術和生物科技的迅猛發(fā)展，生物領域的大數(shù)據(jù)急劇增加。其中，疾病本體和其它相關的數(shù)據(jù)如藥物、基因及相關文獻等是生物大數(shù)據(jù)中不可或缺的典型組成部分。隨著數(shù)據(jù)量規(guī)模的日趨龐大，數(shù)據(jù)的快速、有效檢索成為了至關重要的研究問題。

然而，主流的綜合搜索引擎如百度、Google等對疾病關鍵詞的檢索結果普遍來說都比較簡單通俗，偏向科普的形式，適用于并不具備專業(yè)知識的普通用戶，因而不能滿足更高層面的研究需求，尤其是對專業(yè)的醫(yī)療工作者和研究者來說，搜索結果也尚未臻至專業(yè)和全面。

面向疾病領域的垂直搜索引擎不僅數(shù)目稀少，而且功能單一。例如，疾病瀏覽器Disease Ontology(http://disease-ontology.org)，雖然搜索結果是有效的，但搜索結果未能按照相關性的大小給出有序展示，且包含的知識不夠豐富，對用戶來說，從其中提取自身想要的信息還需做進一步的篩選，是一個耗費時間和精力的過程。

基于此，本文提出了基于疾病本體的關聯(lián)搜索，關聯(lián)檢索算法綜合考慮了疾病本體及其相關數(shù)據(jù)之間的關聯(lián)，為用戶提供有效的檢索信息，結果表明，關聯(lián)搜索算法的搜索結果相關度高、內容豐富，此外，用戶還可以根據(jù)個人的偏好，或者行為習慣，通過調整參數(shù)，修改搜索結果出現(xiàn)的先后順序。

1 相關工作

搜索引擎主要分為2種：綜合搜索引擎和面向專業(yè)領域的垂直搜索引擎[1-2]。 對此可闡釋解析如下。

(1)綜合搜索引擎[3]?，F(xiàn)在已經得到了廣泛的研究。其中，Google公司提出的PageRank算法[4]，即是依靠網(wǎng)頁之間的鏈接關系來確定每一個頁面的等級,一個頁面到另一個頁面的鏈接可解釋成該頁面對另一頁面的投票，PageRank算法根據(jù)這些投票來源和投票目的的等級確定新的等級。PageRank算法在普通的網(wǎng)頁搜索中表現(xiàn)得較好，但是涉及到專業(yè)領域的搜索時，往往沒有很好的結果。除了PageRank之外，HITS也是常用的鏈接分析技術[5]，是用于分析網(wǎng)頁重要性的設計算法，可根據(jù)一個網(wǎng)頁的入度(指向此網(wǎng)頁的超鏈接)和出度(從此網(wǎng)頁指向別的網(wǎng)頁)來衡量網(wǎng)頁的重要性。其最直觀的意義就是如果一個網(wǎng)頁的重要性很高，則由其所指向的網(wǎng)頁的重要性也會較高。一個重要的網(wǎng)頁被另一個網(wǎng)頁所指，則表明指向該網(wǎng)頁的重要性也會很高。指向別的網(wǎng)頁定義為Hub值，被指向定義為Authority值。

(2)垂直搜索引擎。即專業(yè)或專用搜索引擎，就是專為查詢某一學科或主題的信息而產生的查詢工具，專門收錄一方面、某一行業(yè)或某一主題的信息，與搜索引擎門戶相比，對解決實際查詢問題要更加有效[6]。

2 方法

2.1 問題描述

在由不同類型的數(shù)據(jù)構成的數(shù)據(jù)集合中，數(shù)據(jù)之間存在著各種相關關系，比如疾病本體之間的父子及兄弟關系，疾病與藥物、基因等數(shù)據(jù)之間的關聯(lián)關系等。因此，這些數(shù)據(jù)組成了一個復雜的異構網(wǎng)絡，每一個數(shù)據(jù)條目都可以對應成網(wǎng)絡中的一個節(jié)點，數(shù)據(jù)間的關系對應節(jié)點間的邊。

本課題所需要實現(xiàn)的目標是在這個復雜的異構網(wǎng)絡中，搜索出與待搜索關鍵詞相關度最高的前n個節(jié)點。

2.2 知識庫建立

本課題首先建立起了疾病本體及其相關數(shù)據(jù)包括基因、表型、藥物、文獻等數(shù)據(jù)之間的異構網(wǎng)絡，研究使用的數(shù)據(jù)主要來自于選取醫(yī)學數(shù)據(jù)庫，該部分研究內容可探討分述如下。

(1)Disease ontology[7]。疾病本體來自于開放生物醫(yī)學體系(Open Biomedical Ontology，OBO)，是紀錄了與人類相關疾病數(shù)據(jù)的本體庫。

(2)MeSH(Medical Subject Headings)[8]。是美國國家醫(yī)學圖書館創(chuàng)建的醫(yī)學主題詞表，由于其結構體系完整合理，在世界范圍內被廣泛使用。

(3)KEGG[9](Kyoto Encyclopedia of Genes and Genomes)數(shù)據(jù)庫。是從分子水平，整合了基因、酶、化合物及代謝網(wǎng)絡信息的綜合性數(shù)據(jù)庫。

(4)OMIM[10](Online Mendelian Inheritance in Man)數(shù)據(jù)庫。是在線孟德爾人類遺傳數(shù)據(jù)庫，主要包括了遺傳疾病、遺傳表型及基因等信息。

(5)MEDIC(合成疾病詞匯，merged disease vocabulary)[11]。是整合OMIM術語、同義詞和標識符與MeSH術語、同義詞、標識符、定義和層級關系的資源，通過MEDIC，就在原有基礎上補充及豐富了數(shù)據(jù)間的關聯(lián)關系。

2.3 方法設計

知識庫網(wǎng)絡可以表示為圖G=(V,E),其中V為節(jié)點集合，E為邊的集合，任意的2個節(jié)點之間用一條邊連接，邊的權值代表相似性或相關性，其取值范圍為[0,1]。權值矩陣為M，對任意的節(jié)點v1,v2，稱M(v1,v2)為節(jié)點v1和節(jié)點v2之間的固有相關度。

衰減系數(shù)用來表示從某一類型節(jié)點到另一類型節(jié)點之間相關性的衰減。設節(jié)點類型數(shù)量為N，則衰減系數(shù)可以表示為N×N的矩陣R。對?v∈V，函數(shù)t(v)表示節(jié)點v的節(jié)點類型。對任意的節(jié)點v1,v2,R(t(v1),t(v2))表示節(jié)點v1和v2的衰減系數(shù)。

綜合考慮節(jié)點間的相關性和節(jié)點類型間的衰減系數(shù)，得到一個大小為|V|×|V|的綜合相關度矩陣S。計算方法為：

Si, j=Mi, j×Rt(i), t(j),i∈[1, |V|],j∈[1, |V|].

(1)

對于待查詢的關鍵字k，可以將其視為一個特殊的節(jié)點，加入至上述網(wǎng)絡。其與每個節(jié)點之間有一個直接的相似度，由指定的打分函數(shù)進行定義。將網(wǎng)絡由此擴展后，新的網(wǎng)絡可表示為一個(|V|+1)×(|V|+1)的矩陣W。

查詢算法的目的是找到網(wǎng)絡中與待查詢關鍵字k相關性最高的n個節(jié)點，而該相關性不僅由該節(jié)點與待查詢關鍵字節(jié)點之間的直接相關性決定，亦是由該節(jié)點周圍的節(jié)點決定。下面，研究給出了查詢問題的形式化定義。

定義1設vi,vi+1, …,vi+n為vi到vi+n之間的一條哈密頓通路，將W(vi,vi+1)×W(vi+1,vi+2)×…×W(vi+n-1,vi+n)稱為節(jié)點vi和vi+n之間關于該條哈密頓通路的相關度。若該條通路記為p，將該路徑相關度則記為Yp。

定義2設函數(shù)g(vi,vj)表示節(jié)點vi和節(jié)點vj之間的全部哈密頓通路。節(jié)點vi和節(jié)點vj之間相關度可以定義為節(jié)點vi和節(jié)點vj之間的全部哈密頓通路的相關度的最大值，設節(jié)點間的相關度為f(vi,vj)，則f(vi,vj)=max{Yp},p∈g(vi,vj)。當vi為待搜索的關鍵詞節(jié)點k時，記f(k,vj)為f(vj)。

因此，問題可以被表述為輸入待查詢關鍵詞k和查詢數(shù)目n，輸出集合Q，滿足Q?V, |Q|=n, 且?v′∈V-Q,v∈Q,f(k,v′)>f(k,v)(即輸出分數(shù)前n的節(jié)點數(shù)組)。

在此基礎上，研發(fā)得到了關聯(lián)搜索算法的流程步驟可表述如下。

輸入：查詢的關鍵詞k，查詢數(shù)目n

輸出：集合Q，滿足Q?V, |Q|=n, 且?v′∈V-Q,v∈Q,f(k,v′)>f(k,v)(即輸出分數(shù)前n的節(jié)點數(shù)組)。

A←[]

B←[]

ForvinV:

v.score←W(k,v)

B.add(v)

B.sort

Forifrom 1 ton:

v←B.first

A.add(v)

B.remove(v)

forv' inB:

v'.score=max{v'.score,v.score*W(v,v')}

B.sort

returnA

2.4 算法正確性證明

考慮如下的命題：每次循環(huán)執(zhí)行前，B數(shù)組的第一個節(jié)點v1滿足f(v1)=v1.score，且不存在B數(shù)組中的其它節(jié)點vi，會使f(vi)>v1.score。下面,關于該命題的正確性證明過程詳見如下。

經過研究可知，循環(huán)第一次執(zhí)行前，顯然，vi.score=W(k,vi),而B數(shù)組中元素已經經過排序，因此W(k,vi)

由于該命題成立，使得算法每次從B數(shù)組中移除第一個節(jié)點，將其添加到A數(shù)組中，而當循環(huán)執(zhí)行n次結束后，A數(shù)組中的節(jié)點是全部節(jié)點中分數(shù)從大到小排列的前n個元素。因此推得，算法是正確的。

2.5 算法復雜度分析

(1)算法的時間復雜度為：n×|V|×log(|V|)。

(2)算法的空間復雜度為：|V|2。

3 結果分析

以搜索“brain cancer”為例，可得搜索結果如圖1所示。

圖1 “brain cancer”的搜索結果圖

從圖1中可以看出，首先搜索得到與搜索關鍵詞直接相關的疾病本體“DOID:1319”和“DOID:4203”。然后搜索出了其它關聯(lián)的疾病本體，如“DOID:3620”，從路徑中可以看出其是與疾病本體“DOID:1319”相關的，這2個疾病本體在疾病本體樹中的結構如圖2所示，分析得知“DOID:1319”是疾病本體“DOID:3620”的子節(jié)點。圖3是計算后的疾病本體間相似度，由此推得，這2個疾病本體具有較高的相關度。

接下來，若以“0050120”作為搜索關鍵詞，搜索的結果則如圖4所示。從圖4中可以看出，不僅搜索出了直接與關鍵詞匹配的疾病本體“DOID：0050120”，還檢索出了該疾病本體相關的基因及表型等。此外，研究中又發(fā)現(xiàn)，通過疾病本體“DOID:0050120”關聯(lián)到了的基因“5515”再關聯(lián)到疾病本體“DOID:0060060”，體現(xiàn)了這2個疾病本體關聯(lián)著共同的基因，兩者之間也存在著某種關聯(lián)關系。

圖2 疾病本體“DOID:1319”與疾病本體“DOID:3620”在樹中的位置圖

Fig. 2 The “DOID:1319” and “DOID:3620” in the tree of disease ontology

圖3 疾病本體“DOID:1319”與其它疾病本體的相似度信息圖

Fig. 3 The similarity of“DOID:1319” with other disease ontologies

圖4 “0050120”的搜索結果圖

4 結束語

本文針對疾病本體及其相關數(shù)據(jù)的檢索問題，提出了基于疾病本體的關聯(lián)搜索算法。首先，根據(jù)多種醫(yī)療數(shù)據(jù)庫中的原始數(shù)據(jù)，構建異構知識網(wǎng)絡，之后，設計了在知識網(wǎng)絡中進行關聯(lián)搜索的算法，算法可對節(jié)點與關鍵字之間的每條路徑進行評分，并選取其中評分最高的路徑作為該節(jié)點的最后得分，最終選取得分最高的若干個節(jié)點。結果表明，關聯(lián)搜索算法不僅可以搜索出文本匹配方法能夠搜索出的結果，而且能夠搜索出其難于搜索得出、但卻與關鍵詞相關的結果。