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

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

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

中圖分類號：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

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

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

1 生物醫(yī)學本體匹配問題

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

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

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

2 生物醫(yī)學概念相似度度量技術

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

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

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

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

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

3.1 編碼機制

假設| C 1|和| C2|分別是2個生物醫(yī)學本體中概念集 C 1和 C2中元素的個數(shù)，進化算法中的每個個體可表示為長度為| C 1|的一維數(shù)組 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 基于推理的生物醫(yī)學概念對剪枝

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

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

4 實驗結(jié)果與分析

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

4.1Anatomy 測試數(shù)據(jù)集

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

4.2Large Biomed 測試數(shù)據(jù)集

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

5 總結(jié)

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

參考文獻

[1]邱實.基于領域本體的生物醫(yī)學本體匹配算法研究[D].哈爾濱：哈爾濱工業(yè)大學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.

（編輯侯湘）