基于進化算法的生物醫學本體匹配技術

摘要：由于生物醫學本體擁有規模龐大的概念和復雜概念間關系，已有本體匹配技術難以高效確定生物醫學本體匹配結果。為解決這一問題，構建了生物醫學本體匹配問題優化模型，提出基于進化算法的生物醫學本體匹配技術來確定最優匹配結果。在求解生物醫學本體匹配問題時，采用一種新的生物醫學本體概念相似度度量來確保匹配結果質量，并通過基于推理的概念對剪枝技術縮小算法的搜索空間，提高算法效率。實驗結果表明，基于進化算法的生物醫學本體匹配技術能有效匹配生物醫學本體。

關鍵詞：進化算法；生物醫學本體匹配；概念對剪枝

中圖分類號：TP182文獻標志碼：A文章編號：1000-582X（2023）06-130-06

Evolutionary algorithm based biomedical ontology matching technique

WANGYing1 ， XUEXingsi1 ， LU Jiawei1 ， HUANGYikun2

（1. School of Information Science and Engineering， Fujian University of Technology， Fuzhou 350118，P. R . China;2. Department of Information Technology， Concord University College Fujian Normal University， Fuzhou 350117， P. R . China）

Abstract： Sincebiomedicalontologiesownlarge-scaleconceptsandcomplexrelationshipsamongthem ，the existing ontology matching techniques are not able to determine the biomedical alignment efficiently. To tackle this challenge， a mathematical optimal model for biomedical ontology matching problem is first constructed， and then an evolutionary algorithm （EA） based biomedical ontology matching technique is proposed to determine the optimalalignment. In particular， whensolving the biomedicalontology matching problem ，a novel biomedical conceptsimilaritymeasureisutilizedtoensurethequalityof thealignment，andareasoning-basedconcept pruningapproachisusedtoreducethealgorithm'ssearchspaceandimproveitsefficiency. Theexperimental results show that EA -based biomedical ontology matching technique is able to match the biomedical ontologieseffectively and efficiently.

Keywords： evolutionary algorithm; biomedical ontology matching; concept pair pruning

生物醫學本體是對生物醫學領域中存在的概念、實例及它們之間關系的規范化描述，使基于生物醫學知識的智能系統之間準確理解彼此數據的真實含義，在語義層面上實現系統間的交互與協作[1-2]。近年來，生物醫學本體被廣泛應用在諸如病歷的語義標注[3]、醫學數據格式標準化[4]、醫療知識表示和共享[5]、臨床數據集成和輔助診療等[6]應用領域。為滿足不同領域需求，本體工程師開發了如基因本體（gene ontology， GO）[7]、人類表型本體（human phenotype ontology， HPO）[8]、國家癌癥研究術語本體（national cancer institute thesaurus， NCI）[9]和醫學系統術語本體（systemized nomenclature of medicine， SNOMED -CT）[10]等眾多生物醫學本體。由于本體工程師們對于客觀事物的認識、描述角度各不相同，導致不同生物醫學本體之間存在嚴重異質問題，阻礙生物醫學智能系統間的交互與協作。

生物醫學本體匹配技術可通過確定本體中異質概念間的對應關系來解決生物醫學本體異質問題。AgreementMakerLight[11]、YAM -BIO[12]、XMap[13]和LogMapBio[14]等目前已有的本體匹配技術在求解生物醫學本體匹配問題時需要消耗大量時間且無法保證匹配結果質量。因此，如何有效識別異質的生物醫學概念、提高生物醫學本體匹配過程效率是求解生物醫學本體匹配問題的關鍵。為有效且高效求解生物醫學本體匹配問題，研究構建了生物醫學本體匹配問題優化模型，并利用進化算法[15]確定最優匹配結果。筆者采用一種新的生物醫學本體概念相似度度量技術確保匹配結果質量，通過基于推理的概念對剪枝技術來縮小算法的搜索空間并提高算法效率。

