Informatica Medica Slovenica 2008; 13(1) 1 Izvirni znanstveni članek Hiter in preprost algoritem za razdvoumljanje simbolov genov Andrej Kastrin, Dimitar Hristovski Izvleček. Razdvoumljanje simbolov genov je raziskovalno zelo aktualno področje. Največji problem predstavlja ločevanje med besednimi simboli, ki označujejo gene oz. njihove produkte ter simboli, ki se nanašajo na ostale biomedicinske koncepte (npr. CT, MR). V članku predstavimo hiter in preprost pristop k razdvoumljanju, ki temelji na razvrščanju MEDLINE® zapisov v genetsko in negenetsko domeno, ob predpostavki, da se simboli v genetski domeni najverjetneje nanašajo na gene. Algoritem sloni na statistični primerjavi domensko reprezentativnih korpusov zgrajenih na osnovi MeSH® deskriptorjev. Metoda je jasno razumljiva, preprosta za implementacijo ter računsko nezahtevna. Točnost razvrstitve, merjena na validacijski množici podatkov, je znašala 0,91. Algoritem je implementiran kot pomožni sistem za razdvoumljanje simbolov genov v sistemu za odkrivanje dejanskih ali potencialnih zakonitosti iz bibliografskih podatkov BITOLA. A fast and simple document classification algorithm for gene symbol disambiguation Instituciji avtorjev: Inštitut za medicinsko genetiko, Univerzitetni klinični center (AK), Inštitut za biomedicinsko informatiko, Medicinska fakulteta, Univerza v Ljubljani (DH). Kontaktna oseba: Andrej Kastrin, Inštitut za medicinsko genetiko, Univerzitetni klinični center, Šlajmerjeva 3, 1000 Ljubljana. email: andrej.kastrin@guest.arnes.si. Abstract. Gene symbol disambiguation is an important problem for biomedical text mining systems. When detecting gene symbols in MEDLINE® citations one of the biggest challenges is the fact that many gene symbols also denote other, more general biomedical concepts (e.g. CT, MR). Our approach to this problem is first to classify the citations into genetic and non-genetic domains and then to detect gene symbols only in the genetic domain. We used ontological information provided by Medical Subject Headings (MeSH®) for this classification task. The proposed algorithm is fast and is able to process the full MEDLINE distribution in a few hours. It achieves predictive accuracy of 0,91. The algorithm is currently implemented in the BITOLA literature-based discovery support system. ■ Infor Med Slov: 2008; 13(1): 1-8 2 Kastrin A et al.: Hiter in preprost algoritem za razdvoumljanje simbolov genov Uvod Redno sledenje novim znanstvenim spoznanjem, rezultatom raziskav in razvoju tehnologij je celo za izkušenega raziskovalca z dobro informacijsko podporo zahteven zalogaj. Bibliografske zbirke rastejo iz dneva v dan; na področju biomedicine najpogosteje uporabljena zbirka MEDLINE® trenutno obsega že več kot 16 milijonov zapisov. Za učinkovit priklic relevantnih zapisov zato potrebujemo ustrezno zmogljive iskalnike. Uveljavljenim načinom poizvedovanja po tekstovnih podatkovnih zbirkah se je v zadnjem desetletju pridružilo področje z literaturo podprtega odkrivanja zakonitosti iz podatkov (angl. literature-based discovery), katerega namen je iskanje novih in potencialno uporabnih zakonitosti na osnovi implicitnih relacij med posameznimi bibliografskimi zapisi. Oče ideje je Don R. Swanson, ki je na ta način odkril, da ribje olje lahko služi kot učinkovito zdravilo pri zdravljenju Raynaundovega sindroma.1 Skupaj s sodelavci je ponudil tudi orodje za odkrivanje potencialno zanimivih relacij v obliki prosto dostopne spletne storitve Arrowsmith.2 Inovativen koncept so povzeli tudi drugi raziskovalci in ga na različne načine implementirali v svojih iskalnih sistemih. BITOLA je interaktivni sistem za podporo odkrivanju dejanskih ali potencialnih zakonitosti iz bibliografskih podatkov na področju biomedicine in je plod domačega znanja.3 Relacije med biomedicinskimi koncepti so opisane s pomočjo asociacijskih pravil. Kljub temu, da omogoča posplošeno odkrivanje novega znanja znotraj celotne biomedicinske domene, je zlasti uporaben za opisovanje relacij znanja med posameznimi geni in fenotipom oz. boleznimi. V trenutni implementaciji sistem tekstovne simbole, ki se potencialno nanašajo na gene, ekstrahira iz naslovov in povzetkov posameznih MEDLINE zapisov. Problem pa predstavlja učinkovito ločevanje med simboli, ki dejansko označujejo gene oz. njihove produkte ter simboli, ki se nanašajo na ostale biomedicinske koncepte. Ideja je, da najprej razvrstimo zapise na genetsko in negenetsko domeno,4 pri čemer lahko upravičeno pričakujemo, da se bodo v genetski domeni simboli najverjetneje nanašali na posamezne gene. Z izrazom genetska domena označujemo množico MEDLINE zapisov, v kateri je verjetnost pojavljanja simbolov genov večja kot v katerikoli drugi množici zapisov. Nalogo lahko opišemo kot problem razvrščanja MEDLINE zapisov na genetsko in negenetsko domeno na osnovi vsebine posameznega zapisa. Formalno imamo torej množico domen C = (c1, C2} ter množico zapisov D = {d1, d2, ..., dn}, kjer vsakemu paru (c, d; i = 1,2 in 1 < j 2, smo uvrstili v genetsko domeno. Pražna vrednost Slika 2. Točnost razvrstitve zapisov v odvisnosti od pražne vrednosti na testni množici zapisov. Proces razvrščanja si oglejmo na primeru. Izbrali smo dva MEDLINE zapisa, katerih naslova sta "Strain-dependent localization, microscopic deformations, and macroscopic normal tensions in model polymer networks" (PMID: 15697942) in "Recessive motor neuron diseases: mutations in the ALS2 gene and molecular pathogenesis for the upper motor neurodegeneration" (PMID: 15651293). Prvi zapis vsebuje osem, drugi pa sedem deskriptorjev MeSH. Trije deskriptorji v drugem zapisu so prazni (Aminals, Humans in Mice), zato jih izločimo iz nadaljnjega procesiranja. Glede na vsak deskriptor povečamo oz. zmanjšamo vrednost odločitvenega dosežka skladno z vrednostjo indikatorske spremenljivke (Tabela 1). Končni rezultat sta dva odločitvena dosežka: Dosežek (PMID: 15697942) = -6 Dosežek (PMID: 15651293) = 4. Glede na zgoraj definirano pražno vrednost lahko prvi zapis uvrstimo v negenetsko domeno, drugi zapis pa v genetsko domeno. Učinkovitost klasifikatorja smo preverili na validacijski množici zapisov. Na Sliki 3 so prikazane vrednosti priklica in natančnosti za različne pražne vrednosti parametra 0. ~~i-1-1-1-1-r 0.0 0.2 0.4 0.6 0.8 1.0 Priklic Slika 3. Graf odnosa med priklicem in natančnostjo razvrstitve na validacijski množici zapisov. Informatica Medica Slovenica 2008; 13(1) 7 Povedena metoda je dosegla Acc = 0,91 točnost razvrstitve, pri čemer je priklic znašal Rec = 0,64, natančnost pa Pre = 0,93. Harmonična sredina priklica in natančnosti je znašala F = 0,76. Graf poteka skozi dve točki. Točka (0,1) označuje klasifikator, ki ne prepozna genetsko relevantnih zapisov. Vsi negenetski zapisi so v tem primeru razvrščeni pravilno, genetski zapisi pa napačno. V točki (1,0) klasifikator vse zapise razvrsti kot genetsko relevantne. Genetski zapisi so v tem primeru razvrščeni pravilno, vsi negenetski zapisi pa napačno. Optimalno točnost oz. optimalno razmerje med priklicem in natančnostjo je v našem primeru klasifikator dosegel v točki A. Če pražno vrednost povečamo (0B = 5), bomo zapise razvrstili z večjo natančnostjo (Pre = 1,00), na račun katere pa se bo zmanjšal priklic (Rec = 0,27). Do obratnega učinka pride v točki C, kjer pražno vrednost zmanjšamo (0C = -1). Dokumenti so v tem primeru razvrščeni z manjšo natančnostjo (Pre = 0.67), priklic pa je višji (Rec = 0.82). Zaključki V članku smo predstavili preprost in hiter algoritem za razvrščanje MEDLINE zapisov na osnovi deskriptorjev MeSH. Trenutno je algoritem implementiran kot pomožni sitem za razdvoumljanje simbolov genov v interaktivnem sistemu za podporo odkrivanju zakonitosti iz bibliografskih podatkov BITOLA. Eksperimentalni rezultati potrjujejo razmeroma visoko napovedno točnost klasifikatorja (Acc = 0,91). V odvisnosti od namena poizvedovanja ter željenega razmerja med priklicem in natančnostjo, lahko pražno vrednost tudi spreminjamo. V nadaljnjih raziskavah bomo preizkusili klasifikatorje z vključitvijo kompleksnejših prediktorskih spremenljivk: (i) kvalifikatorjev MeSH, ki podrobneje omejijo vsebinski obseg posameznega deskriptorja, (ii) parov deskriptor/kvalifikator ter (iii) prostim besedilom naslova in povzetka MEDLINE zapisa. V gradnji je tudi obsežnejši označeni korpus zapisov, ki bo omogočal bolj zanesljivo in veljavno vrednotenje uporabljenih klasifikatorjev. Zahvala Avtorja se zahvaljujeva Susanne M. Humphrey in Thomasu C. Rindfleschu za koristne napotke in vzpodbudne komentarje. Raziskovalna sredstva je zagotovila Javna agencija Republike Slovenije za raziskovalno dejavnost (J3-7411). Literatura 1. Swanson DR: Fish oil, Raynaud's syndrome, and undiscovered public knowledge. Perspect Biol Med 1986; 30(1): 7-18. 2. Swanson DR , Smalheiser NR: An Interactive System for Finding Complementary Literatures: A Stimulus to Scientific Discovery. Artif Intell 1997; 91(2): 183-203. 3. Hristovski D, Stare J, Peterlin B, et al.: Supporting discovery in medicine by association rule mining in MEDLINE and UMLS. Medinfo 2001; 10(2): 1344-1348. 4. Hristovski D, Peterlin B, Mitchell JA, et al.: Using literature-based discovery to identify disease candidate genes. Int J Med Inform 2005; 74(2-4): 289-298. 5. Feldman R, Sanger J: The Text Mining Handbook: Advanced Approaches in Analyzing Unstructured Data. Cambridge 2006: Cambridge University Press. 6. Manning CD, Schuetze H: Foundations of statistical natural language processing. Cambridge 2003: MIT Press. 7. Agiree E, Edmonds P (ur.): Word sense disambiguation: Algorithms and applications. Berlin 2006: Springeer. 8. Weeber M, Schijvenaars BJ, Van Mulligen EM, et al.: Ambiguity of human gene symbols in LocusLink and MEDLINE: creating an inventory and a disambiguation test collection. Proc AMIA Symp 2003; 704-708. 9. Chen L, Liu H, Friedman C: Gene name ambiguity of eukaryotic nomenclatures. Bioinformatics 2005; 21(2): 248-256. 10. Di Fabio F, Alvarado C, Majdan A, et al.: Underexpression of mineralocorticoid receptor in colorectal carcinomas and association with 8 Kastrin A et al.: Hiter in preprost algoritem za razdvoumljanje simbolov genov VEGFR-2 overexpression. J Gastrointest Surg 2007; 11(11): 1521-1528. 11. Xu H, Fan JW, Hripcsak G, et al.: Gene symbol disambiguation using knowledge-based profiles. Bioinformatics 2007; 23(8): 1015-1022. 12. Savova G, Pedersen T, Purandare A, et al.: Resolving ambiguities in biomedical text with unsupervised clustering approaches. Research Report UMSI 2005/80 and CB Number 2005/21; Minneapolis, Minnesota 2005: University of Minessota Supercomputing Institute. 13. Schijvenaars BJ, Mons B, Weeber M, et al.: Thesaurus-based disambiguation of gene symbols. BMC Bioinformatics 2005; 6: 149. 14. Humphrey SM, Rogers WJ, Kilicoglu H, et al.: Word sense disambiguation by selecting the best semantic type based on Journal Descriptor Indexing: preliminary experiment. J Am Soc Inform Sci Tech2006; 57(1): 96-113. 15. Liu H, Lussier YA, Friedman C: Disambiguating ambiguous biomedical terms in biomedical narrative text: an unsupervised method. J Biomed Inform 2001; 34(4): 249-261. 16. Farkas R: The strength of co-authorship in gene name disambiguation. BMC Bioinformatics 2008; 9: 69. 17. Maglott D, Ostell J, Pruitt KD, et al.: Entrez Gene: gene-centered information at NCBI. Nucleic Acids Res 2007; 35(Database issue): D26-31. 18. Cohen J: A coefficient of agreement for nominal scales. Educ Psychol Meas 1960; 20(1): 37-46.