1 生物醫學本體匹配問題

生物醫學本體是生物醫學概念及概念間關系集合，生物醫學本體匹配結果是2個本體中語義相同的概念對集合。本體匹配結果的質量通常利用查全率、查準率和 F 度量[16]來評價，但需要專家提供標準的本體匹配結果。由于生物醫學中的概念規模龐大，專家無法事先提供標準本體匹配結果，筆者提出一種近似度量技術評價生物醫學本體匹配結果質量。通過實驗觀察發現，生物醫學本體匹配結果的質量同匹配結果中的概念對數量和平均相似度值成正比。給定一個生物醫學本體匹配結果 A ，提出如下公式近似評價生物醫學本體匹配結果質量

式中： r （A）=； | A |是 A 中概念匹配對的數量；M 是大的正整數；p （A）= ， sim （ ai ）表示 A 中第i個概念對的相似度值。在此基礎上，給定2個生物醫學本體 O 1和 O 2，生物醫學本體匹配問題的數學優化模型定義如下

式中：| O 1|和| O 2|分別表示 O 1和 O2中的概念數量；xi = j，j =1，2， …;| O 2|表示 O 1中第i個概念同 O2中第j個概念形成概念對（若x i = 0，則 O 1中第i個概念沒有匹配上任何一個概念）； X 表示一個本體匹配結果，該模型的目標是最大化f （X ）的值。

2 生物醫學概念相似度度量技術

概念相似度度量技術是本體匹配技術的基礎，生物醫學概念的異質性高、專業性強、結構復雜，因此已有概念相似度度量技術難以有效識別語義相同的生物醫學概念。在基于概念名稱、背景知識庫和本體概念體系關系結構這三類相似度度量技術基礎上，提出混合度量技術以識別異質的生物醫學概念。給定2個生物醫學概念 c 1和 c2，利用本體概念體系關系結構獲取二者直接的子概念集合 C 1和 C2，分別抽取出 C 1和 C2中所有概念的名稱和屬性名稱構建二者對應的信息檔案 p 1和 p2，通過其對應的信息檔案 p 1和 p2的相似度值來度量 c 1和 c2的相似程度，相關的計算公式如下

式中：| p 1|和| p2|分別是 p 1和 p2中元素的個數；p 1i 和 p2j 分別是 p 1和 p2中第i個和第j 個元素。當 p 1i 和 p2j 在生物醫學知識庫 Unified Medical LanguageSystem （UMLS）[16]中是同義詞時，sim'（p 1i ，p2j ）=1 ，否則 sim'（p 1i ，p2j ）= N - gram （ p 1i ，p2j ），其中 N -gram 距離[17]是用于度量生物醫學概念名稱編輯距離最有效技術。

3 求解生物醫學本體匹配問題的進化算法

生物醫學本體匹配問題是一個復雜的大規模優化問題，進化算法具有全局尋優能力、自動獲取和指導優化搜索空間并自適應調整搜索方向，是求解該問題的有效方法。提出的用于求解生物醫學本體匹配問題的進化算法框架如表1所示。

該算法初始化進化代數 t 并隨機初始化種群 Pt ，對種群中每個個體的質量進行評價；在每一代的進化過程中，通過賭輪盤方法來選出新一代種群，依據交叉概率對種群中的個體執行單點交叉操作以實現個體間的信息交換，依據變異概率對種群中的個體執行位點變異操作以保證種群多樣性；最后更新精英個體（歷史最優解）并將精英個體取代種群中適應度值最低的個體以保證精英個體不會在進化過程中丟失，當精英個體被更新后，算法依據新的精英個體信息對概念進行剪枝以縮小算法的搜索區域，當算法進化到最大代數tmax后終止，輸出精英個體 elite。

3.1 編碼機制

假設| C 1|和| C2|分別是2個生物醫學本體中概念集 C 1和 C2中元素的個數，進化算法中的每個個體可表示為長度為| C 1|的一維數組 N1 N2…N| C 1|，其中，Ni ∈{0， 1，2， … ， | C2|}。當 Ni = j ∈{1，2， … ， | C2|}時，表示 C 1中的第i個概念同 C2中的第j個概念匹配上；當 Ni =0時，表示 C 1中的第i個概念沒有匹配上 C2中的任何一個概念。

3.2 基于推理的生物醫學概念對剪枝

針對大規模本體匹配問題，目前是通過本體劃分算法將大規模生物醫學本體劃分為若干本體分塊，問題轉化為等價的若干個小規模的本體分塊匹配問題。本體劃分算法存在3個局限： 1）本體劃分算法的時空復雜度同后續大規模本體匹配算法的時空復雜度一樣，無法從本質上提高匹配過程的效率；2）本體劃分算法無法控制本體分塊規模，使本體分塊的規模不是太大就是太小，使得匹配過程效率不高； 3）本體劃分算法會導致位于分塊邊緣概念丟失一定程度的語義信息，使本體匹配結果質量不高。為縮小匹配過程中進化算法的搜索空間，提出一種基于推理的生物醫學概念對剪枝方法，利用生物醫學本體的概念體系結構減少匹配過程中所需的概念相似度值計算次數，提高生物醫學本體匹配過程效率。

通過實驗發現： 1）生物醫學本體的概念體系結構通常是通過“is-a”和“part-of”關系來構建的，正確的匹配結果同該體系結構一致；2）生物醫學本體在某個區域內的大部分概念會同另一個生物醫學本體在概念對，則 ci 所有的直接子概念（或父概念）同cj所有的直接父概念（或子概念）為不相似概念，即將cj所有的直接父概念（或子概念）編號從 ci 所有的直接子概念（或父概念）對應基因位可行域中移除。

4 實驗結果與分析

實驗中采用國際本體匹配競賽（ ontology alignment evaluation initiative， OAEI）提供的 Anatomy 測試數據集和 Large Bio 測試數據集。表2-3分別給出了研究方法的匹配結果（30次獨立運行的均值）和 OAEI 參與者的匹配結果。進化算法采用的配置如下：種群規模=100，交叉概率=0.85，變異概率=0.02，最大進化代數=3000，相似度值閾值=0.95。算法的配置是通過實驗確定的，該配置可以確保獲取的匹配結果質量最好。

4.1Anatomy 測試數據集

Anatomy 要求是將成年鼠類解剖學本體（2744個概念）同 NCI 中的人類解剖學本體（3304個概念）進行匹配。從表2中可以看出，研究方法獲取的匹配結果查全率、查準率和 F 度量值明顯高于其他前沿本體匹配技術。研究方法的查全率最高，這說明提出的概念對剪枝可以在保證生物醫學本體匹配結果質量前提下提高本體匹配過程的效率（研究方法的運行時同LogMap并列第1）。最后，方法的標準差較小，說明其穩定性較好。

4.2Large Biomed 測試數據集

Large Biomed 包含了3個任務，要求匹配3個大規模生物醫學本體 FMA （78989個概念）、 SNOMEDCT （306591個概念）和 NCI （66724個概念）。從表3中可以看出，方法在3個任務中的查準率和 F 度量值都最高，查全率和運行時在2個任務中最好，相應的標準差值較小。基于進化算法的生物醫學本體匹配技術可以比前沿的生物醫學本體匹配技術更有效匹配生物醫學本體。

5 總結

生物醫學本體匹配技術能確定不同生物醫學本體中異質概念，實現基于本體的生物醫學智能系統之間協作。研究提出一種基于進化算法的生物醫學本體匹配技術求解該問題，并確定最優的本體匹配結果。在算法求解過程中，采用新的生物醫學概念相似度度量和基于推理的概念對剪枝來提高算法性能。實驗結果表明，基于進化算法的本體匹配技術能夠有效匹配生物醫學本體。

參考文獻

[1]邱實.基于領域本體的生物醫學本體匹配算法研究[D].哈爾濱：哈爾濱工業大學2015.

QiuS . Researchonbiomedicalontologymatchingalgorithmbasedondomainontology[D]. Harbin： HarbinInstituteof Technology， 2015.（in Chinese）

[2] ChatterjeeN ，KaushikN ，GuptaD ，etal. Ontologymerging： apracticalperspective[C]//InternationalConferenceonInformation and Communication Technology for Intelligent Systems . Cham： Springer， 2018：136-145.

[3] Yan S K ， Wong K C . Elucidating high-dimensional cancer hallmark annotation via enriched ontology[J]. Journal of BiomedicalInformatics， 2017， 73：84-94.

[4] Ping P P， HermjakobH ， Polson J S ， et al. Biomedical informatics on the cloud： a treasure hunt for advancing cardiovascularmedicine[J]. Circulation Research， 2018， 122（9）：1290-1301.

[5] Strang J F， Meagher H ， Kenworthy L ， et al. Initial clinical guidelines for Co-occurring autismspectrum disorder and genderdysphoria or incongruence in adolescents[J]. Journal of Clinical Child amp; Adolescent Psychology， 2018， 47（1）：105-115.

[6] HeringaM ， Floor-Schreudering A ， De Smet P A G M ， et al. Clinical decision support and optional point of care testing of renalfunctionforsafeuseof antibioticsinelderlypatients： aretrospectivestudyincommunitypharmacypractice[J]. Drugs amp; Aging， 2017， 34（11）：851-858.

[7] Consortium T G O . Expansion of the gene ontology knowledgebase and resources[J]. Nucleic Acids Research， 2017， 45（D1）：D331-D338.

[8] Taboada M ， Rodriguez H ， Gudivada R C ， et al. A new synonym -substitution method to enrich the human phenotype ontology[J]. BMC Bioinformatics， 2017， 18（1）：446.

[9] ZhengL ，MinH ，ChenY，etal. AuditingNationalCancerInstitutethesaurusneoplasmconceptsingroupsof higherrorconcentration[J]. Applied Ontology， 2017， 12（2）：113-130.

[10] Sanz X ， ParejaL ， Rius A ，etal. Definitionof aSNOMEDCT pathologysubsetandmicroglossary， basedon 1.17 millionbiological samples from the Catalan Pathology Registry[J]. Journal of Biomedical Informatics， 2018， 78：167-176.

[11] Cruz I F， PalmonariM ，Caimi F， et al. Building linked ontologies with high precision usingsubclass mapping discovery[J].Artificial Intelligence Review， 2013， 40（2）：127-145..

[12] Duchateau F， BellahseneZ .YAM ： A step forward for generating a dedicated schema matcher[J]. Transactions on Large-ScaleData-and Knowledge-Centered Systems XXV， 2016：150-185.

[13] Djeddi W E ， Yahia S B ， Nguifo E M . A novel computational approach for global alignment for multiple biological networks[J].IEEE/ACM transactions on computational biology and bioinformatics， 2018， 15（6）：2060-2066.

[14] HarrowI，Jiménez-RuizE ，SplendianiA ，etal. Matchingdiseaseandphenotypeontologiesintheontologyalignmentevaluation initiative[J]. Journal of biomedical semantics， 2017， 8：1-13.

[15] RudolphG . Anevolutionaryalgorithmforintegerprogramming[C]//ParallelProblemSolvingfromNature — PPSNIII .Berlin， Heidelberg： Springer Berlin Heidelberg， 1994：139-148.

[16] BodenreiderO . TheUnifiedMedicalLanguageSystem （UMLS）： integratingbiomedicalterminology[J]. NucleicAcidsResearch， 2004， 32： D267-D270.

[17] KondrakG . N -gramsimilarityanddistance[C]//StringProcessingandInformationRetrieval. Berlin，Heidelberg： Springer，2005：115-126.

（編輯侯湘）