Fa oltà di S ienze Matemati he Fisi he e
Naturali
Corso di Laurea Spe ialisti a in Te nologie
Informati he
Tesi di Laurea
Sviluppo ed integrazione di strategie di
lustering in strumenti di ri er a per
grandi ban he dati biol ogi he
Candidato:
Claudio Corsi
Relatori:
Prof. Paolo Ferragina
S rivereiringraziamentisirivelasempreil ompitopiùdi ileperilris hiodidimenti arequal uno.Se iò
dovessea aderenonèperingratitudine,maperdistrazione. Devoringraziarelamiafamiglia heinmolti
modimiha onsentitodiarrivareas riverequesteparole. Ringraziogliami i, heinmodo onsapevoleo
lustering in strumenti di ri er a per
grandi ban he dati biol ogi he
Claudio Corsi
1 Introduzione 9
2 Motori di ri er a e ban he dati biologi he 17
2.1 I motori diri er a didomani. . . 17
2.2 Le ban he dati biologi he . . . 20
2.2.1 Il ontenuto delle ban he dati biologi he e la qualità
dei dati . . . 26
2.2.2 La ban adati UNIPROT . . . 28
2.3 Un nuovoappro io alleban he dati biologi he . . . 30
3 Gene Ontology 37
3.1 Struttura diGene Ontology . . . 38
3.2 Tipi direlazioni . . . 39
3.3 Utilizzo diGene Ontology nella lusterizzazione dei risultati . 41
3.3.1 Il metododelle Upward Paths . . . 47
4 Elementi di Information Retrival 53
4.1 Strutture a supporto della fase diindi izzazione . . . 53
4.2 Il modellovettoriale . . . 59
Com-5.1 Ban he dati diinteresse . . . 68
5.2 A esso eindi izzazione dei dati . . . 70
5.3 Formatodeido umentieindi izzazionemedianteApa heLu ene 73 5.4 Parsingdei do umenti medianteCommons Digester . . . 79
6 Progetto del motore di ri er a e riteri di lustering 85 6.1 Il livellodia esso ai dati . . . 87
6.2 Struttura del livellodi presentazione . . . 90
6.2.1 Raggruppamento dei risultatiin viste . . . 96
6.2.2 Sfruttare leviste per migliorare lari er a . . . 100
6.3 Classi e metodi asupporto dell'appli azione . . . 109
6.4 La Business Logi . . . 110
6.4.1 Appli azione dei metodidi business logi alle viste. . . 118
6.4.2 Aspetti implementativi . . . 119
6.5 Utilizzo diBLAST omemetodoalternativoper lari er a . . 121
Introduzi one
Iprogressi nel ampodellabiologiamole olaredegliultimiannihanno
deter-minato una res itaesponenziale delle informazionie dei dati a disposizione
dei biologi. Il sequen ziamento del genomaumano e di altriorganismi
assie-me allo studio del DNA e delle proteine hanno dato un forte impulso alla
bioinformati a he ra oglie la grande s da di fornire strumenti adeguatial
ne di analizzare e apire l'enormequantità didati prodotta inlaboratorio.
La bioinformati a è una nuova dis iplina he si o upa dello sviluppo e
dell'integrazione dellari er ainformati aalservizio dellari er a
biote nolo-gi a. Perfare iòutilizzastrumentiinformati iperanalizzareidati biologi i
he des rivono sequen zedigeni, sequen ze estruttura delleproteine, pro essi
bio himi inelle ellule, e ...Rappresenta pertanto una dis iplina a avallo
tra due s ienze he trae soluzioniderivanti dall'appli azione di te ni he
no-te in ambito informati o per risolvere problemi orrelati alla res ita della
onos enza in ambito biologi o.
Labiologiaètradizionalmenteunas ienzaeuristi aedes rittivapiuttosto
hededuttiva. Laquantitàdidatiosservatiinlaboratorionegliultimide enni
ha generato la ne essità di una atalogazione e onservazione degli stessi.
Tuttaviaavere moltidatienon potervi a ederesigni anonavere nientedi
quantità di dati erto non rappresenta più il problema prin ipale né lo è il
loro a esso in tempi rapidi. La vera s da è trovare un modo e a e per
supportare ilbiologonella omprensione dei dati.
Il ontestoappenades rittori hiamaallamenteunaltroambitooggi
mol-tonoto estudiato,ossia ilWeb. Leanalogiesono evidenti: inentrambii asi
l'utentesitrovadifronteadenormi ollezionididatiespessodeveimpiegare
molto tempo per poter trovare una risposta esauriente alla sua domanda. I
motoridiri er adise ondagenerazione he operanosulWeb ( omeGoogle)
ries onoafornireunarisposta heben soddisfalaquery dell'utentemediante
l'impiego di te ni he in grado di dare una valutazione oggettiva
dell'impor-tanza di una pagina sulla base dell'analisi del grafo Web. I motori di terza
generazione er ano ora di dare maggiore informazione all'utenteindi ando
possibiliinterpretazionidel risultatoed operandori er he he tengano onto
sempre più del suo pro lo. Qual osa di analogo sta su edendo nel ampo
della bioinformati a. L'utente inizia ad avere non più la sola ne essità di
sapere tutti ido umenti he soddisfano una sua query , maan he lerelazioni
he tali do umenti presentano, osì da apire meglio quello he sino a quel
momento è stato atalogato. Più un sistema ries e a soddisfare tale
biso-gno menosforzo dovràfare il ri er atoreper omprendere imolti dati a sua
disposizione. L'esperienza del Web può rappresentare un ottimo punto di
partenza per lo studio di questa nuova problemati a. Capire i me anismi
e le soluzioni adottate in questo ontesto può essere utile al ne di reare
uno strumentoin gradodirispondereaduna interrogazionesudi unaban a
dati biologi asapendo mostrare le orrelazioni tra i dati ritornati. Tuttavia
l'ambito biologi o presenta aspetti ompletamente nuovi sia per il tipo di
informazione rappresentata he per iltipo di ontrollo operato suidati.
Èsemprepiùdiusa l'idea hesulWeb sipossatrovarequalsiasi
dibilitàdell'informazionepresentataoinrelazioneallasuaa uratezza. Nelle
ban he dati biologi he lasituazione è ovviamente diversa. I dati si
riferis o-noprin ipalmenteasequen zedima romole oleoadinformazionirelativead
esse, ome nel aso diriferimentibibliogra i o dati strutturali o funzionali.
Inoltreidatisono uratiegestitidaespertidel settore,rendendo osì
l'infor-mazione erti ata. In questo aso l'analogia on il Web risiedenelle pagine
lassi ate in dire tory ( ome DMOZ) da uratori, i quali ne garantis ono
l'attendibilità. Nonostante le dierenze esistenti tra i due ontesti, in
en-trambii asi l'utentepresenta ilmedesimobisogno,ossia quellodiavere uno
strumentoingrado diguidarlo nella onsultazionedeimolti dati disponibili.
Questoè an orapiù vero nelle ban he datibiologi hedove vengonodes ritti
elementi he per natura sono in relazione tra di loro, relazioni he devono
essere omprese e rese note al biologo. Per onseguire questo obiettivo esso
può imparare a orrelare amano, mediantela propriaesperienza, idati on
ui sitrovaa he fare,imparandoari er areinmanierasempremigliore
tra-mite glistrumentidia essoalleban he dati disponibili. Chedire peròsein
questa operazionevenissesupportatodaunostrumentoingradodimostrare
automati amente le relazioni he legano i risultati di una ri er a? Oppure
in gradodimettere inlu e aspetti menoevidenti dei risultatiottenuti
sfrut-tando il più possibile le informazioni a orredo delle singole sequen ze o dei
singolidati oggettodella ri er a? Èquesta ladirezioneesplorata nell'ambito
di questa tesi il ui s opo è quello di porre le basi per la ostruzione di un
sistemadiri er aingradodisupportareilbiologonellesue ri er he inban a
dati. Il motoredi ri er a sviluppatoè ingrado di mettere in evidenza le
re-lazionipiù interessantidellalistadei risultatiritornatimediantel'impiegodi
ontologiee tassonomie, on l'obiettivo difornire all'utentedei feedba k utili
al ne di ra nare la ri er a. Il biologo interessato ad un argomento potrà
1. Formulareuna query dipartenza;
2. Consultare non solo la lista dei risultati restituiti, ma an he la
gerar- hia dei on etti e delle relazioni aratterizzanti il risultato ottenuto,
generata mediante lustering dei do umentiritornati;
3. Ra nare lari er a sulla base delle informazionipresentate;
Il punto entrale dell'intero sistema risiede nell'insieme degli algoritmi
impiegati per la generazione delle informazioni aggiuntive espresse
median-te eti hette relazionate tra di loro. Queste devono essere rappresentative
di al une proprietà orelazioni aratterizzantil'insieme dei risultatiin modo
da onsentire al biologo di omprendere in misura maggiore i dati, le loro
proprietà e relazioni. Piuttosto he onsiderare la solalista non strutturata
delle risposte, l'utente potrà onsultare an he le eti hette prodotte
automa-ti amente e vedere quali e quanti do umenti ri adono sotto quali on etti.
Questo determina pertanto un raggruppamento qualitativo dei risultati in
gruppi i ui elementi mostrano una medesima proprietà. Naturalmente un
do umentopotràappartenere ontemporaneamenteapiùgruppiqualora
pre-senti aratteristi he diverse. L'utente osì non avrà solamente la per ezione
diqualisonole aratteristi he piùrilevantideido umentitrovati(gliinsiemi
on ardinalità maggiore) ma vedrà an he quali sono le relazioni he
sussi-stono tra i do umenti. Fissatoun insieme dirisultati, ilsistema è inoltre in
grado di produrre moltepli igerar hie di on etti, generate in base adiversi
riteri selezionabilidall'utente. Questo ore l'opportunità di avere più viste
del medesimo insieme dei risultati, on lo s opo di ra nare la ri er a
tra-mite la ombinazione dei on etti appartenenti a viste diverse mediante ui
generare query più selettivee pre ise.
Figura1.1: Larisposta generataperlaqueryopsin.
per ui i feedba k generati a fronte diun risultato devono essere
ne essaria-mente di fa ile omprensione per hiunque. Nell'ambito delle basi di dati
biologi he il punto di partenza è diverso. L'utente è uno spe ialista he
o-nos ei dati on ui haa he fareed èabituatoall'utilizzoditerminispe i i
del suosettore. Questoaspettogiusti aunamaggiore omplessitàdel
risul-tato propostodalsistema diri er a he, adun o hionon esperto, potrebbe
appariredidi ile omprensioneotropposo sti ato. Al ontrario,ilbiologo
troverà nei feedba k generatiterminied espressionialuifamiliari. In Figura
1.1 viene mostrata, a titolo diesempio, la risposta he il sistemasviluppato
Lasoluzione proposta,standoaiprogettianalizzatiinquestoambito,èla
primanelsuogenere. Progettianaloghisottoal uniaspettisonoallostudioo
giàesistono,tuttaviainquesta tesi siindagaperlaprimavoltalapossibilità
di operare do ument lustering direttamentesui dati ontenutinelle ban he
dati biologi he, impiegando le meta-informazioni a orredo delle singole
se-quenze (DNA o proteine). Progetti omeClusterMed [29℄oGOPubMed [30℄
arontano un tema analogo, ma il do ument lustering è eseguito a fronte
di ri er he sulla ollezione dido umenti PubMed , ontenente arti olirelativi
all'ambitomedi o e biologi o. Il primo, ClusterMed , bene ia inparti olare
della te nologia di Vivísimo [21℄ per generare i gruppi, impiegando an he la
tassonomia MeSH (Medi al Subje t Headings) nel pro esso di ustering. Il
se ondo, GOPubMed ,proponeunasoluzionebasatasull'impiegodiGene
On-tology 1
pera edere alla ollezione PubMed . Apartire dalrisultatoottenuto
interrogandoPubMed on laquery sottopostadall'utente,viene appli atoun
algoritmodi estrazione dei termini signi ativi dagli abstra t ritornati. Tali
termini vengonoimpiegatiper asso iare ogni do umento aduna o più lassi
di on etti des ritti da Gene Ontology operando osì un raggruppamento.
Ogni gruppo viene identi ato dal nome della lasse stessa ed i gruppi
ge-nerati vengono organizzati in base allerelazioni he legano, nell'ontologia, i
termini utilizzati.
Il lavoro svolto inquesta tesi è stato a ettato ome poster a RECOMB
2006 (Resear hinComputationalMole ularBiology)[32℄ non hé daB.IT.S
(The Bioinformati sItalianSo iety) [33℄.
1
Comesaràspiegatopiùavanti,GeneOntologyèun'ontologiaingradodiorireuna
Struttu ra della tesi
•
Il apitolo 2 prende in onsiderazione lo stato dell'arte dei motori di ri er ae delle ban he dati biologi he. Inoltre pone le basi del progettoanalizzando il aso di studio;
•
Il apitolo3des rive GeneOntology ed in he modole informazioniin essa ontenute sono impiegatenella lusterizzazione dei do umenti;•
Il apitolo4puntualizzaal unielementidiInformationRetrival impie-gatinel progetto;•
Il apitolo 5 mostra ome èstato arontato ilproblema dell'indi izza-zione dei dati e qualistrumenti sono stati impiegatiper tale s opo;•
Il apitolo 6 spiega in dettaglio l'organizzazione del motore di ri er a edillustralete ni hedi lusteringimpiegateedin hemodovienedataMotori di ri er a e ban he dati
biologi he
In questo apitoloviene analizzatolostato dell'artedellosviluppodimotori
di ri er a per il Web on parti olare attenzione a quelle he sono le nuove
tendenze di sviluppo in questo settore in ostante evoluzione. Viene poi
presain onsiderazionelaproblemati aesistentenelleban he datibiologi he
relative a sequen ze di DNA e proteine. Chi opera nel ampo della biologia
mole olareavverteinmanierasempre res ente lane essità distrumentipiù
e a i per la ri er a in tali ban he dati, ne essità he può trovare risposta
negli appro iimpiegatinello sviluppodei nuovi motoridi ri er aWeb.
A on lusione viene onsideratoin he modol'attualete nologia dei
mo-toridiri er aperilWeb possaessereimpiegataperlosviluppodiunsistema
di ri er ain gradodi soddisfare le nuovene essità dei biologi.
2.1 I motori di ri er a di domani
Lo s opo di un motore di ri er a è quello di re uperare da una ollezione
i do umenti giudi ati rilevanti a fronte di una ri hiesta formulata da un
1. Larilevanzadiun do umentoèungiudiziosoggettivonon hévariabile
nel tempo;
2. La ollezione potrebbe essere eterogenea e altamentedinami a on un
fattore di res itanon prevedibile;
3. Gli utenti possono avere attese e obiettivi diversi;
4. Chi sottopone la query manifesta generalmente un atteggiamento
pi-gro limitandosia onsideraresolamenteleprimerisposte(tipi amente
non più di 10) e introdu endo query mal poste e/o parti olarmente
brevi.
Il problema è piuttosto noto in ambito Web dove la ollezione di
do u-menti onsiderata,ossial'interoinsiemedirisorsea edibilimediantei
proto- ollitipi i del Web (HTTP, FTP) enei formatipiù utilizzati(HTML, PDF,
e ...), ed il omportamento di un utente he opera una ri er a,
presenta-no tutte le aratteristi he menzionate. In questo ambito i motori di ri er a
di terza generazione arontano il problema on entrandosi sul bisogno
del-l'utente piuttosto he sulla sua query , orendo vari strumenti utilizzabili a
seguito diunrisultatodiuna ri er a. L'obiettivoèquellodifornireun aiuto
nel gestire il grande e non fa ilmente esplorabile insieme dei do umenti
ri-tornato. Esempidiquesto sonoi sistemidisuggerimento oquery re nement
(impiegati ad esempio da Yahoo! e Teoma), di lustering dei risultati (
Vi-vísimo eWisenut), dimapping del risultatosutassonomiepreesistenti ome
Google Dire tory eODP ( Open Do ument Proje t).
Traisistemiproposti,quellopiùpromettentesembrerebbeessereilresult
lustering introdottoinizialmentedaNorthernLight,resopopolareda
per una ri er ain una gerar hia digruppi eti hettati on frasi. Tali
eti het-te devono atturare il tema dei do umenti asso iati allospe i o gruppo.
Questa gerar hia ore una vista omplementare alla tradizionale lista dei
do umenti ordinata per rilevanza. L'utente può sfruttare questa vista
navi-gando i gruppiguidatodalle sue ne essità ed interessi,avendo l'opportunità
di:
1. Estrarre informazionidalle eti hette;
2. Riformulareuna nuovaquery;
3. Restringere l'insiemedei do umenti rilevantis egliendo quelli he
ri a-dono indeterminati gruppi.
Questoappro iorisultaparti olarmenteutilenel asodiquery polisemi he,
dalsigni ato vago e non selettive.
Negli ultimi mesi molti sono i progetti nati attorno a questa idea (vedi
[20,21, 34, 36℄) on l'obiettivo diproporre una valida alternativa al lassi o
browsing del Web he sta divenendo sempre più insu iente per la mole
di informazione on ui l'utente si trova a he fare. L'e a ia di questo
innovativo modello di ri er a verrà dimostrata solo nel tempo, tuttavia le
aspettative in merito sono ottimisti he e sintetizzate nella frase lustering
te hnology is the PageRank of the future [20℄. Sfortunatamentepo he sono
le informazioni disponibili ir a le soluzioni adottate al riguardo in ambito
industriale a ausa dei omprensibili interessi ommer iali. Avere infatti la
te nologia vin ente in fatto dimotori di ri er a signi a possedere un know
how molto redditizioe Google ne è un esempio. D'altraparte molte sono le
soluzioni des ritte an he dettagliatamentein letteratura mala loro e a ia
Un se ondo appro io promettente in fatto di ri er a sul Web è il
ran-king personalizzato dei risultati. L'idea inquesto aso èquelladi ombinare
il tradizionale ranking on informazioni legate alpro lo dell'utente, on
l'o-biettivodiaumentarel'adattabilitàelas alabilitàdelsistemainfunzionedei
bisogni edellepreferenze dell'utente. Collezionandoinformazioni ir a
l'abi-tudinedi hiesegueleri er heèpossibile,almenoteori amente,mostrare un
risultatodiverso a ias unutente, maggiormenteinlinea on lesue abitudini
e desideri, ossia personalizzato. Esempi di questo genere di appro io sono
quelli oerti daGoogle, Yahoo! , AskJeeves e Eurekster . Questi strumenti di
ri er aorono omunque unasoluzioneparzialealproblema delranking
per-sonalizzato inquanto onsentola reazione dipro li on unnumerolimitato
di s elte o omunque impongono agli utenti di mantenere aggiornati i loro
pro li, he omunque rappresentano informazioni riti he e private. Le
so-luzioni proposte inletteratura sonoin entrate prevalentemente nel al olare
il ranking della ollezione dido umentiperogni pro lo disponibile,
soluzio-ne erto non appli abile su larga s ala a ausa dei problemi omputazionali
onnessi a tale operazione (vedi adesempio [18, 19℄).
2.2 Le ban he dati biologi he
Il progresso della biologia mole olare passa per l'a quisizione ostante di
nuovi dati ir a le ma romole ole (DNA o proteine) generati da esperienze
di laboratorio. Tali informazioni vengono ollezionatein ban he dati di due
tipi: primarie ospe ializzate.
•
Le ban he dati primarie ontengono informazioni e annotazioni delle sequen ze nu leotidi he e aminoa idi he, strutture del DNA e proteinee dati sull'espressione di DNAe proteine;
ra - olgono insiemi di dati omogenei dal punto di vista tassonomi o e/o
funzionaledisponibilinelleban hedatiprimariee/oinletteratura,o
de-rivantidavariappro isperimentali,rivistieannotati oninformazioni
di valore aggiunto.
Questedue ategoriesonoa an ate daban he datibibliogra he ontenenti
arti oli ir a studimedi i obiologi i. Neèun esempioPubMed Central [31℄,
he è un ar hivio digitale di pubbli azioni inerenti alle s ienze biologi he
mantenuto dal U.S. National Institute of Healt (NIH). Questo istituto si
pone ome obiettivo quello di atalogare e rendere liberamente a essibile
l'insiemedi pubbli azioniprodotte inambito medi o.
Leban he dati primariesono:
1. LaEMBLDataLibrary delloEuropeanBioinformati sInstitute ( EBI);
2. La GenBank del NationalCenter for Biote hnologyInformation (
NC-BI);
3. La DNA Data Bank of Japan ( DDBJ);
LaEuropean Mole ular BiologyLaboratoryData Library ( EMBL)èlaban a
dati europea ostituita nel 1980 nel laboratorio Europeo di Biologia
Mole- olare di Heidelberg (Germania). La GenBank è la orrispondente ban a
ameri ana ostituita nel 1982 e la DDBJ è la orrispondente giapponese.
Fra le tre ban he dati è stato stipulato un a ordo internazionale per ui il
loro ontenuto èquasidel tutto oin identeinquantogliaggiornamenti
quo-tidianiapportatiin ias una ban adativengonoautomati amentetrasmessi
allealtre due.
Per omprendere megliole dimensioni ditali ollezionibasti pensare he
Figura 2.1: Cres itadelleban hedatiprimarienelperiodo 1982-2006. I valoritotali
si riferis onoal4 marzo2006.
esponenziale dei datiadisposizionedell'utente. L'andamentodal1982a ne
2006èmostratoinFigura2.1. Agliinizidel2006laban adatiEMBL ontava
più di 126 miliardi di nu leotidi per un totale di più di 69 milioni di entry
nei lorodatabase. LaFigura 2.2 mostra ladistribuzione ditaliinformazioni
rispetto agli organisimi. Nel 2005 è stato festeggiato il raggiungimento del
traguardo delle 100 Gigabases 1
rese pubbli amente a essibili dalle ban he
dati prin ipali. Similmente, an he le ban he dati primarie he gestis ono
le informazioni inerenti alle proteine hanno assistito ad una simile res ita
nel tempo. Maggiori informazioniin merito sono riportate più avanti, nella
Sezione 2.2.2.
Le interrogazioni delle ban he dati mirano ad identi are un insieme di
risultati sulla base dispe i he aratteristi he indi atedall'utente mediante
una query formulata nell'opportuno linguaggio, oppure sulla base di
simila-rità on una sequen za o una struttura ampione. Ad esempio una ri hiesta
1
Figura2.2: Distribuzionedelle entry e dei nu leotidi rispetto agliorganismi.
potrebbemirareadottenere unarispostaallaseguentedomanda: Ho
deter-minato una nuova sequenzao un nuova struttura, leban he dati ontengono
qual osa di simile?. Una volta posta la query nel modo opportuno
(me-dianteil linguaggiodi interrogazionesupportato) edeterminato l'insiemedi
sequen zeodistrutturesimiliall'oggetto ampione,ilbiologoènellaposizione
di poter identi aree analizzare le aratteristi he omuni.
A titolo di esempio elen hiamo al une delle domande he un utente
po-trebbevoler sottomettereadun sistemadiri er a, indi ando perprima una
formulagenerale ea seguire un esempio on reto:
•
Laban adati ontienel'informazione hehori hiesto?. Peresempio: Inqualeban adatipossotrovarelesequenzeaminoa idi hedelleal ooldeidrogenasi?;
•
Come posso assemblarele informazioniselezionate dalla ban adati in una forma utile?. Per esempio: Come posso ompilare una lista disequenzedi globine?;
•
Dove posso trovare spe i ielementi di informazione?. Per esempio: Quali ban he dati ontengono la sequenza aminoa idi a della tripsinaÈ evidente ome il su esso di una ban a dati biologi asia strettamente
legato alla possibilità he essa ore di porre in modosempli e tali ri hieste
non hé alla apa ità di integrare quante più informazioni possibili. Al
ri- er atore si hiede omunque diformulareuna query idonea allos opo sulla
base della propria esperienza e know-how. Tuttavia la quantità di
informa-zioni prodotteneltempoesoprattuttolerelazionitradiesse hannoposto (o
stanno nel tempo ponendo) ilbiologonellaposizionedisapere sempremeno
in merito all'obiettivo della sua ri er a. Può essere noto il punto di
parten-za o l'ambito di una ri er a. Probabilmente la risposta he se ne ottiene
potrebbe fa ilmente trasformarsi nel primo passo di un pro esso di ri er a
he prevede più interrogazioni e he pone in lu e più relazioni tra elementi
di quelle inizialmente immaginate dall'utente stesso. È questo andamento
he sta generando nel ri er atore un nuovo bisognodiinformazione he vaa
sostituire la primaria ne essità di onos ere un sempli e dato. Sempre più
spesso è interesse dell'utente voler onos ere non solo la risposta pre isa e
puntuale alla domanda, maan he vedere le relazionidella risposta on altri
ambitio altridati e apire quali siano le possibili direzioni di ri er a su ui
indirizzarsiper migliorareilrisultato stesso.
ArthurLesk[11℄parlandodiquestane essità,evidenziailfatto hean ora
maggiorisforzidevono essere ompiutiinquesta direzione, valeadire a
sup-portodiri er he volteastudiarele orrelazionifraleinformazioni ontenute
indiverseban he dati. Purnon proponendounasoluzione,Leskipotizza he
questa risiedanellosviluppodisistemi he integrinoilpiùpossibilelediverse
fontidiinformazioni,rendendo osìpossibilegenerareuna rispostaperquery
del tipo: Per qualiproteineastruttura nota, oinvolteinpatologiedella
bio-sintesi della purina nell'uomo, esistono delle proteine orrelate nel lievito?.
Unadomandadelgenereponedelle ondizionisudiversipunti: struttura
ban a dati non siasu iente adeterminare larisposta ad essa. Il
ri er ato-re dovrà pro edere progressivamente, ollezionando risultati provenienti da
diversefontie omponendotaliinformazioni. Il pro esso innes ato potrebbe
esserelungosenonsupportatodastrumentiautomati i he vengonoinaiuto
dell'utente. Una strada he in questi anni è stata per orsa è quella dello
sviluppo di appli azioni a supporto proprio di questo pro esso [24℄. L'idea
non è tanto quella di imporre un nuovo modo di ri er are le informazioni,
ma piuttosto quella di venire in ontro all'utente nella gestione dei ussi di
informazione he genera. Spesso l'utente si deve onfrontare on insiemi di
dati di ardinalità molto grandi su ui eseguire determinate operazioni per
apirne le relazioni e le aratteristi he. Il tutto si tradu e in prati a nel
dovere gestire molti le ed eseguire ripetutamente le medesime operazioni
su di essi. Piuttosto he las iare all'ingegno e all'esperienza del biologo la
gestione ditalidati, questi strumentiautomati iorono lapossibilitàdi
or-ganizzare il lavoro da ompiere potendo indi are quali omandi eseguire e
su quali dati. Il biologo pertanto si trova ad operare ad un livello più alto,
dovendo indi are al sistema osa fare, su quali dati operare e in he ordine
pro edere. Sarà l'appli azione agestire le e omandi per onto dell'utente,
il quale pertanto, avrà a he fare solamente on ussi di dati ( work ow).
Come detto, un appro io simile mira a fa ilitare il ompito del biologo il
quale già opera se ondo tale s hema. Una strategia alternativa è quella di
proporre all'utente uno strumento in grado di mettere automati amente in
lu e le orrelazioni tra i risultati di una query in modo da alleviare il
om-pito del biologo il quale non sarà più hiamato a determinare tali relazioni
analizzando i dati manualmente, ma dovrà solamente prendere in
onside-razione iò he il sistema propone, o mette in evidenza, al ne di a ettare
il risultato o migliorare la ri er a. Naturalmente questo tipo di appro io,
tare uno strumento e a e in grado di s oprire e giudi are adeguatamente
le informazioni on ui si haa he fare, inmodo danon far perdere nessuna
informazione importanteper l'utente etale dainfondere inlui lasensazione
di potersi eettivamente daredel sistema.
2.2.1 Il ontenuto delle ban he dati biologi he e la
qua-lità dei dati
Leinformazioni ollezionatenelleban hedati omprendonosiarisultati
speri-mentaligrezzi,siainformazioniaggiuntiveoannotazioni. Laloroa uratezza
è ertamente un fattore riti o dal momento he le omunità s ienti he e
medi he he utilizzanotalidati dipendonodalla qualità degli stessi. La
pro-babilitàdigiungere a on lusionisbagliateètantominorequantopiùbassoè
l'errore asso iato adogni dato. Ilfattore prin ipale he determina laqualità
dei dati è legata all'a uratezza delle te ni he sperimentaliimpiegate. Oggi
la biologia mole olare può ontare, ome è naturale aspettarsi, su te ni he
più so sti ate he non solominimizzano gli errori ma he onsentono an he
un'a elerazione del lavoro diindagine.
Le annotazioni he a ompagnano una sequen za individuata mediante
te ni he di laboratorio omprendono informazioni di diversa natura. Ad
esempio identi ano i ri er atori responsabili, itano le pubbli azioni più
rilevanti, registranoal uni ommentidei ri er atoristessi o fornis ono
olle-gamentiadinformazionipresentiinaltreban he dati. Inoltre possonoessere
presentian he liste disegmentidella sequen za he hanno un signi ato
bio-logi ospe i o. Per esempioregionidi una sequen za di DNA he odi ano
perproteine. Sarebbe un lavoro omplesso quantoprivo disigni ato quello
il lettore interessato alla onsultazione della do umentazione relativa aivari
formatireperibile on-line presso i sitidelle prin ipaliban he dati.
Fino a po o tempo fa, una tipi a entry di una sequen za di DNA
veni-va prodotta da un singolo gruppo di ri er a, he studiava un gene e i suoi
prodottiinmodo oerente. Leannotazionierano basatesudatisperimentali
e venivano s ritte da spe ialisti, pro edimento he, pur ri hiedendo molto
tempo, garantiva un buon livello di a uratezza. Gli attuali progetti di
se-quenziamentodiinterigenomiinve enonorononéla onfermasperimentale
dell'espressione della maggiorpartedei geni putativi,né la aratterizzazione
dei loroprodotti. I uratoridelle ban he dati, basano leproprieannotazioni
sull'analisi delle sequen ze uni amente per mezzo di programmi informati i.
Questo introdu e un fattore riti o inrelazione alla qualità degli stessi.
Leannotazionirappresentanolapartepiù deboledell'impresagenomi ae
l'automazione del pro essodiannotazione èpossibilesoloinmisura limitata
ed espone al ris hio di introdurre informazioni non veritiere ir a una
se-quenza. L'importanzadi annotazioni orrette non deve essere sottostimata.
Èstatodettoinfatti he glierrorinelleassegnazionidei genivizianol'elevata
qualità degli stessi dati di sequen za (vedi [11℄).
La res itadei datie della onos enza suigenomifavorirà un in remento
della qualità delle annotazioniparallelamenteadun in remento
dell'a ura-tezza dei metodistatisti ie algoritmi iimpiegati perl'annotazione
automa-ti a. Questoinnes herà inevitabilmenteunlavoro diriannotazionedellevo i
già ontenute nelle ban he dati. Tale pro esso non può he essere
valuta-to in modo positivo e determinerà (se già non è a aduto) la on ezione di
ban he dati dinami he . Il biologo sarà ostretto ad abbandonare la
tran-quillizzanteidea diunaban adati stabile, omposta daelementi orrettigià
2.2.2 La ban a dati UNIPROT
Il motorediri er asviluppatoinambitodiquesta tesiopera sudatiinerenti
alle proteine ontenuti nella ban a dati UNIPROT. Come sarà spiegato più
avanti, questa s elta è stata fatta in virtù della de nizione di un aso di
studio. Infuturo èauspi abile he venga estesoil supporto an he verso altre
ban hedatidiinteresse, omeadesempioGenBank. Inquestasezionesivuol
dare qual he informazione ir a l'evoluzione della ban a dati UNIPROT, a
partire dalla sua storia.
Nel 1965 apparve la prima pubbli azione dell'Atlante delle sequenze e
strutture protei he di MargaretDayho. Esso onteneva informazioni su 65
proteine. In seguito furono redatte altre versioni dell'atlante no ad
arriva-re al 1978, anno in ui vennero des ritte 1660 proteine. Quando nel 1983
Dayho morì, l'atlante si era evoluto in una ban a dati per proteine
ono-s iuta on il nome di Protein Identi ation Resour e (PIR) ospitata presso
la National Biomedi al Resear h Foundation (NBRF).
Nel 1985, AmosBairo h,impegnato nello sviluppo diun pa hetto
soft-ware (PC/Gene) per l'analisi delle sequen ze protei he (nell'ambito del suo
dottorato), ebbe a he fare on al une arenze ed omissioninella ban a dati
PIR.Nonsoloidatierano odi atiinunformatodi iledagestire
median-te programma, ma erano del tutto arenti di qualsiasi riferimento ad altre
informazioni, omeadesempiodellasequen zanu leotidi agenitri e
ontenu-ta nel database relativo al DNA, annotazioni delle funzioni svolte, lo azioni
sub ellulari e altre importanti aratteristi he asso iate alla proteina
studia-ta. Bairo h manifestò le sue perplessità ai uratori di PIR ma non ebbe
su esso. Fu osì he ne sviluppò una versione personalizzata adottando il
formato del database di sequen ze nu leotidi he dell'EMBL ed introdu endo
arri -Swiss-Prot . Su essivamenteBairo h ontattò la EMBL persapere seerano
interessati nella distribuzione del suo database e se volevano ollaborare al
suo mantenimento. La EMBL a ettò, dando vita osì alla ollaborazione
on quello he sarebbe divenuto lo Swiss-Prot Gorup a Ginevra. Per molti
anni le sequen ze protei he vennero inviatedall'EMBL direttamente al
grup-po di Bairo h, i quali provvidero alla annotazione delle stesse, dando vita
osì al primo database di proteine urato a mano e di alta qualità.
Que-sto venne poi distribuito impiegando i supporti resi disponibili nel tempo:
nastri, oppy, CD, no ad arrivare al Web. In ne, nel 1993 prese vita il
sito dell'ExPASy (Expert Protein Analisys System) [37℄. A metà degli anni
novanta,a ausa dell'in remento dei dati prodotti a seguitodei progetti
ge-nomi i, i uratori di Swiss-Prot in ontrarono il problema di non rius ire ad
annotare nei tempi ri hiesti tutte le sequen ze protei he s operte. Tuttavia
era evidentel'importanzadi rendere disponibilile nuovesequen ze nel minor
tempopossibile. Con la ollaborazione dell'EBI, na quenel 1996il progetto
TrEMBL (Translation of EMBLnu leotidessequen e database) he miraad
annotare automati amentelenuovesequen zemediantel'ausiliodiopportuni
programmi. Taliannotazionivengonosu essivamenteri ontrollate
manual-mente ed arri hite, e le entry osì orrette vengono quindi inserite nella
ollezione Swiss-Prot . Dal 1996 all'iniziodel 2005, Swiss-Prot è res iuto da
83milaentry a170 mila. NelsolitoperiodoTrEMBL è res iuto da86mila
entry a 1.5 milioni.
Nel 2003 in ne, il gruppo uratore della ban a dati PIR e i uratori di
Swiss-Prot/TrEMBL hanno dato vita alla ban a dati uni ata UNIPROT
(UniversalProteinknowledgebase onsortium),adoggiilprin ipaledatabase
2.3 Un nuovo appro io alle ban he dati
bio-logi he
T he
BioPrompt-box èilnomedelnuovomotorediri er aperban hedati
bio-logi he sviluppatoinquesta tesi, he hal'ambizione diintrodurre un diverso
paradigmadiri er ain ampobiologi o. Tresonoglielementiinnovativi he
il sistema propone:
1. Unsistemaingradodimettereinlu eautomati amenterelazionie
pos-sibiliinterpretazionideirisultatiottenutiafrontediunainterrogazione
medianteil lustering dei risultatistessi;
2. Integrazione dei dati provenienti dalle ban he dati biologi he on le
informazioniderivate datassonomie ed ontologie urate daesperti;
3. Possibilitàper l'utente diinstaurare una ri er a basata sudue passi:
(a) Lettura e analisi dei feedba k generati mediante lustering dei
risultatiprodotti dalla ri er a;
(b) Ra namentodellaquery medianteselezionedeifeedba k generati;
il tuttosupportatodaun'interfa iasu ientemente omodaed
intui-tiva.
Ilprogettoèmaturatodall'analisideglistrumentiesistentiedalla
valuta-zione diquelle he sonoleemergentine essitàdegli utenti/biologi. Ri er are
nonbasta,o orrefornireun aiutoagliutentipermigliorarel'interpretazione
dei dati e/o a nare le lorori er he osì dasoddisfare al meglio ilbisogno
he si ela dietro laloroquery .
quelle diappartenenza. Questopone pertantouno s enariodiversodaquello
Web dove l'informazione è s arsamente strutturata, la ollezione dei
do u-mentièprati amenteuni a(non isonopiù ban he datimalasola ollezione
di pagine Web) ed i riferimenti presenti nei do umenti sono verso altri
do- umenti del solito tipo ( link ad altre pagine Web). I due ontesti pertanto
sono diversi, mal'esperienzadel Web puòessere e a ementeimpiegataper
sviluppare un sistema diri er a migliorean he in ambito biologi o.
Ilfattodiavere datistrutturatièsi uramenteun vantaggioper
ompren-dere le relazioni tra do umenti, osì ome l'avere riferimenti ad ontologie e
tassonomie . Sonotuttistrumentiper apire om'èorganizzatal'informazione
equalirelazionisussistano tra idati. L'obiettivoèquellodirius irea reare
un tool per i biologi in grado di mostrare i legami e le relazioni nas oste
tra elementi quali sequen ze protei he o di DNA, des ritte dalle
annotazio-ni he a ompagnano ogni sequen za. Si vuol reare un sistema in grado di
sempli are quello he è l'attuale modo di pro edere del ri er atore basato
sull'analisie sulla orrelazione manuale delle entry ritornate dauna
inter-rogazione ad una ban a dati. Le meta-informazioni fornite a orredo delle
sequen zevengonoimpiegateda
T he
BioPrompt-box per lusterizzare i
risulta-tiottenuti. Ognigruppo( luster)radunainsétutteleentry he ondividono
una medesima aratteristi ades rittadaquella he ostituis el'eti hetta del
gruppo stesso. Per tale s opo vengono impiegate le diverse fonti di dati a
disposizione.
Nei sistemi tradizionali, la presenza di più ban he dati rappresenta una
fonte di maggiore informazione ma ontestualmente an he di maggiore
di-spersività per l'utente il quale è hiamato a ripetere la propria ri er a più
volte, onstrumentidiversi,perottenereinformazioniaggiuntive ir ailtema
della sua ri er a.
T he
BioPrompt-box vuolgestire questa situazione er ando
te suggerimenti o informazioni aggiuntive attinenti al risultato determinato
dalla query usando le informazioni provenienti da più ban he dati, osì da
aumentare la sua per ezione della risposta stessa (ad esempio rendendolo
onsapevole delle relazioni tra le entry ritornate) e di renderlo in grado di
ra nare opportunamentela sua ri er a verso una direzione migliore.
Raggruppare i do umenti in luster omporta la s da della generazione
di eti hette signi ative da asso iare ad ogni gruppo he devono essere tali
da des rivere in maniera oin isa ed e a e la proprietà omune dei
do u-menti radunati. Per tale ompito
T he
BioPrompt-box impiega estesamente
Gene Ontology mediantelaquale siè ingradodimostrare qualisonole
fun-zioni mole olari ed i pro essi biologi i aratteristi i delle entry ritornate, in
quale omponente ellulare avvengono tali pro essi, ome le entry si
distri-buis ono sutaliinformazioniequalirelazionisussistono tradiesse. An he la
tassonomia relativaagliorganismisi rivelaparti olarmenteutile allos opo.
Ogni vista dell'insieme dei risultati sottintende un dierente riterio di
similarità sulla base del quale vengono reati i gruppi ele relative eti hette.
In relazione a questo, la novità introdotta è quella di dare l'opportunità
all'utentedipoteruniretraloroelementidiviste diverse osì dafaravanzare
il pro esso di ri er a in una direzione migliore per l'utente. Ad esempio il
ri er atore potrebbe ssare una spe ie o uno spe i o organismo assieme
ad una spe i a funzione mole olare osì da determinare tutte le proteine
orrispondenti a taliparametri perpoianalizzare i diversi pro essi biologi i
oinvolti. Ri onsideriamoad esempiolapossibiledomanda he un utente di
una base di dati biologi asi potrebbe porre: Per quali proteine a struttura
nota, oinvolte in patologie della biosintesi della purina nell'uomo, esistono
delle proteine orrelate nel lievito?. Come notato in pre edenza (siveda la
sezione 2.2), una domanda del generepone delle ondizionisu diversi punti:
•
Funzione spe i a;•
Ri onos imentodella orrelazione;•
Correlazione on lapatologia;•
Spe ie de nita.T he
BioPrompt-box onsente, allo stato attuale, di intraprendere una
ri- er a ssando la funzione desiderata e la spe ie. In futuro è auspi abile he
onsenta an he di ssare la ondizione sulla struttura mole olare. Queste
possibilità permettono osì di dare risposta alla query del biologo, il quale,
ad esempio, potrebbe ri er are inizialmente tutte le proteine asso iate alla
biosintesi della purina on una query del tipo purin biosynthesis.
Su es-sivamente, analizzando i luster relativi alle funzioni mole olari svolte dalle
entry ritornate e agli organismi oinvolti, il biologo può ra nare la ri er a
ponendo dei vin oli sulla funzione e sull'organismo di interesse (in questo
aso Homo Sapiens). La lista dientry risultante sarà un ra namento della
pre edente ontenente le sole proteine on le aratteristi he volute. Di
que-ste, l'utente potrà onsiderare solamente quelle relative allievito sfruttando
la lusterizzazione eseguita in base alla tassonomia degli organismi itati,
ottenendo quindi la risposta dalui er ata.
Attualmente, ome spiegato più avanti, è stata presa in onsiderazione a
titolodistudio solamentela ban adati protei aUNIPROT assieme aGene
Ontology per avere una des rizione sistemati a delle relazioni he sussistono
tra le varie entry .
L'implementazione del sistema si è on entrata an he su aspetti di
usa-bilità dello stesso al ne di sviluppare un'interfa ia quanto più intuitiva
pro esso di ra namento della ri er ain quanto onsente on po he,
sempli- i operazionidi impostare delle nuove ondizioni di ri er a o di fo alizzarla
solo su uno spe i o sottoinsieme di risultati. Oltre he a urare aspetti
implementativi, ome l'indi izzazione della ollezione onsiderata e lo
svi-luppo dell'appli azione Web, l'attenzione del progetto è stata rivolta an he
all'analisi e all'implementazione di te ni he mediante le quali generare
vi-ste formate da eti hette semanti amente rilevanti per l'utente, in modo da
non sommergerlo on troppe informazioni, ma al tempo stesso, in grado di
fornirgli feedba k interessanti e utili per la omprensione del risultato e il
ra namentodella query . Questoèun aspetto ru ialedell'interosistema ed
è una parte su ui è possibile intervenire estesamente al ne dimigliorare il
risultato prodotto.
L'idea di sviluppare un simile strumento di ri er a nas e
dall'esperien-za e dal dialogo on i biologi he avvertono la ne essità di un appro io
più potente rispetto a quellooerto n ora dagli strumenti tradizionali. Ad
oggi tali strumenti permettono di interrogare le ban he dati in maniera
si-stemati a impiegando un linguaggio di query booleano, restituendo una
li-sta di risultati e delegando al biologo il ompito di interpretare la risposta
fornita.
T he
BioPrompt-box per ontro er a di sfruttare al meglio le
meta-informazioni he a ompagnano una sequen za nu leotidi a o aminoa idi a,
per lusterizzare i do umenti ritornati ome risposta in gruppi des ritti da
eti hette signi ative ed intellegibili, on l'obiettivo di mettere in evidenza
le relazionipiù importanti he sussistono tra diessi.
Lo sviluppo di un nuovo sistema non può pres indere dall'analisi degli
strumenti esistenti e dalla omprensione di quelli he sono i loro punti di
forza oltre he quelli di debolezza. Tipi amente i motori di ri er a oerti
dagli enti he operanoin ampobioinformati o, omeEntrez dell'NCBI [22℄
risul-qual osa di similea quello he hoottenuto tramiteun mio studio?. In
gene-revengonoimpiegatialgoritmi omeBLAST ( Basi Lo al AlignmentSear h
Tool)oFASTA( FAST Alignement)perottenereun elen odisequen ze
omo-loghe aquelladiinput.
T he
BioPrompt-box impiegaquesto utileme anismo
al nediorireall'utenteunostrumentodianalisiinpiùnon héun ulteriore
puntodi partenza del pro esso diri er a. A partireda una sequenza nota il
ri er atore può determinare tutte le sequen ze omologhe, vedere le relazioni
esistenti tra di esse e pro edere on il ra namento della query mediante i
feedba k generati.
Il motoredi ri er asviluppato èdisponibile on-line all'indirizzo:
http://brie.di.unipi.it:8080/BioPrompt-box
A seguire vengono trattati i diversi dettagli implementativi e le s elte
fatteaivarilivellidel sistema. GeneOntology riveste un ruolodeterminante
nella lusterizzazione dei risultati e nella generazione delle eti hette ed il
apitolo3 ne prende in esamegli aspetti aratteristi i emostra in he modo
taleontologiaèstataimpiegatanelsistema. L'indi izzazionedeidatieilloro
a essovienegestitomediantelibrerieopensour e di uine vienefornitauna
Gene Ontology
Un'ontologia è il tentativo di formulare uno s hema on ettuale esaustivo
e rigoroso nell'ambito di un dato dominio di onos enza; si tratta
general-mente diuna struttura dati gerar hi a he ontiene tutte leentità rilevanti,
le relazioni esistenti fra di esse, le regole, gli assiomi, ed i vin oli spe i i
del dominio. Nel
1998
nas e Gene Ontology [38℄, progetto voluto e portato avanti dapiù enti, on l'obiettivodi fornire nel orso del tempo unades ri-zione onsistente dei dati relativi ai geni atalogati in diverse ban he dati.
Lostudiodiproteineegeni ondottodapiùlaboratoridiri er ahagenerato
e sta generando molidi dati sempre più grandi. La naturale onseguenz a è
statalanas itadimoltepli iformatiperlarappresentazionediinformazioni,
talvoltaidenti he, in ban he dati diverse o gestitedaorganizzazionidiverse.
Coltempoognunoha odi atoleinformazioni hegravitanoattornoaduna
sequen za biologi a nei formati ritenuti più opportuni vista la man anza di
uno standard. Gene Ontology è un punto di riferimento per queste ban he
dati, in grado diorireuna des rizione uni ata diquelle he sono le
arat-teristi hedellesequen ze atalogate. Nonsitrattadiun formatostandard dei
dati né diuna nuovaban adati he miraaradunare inséi diversi database.
Gene Ontology è l'implementazione diun'ontologia on l'obiettivodi
3.1 Struttura di Gene Ontology
Gene Ontology viene distribuito sotto forma di database relazionale le ui
relazionides rivonoleentitàdell'ontologiaelerelazionitradiesse. L'insieme
dei on etti rea un Dire ted A y li Graph (DAG). Il grafo si ompone di
tre partiprin ipali hevannosottoilnomedi: Mole ular Fun ion,Biologi al
Pro ess e Cellular Component. Questi sono i tre ambiti prin ipali di Gene
Ontology organizzatialorovoltasottoformadiDAG.GeneOntology èquindi
l'unione di queste strutture in una struttura più grande, generata mediante
l'introduzione diun nodo ttizioi ui gli sono inodi radi e dei tre DAG.
I on etti hede nis onol'ontologiavengono hiamatitermini 1
nelgergo
di Gene Ontology . Ogni nodo del grafo viene eti hettato on un termine
he ne de nis e la semanti a. Gliar hi del grafo des rivono le relazioni he
sussistono tra due termini.
Per omprendereilsigni atodeitreambitiin uisisuddividel'ontologia,
sipuòdire heungeneounsuoprodottosvolgeunaopiùfunzionimole olari
ed èutilizzatoinuno opiù pro essi biologi i;può inoltreessere asso iato ad
uno opiù omponenti ellulari.
Consideriamoin maggiordettaglioqueste tre sotto-ontologie.
Mole ular Fun tion
Des rive attività, omeattività atalizzatri io diasso iazione,a livello
mo-le olare. I termini di questa ontologia rappresentano attività piuttosto he
entità (mole ole o omplessi) he svolgono l'azione,senza indi arequando o
dove, oin quale ontesto, l'azioneavviene.
1
Biologi al Pro ess
Un pro esso biologi oèuna serie dieventiportati a terminedauna sequen
-za ordinata di funzioni mole olari. In generale iò he distingue una
singo-la funzione mole olare da un intero pro esso biologi o è he quest'ultimo è
ostituitoda una serie dipassi insu essione.
Cellular Component
Un omponente ellulare è, ome suggeri se il nome, il omponente di una
ellulain uiavvieneilpro esso biologi oolafunzionemole olaredes ritta.
3.2 Tipi di relazioni
Esistono due relazioni prin ipali tra i termini: is_a e part_of. La prima
relazione indi a un rapporto padre- glio tra termini. Indi a he un termine
è unasotto lasse del padre;èun on etto più spe i o. Danotare he is_a
non signi a istanza di . In Gene Ontology non esistono infatti istanze, ma
solo lassi di on etti. I do umenti ontenuti nelle diverse ban he dati he
riferis ono i termini in Gene Ontology sono le istanze. Larelazione part_of
è inve e più omplessa. Ci sono quattro livelli di restrizioni he possono
aratterizzare questa relazione, omemostrato inFigura 3.1.
Il primo tipo non ha restrizioni ed è la relazione più debole. Viene
sem-pli ementedi hiarato he ilterminepadrepotrebbeavereil glio omeparte
e he il gliopotrebbeesserepartedel terminepadre. Il se ondotipo,
ne es-sarily is_part ,indi a he iltermine glio,quando o orre,èpartedel padre.
Questo signi a he se il termine glio o orre, questo è si uramente parte
Figura 3.1: Le quattro restrizioni della relazione part_of. Le fre e indi ano he
l'elemento dipartenzadeve ne essariamenteavere l'altro ome parte.
Laterza relazione, ne essarily has_part , èl'inversa dellarelazione
pre e-dente; laddove il termine padre esiste, esso ha il termine glio ome parte,
ma il glio non è ne essariamente parte del padre. Peresempio il nu leo ha
sempre ome parte il romosoma, ma il romosoma non è ne essariamente
parte del nu leo .
La quarta e ultima relazione è la più forte e ombina inseme le relazioni
due etre, is_part ehas_part . Adesempioogninu leo hasempre omeparte
la membrana nu leare evi eversa. Sono due elementi he non posso esistere
separatamente.
Larelazione part_of utilizzata solitamenteinGene Ontology è la
se on-da, ne essarily is_part . La primarelazione e laterza non vengonousate dal
momento he esse potrebbero violare la true path rule. Questaregola
stabi-lis e he tutti i per orsi daun termine glio atutti i suoi possibiliantenati
devono essere sempre veri. Pertantonon è possibile utilizzare relazioni he
Come la relazione is_a, part_of è transitiva per ui se un termine A is
part_of B e B is part_of CalloraA is part_of C.
Note implementatite relative a Gene Ontology
Come aermatoin pre edenza, Gene Ontology viene distribuito sotto forma
di database relazionale. Al momentodella s rittura diquesto do umento,il
DBMS u ialmentesupportato èMySQL. Lerelazioniprin ipalisono term ,
term2term e graph_path . La prima elen a tutti i terminidi Gene Ontology
he ostituis onoinodidel DAG, lase onda des rive lerelazionitratermini
(gliar hi)mentre laterza èla hiusura transitivaeri essivadel grafo.
Que-st'ultima è ertamente una relazione utile dal momento he elen a tutte e
sole le oppiediterminiinrelazionetra loroassiemealladistanzainnumero
di ar hi he sussiste tra il termine padre e il termine glio. Se tra due
ter-miniesistono più per orsi (ri ordiamo he Gene Ontology è un DAG)allora
esisterannopiù righeinquestatabella, unaperogni per orso. Asupportodi
queste relazionine vengono fornite altre ontenentidati aggiuntivi, omead
esempioterm_de nition in uiperogni terminevieneriportatala
des rizio-ne ompleta del signi ato del termine stesso. Nella relazione term infatti
si trova solamenteil nome del termine ostituitodauna breve eti hetta. La
relazione term_de nition apporta quindi una maggiore informazione, utile
per lagenerazione di un risultatopiù omprensibile perl'utente.
3.3 Utilizz o di Gene Ontology nella
lusteriz-zazione dei risultati
orga-dati èpossibiledes rivere lasemanti a deidati stessiinun modopiù pre iso
rispettoate ni heautomati heditextmining. L'e a iadell'ontologia
deri-vadalfatto heido umentisonoannotatiamanodaesperti, iqualipossono
valutareattentamenteilsigni atodiundo umento. Tantopiùle
annotazio-ni sarannori he epre ise, tanto meglioverrà rappresentata lasemanti a di
un do umento. Il prezzodapagareperottenerequesto risultatoèuno sforzo
notevole da parte degli esperti per annotare i do umenti o per mantenere
le annotazioni esistenti. Tuttavia, mentre un appro io simile è prati abile
solo in pi ola misura per orpus molto estesi ome il Web, nel aso delle
ban he dati biologi he (an he se in ontinua res ita) l'impresa risulta
es-sere fattibile. Il lavoro di annotazione dei do umenti provenienti da diverse
ban he dati è un'attività probabilmente senza termine sia per hé
rimango-no, allostato attuale,molti do umenti prividi riferimenti aGene Ontology ,
sia per hé nel tempo l'ontologia stessa ambia, orendo una maggiore
gam-ma di on etti referenziabili. An he le annotazioni già fatte possono essere
modi ate mediante un lavoro direvisione al ne di orreggere o migliorare
la des rizione della semanti a del do umento. Nonostante questa ontinua
evoluzione, è possibile sfruttare il lavoro già fatto al ne di sviluppare uno
strumento di ri er a in grado di mostrare all'utente maggiori informazioni
ir a il dominio dei dati di suo interesse. È possibile far questo sfruttando
proprio le annotazioni he a ompagnano i do umenti ritornati a fronte di
una query sottoposta dall'utente.
Mediante un'opportuna indi izzazione dei dati è possibile mostrare
al-l'utente tutti i do umenti attinenti ad un insieme di parole hiave. Come
nel aso del Web, è di fondamentale importanza he i do umenti re uperati
siano ordinati se ondo la presunta attinenza allaquery sottoposta osì he i
trovate, l'utentepotrà onsideraresolamenteleprime ora nare iparametri
di ri er a. Un sistema he mostri informazioni ontestuali alla ri er a
in-trapresa aiuta l'utente proprio nella fase di miglioramento dei parametri di
ri er a. Spesso hi inizia una ri er a lofa on query troppogeneri he o
ine-satte. Forse deve a quisire le prime nozioni ir a un argomento per ui non
onos ean oraitermini orrettidautilizzareoquellimaggiormente
dis rimi-nanti. Sfruttando i riferimenti verso Gene Ontology dei primi n top-ranked
do uments 2
è possibile mostrare un insieme di on etti legati alla ri er a
intrapresa. Tali informazioni saranno tanto più signi ative e informative
quanto più i do umenti saranno annotati in modo a urato. Dal momento
he Gene Ontology raduna in sé lassi di on etti organizzati sotto forma
di DAG in ui si possono distinguere termini padri e termini gli, an he le
informazioni ri avate daitop ranked do uments saranno mostrate all'utente
in modo gerar hi o. In generale iò he viene visualizzato dal sistema di
ri- er a sono proprioi nomi dei termini itatidai do umentipiù rilevanti, osì
ome appaiono in Gene Ontology , assieme alla loro des rizione. Il sistema
utilizzaindiversimoditaliriferimenti,al nedimostrareall'utente
solamen-te le informazioni più interessanti. Questa selezione si rende ne essaria dal
momento he per essere realmente utilizzabile, un sistema di suggerimenti
automati ideve orirepo hiriferimentimamoltosigni ativi. Il ris hio
in-fatti è quello di mostrare un'e essiva quantitàdi informazioni he vengono
per epite dall'utente ome non interessanti otroppeperessere onsultate. I
suggerimenti mostrati hanno l'obiettivo di fa ilitare la lettura dei molti
ri-sultati ottenuti dalla ri er a. È essenziale quindi he la loro onsultazione
non sia onsideratadall'utentetanto di oltosaquanto la onsultazione dei
singoli risultati.
Un sempli e mododi organizzare i riferimenti a Gene Ontology è quello
di raggruppare tutti i do umenti he riferis ono il medesimo termine in un
2
insiemeeti hettato onilnomedel terminestesso. An he sesempli e
on et-tualmente,questaoperazioneries eaduniredo umentisimilinelmedesimo
gruppo. Il riteriodisimilaritàinquesto asoède nitodalfatto he due
en-try annotate onilmedesimoriferimentoall'ontologiasonorelativeaproteine
he svolgonolamedesimafunzionemole olare,oppure hesono oinvolte nel
medesimo pro esso biologi oo he sono situate nel solito omponente
ellu-lare. L'insieme di annotazioni ontenute nelle entry ostituis ono un modo
e a e e sistemati o per des rivere la proteina rappresentata, he pertanto
possono essere impiegatefa ilmente per raggrupparei do umenti in insiemi
he ondividonolamedesimainformazione. Mediantequesto
raggruppamen-to l'utente ri eve un'immediata per ezione di quelle he sono le entità he
ri adono sotto un determinato on etto e quanto quel on etto è rilevante.
L'importanza di un on etto è determinata dalla dimensione del gruppo di
do umentia lui asso iato. Vari ordato he ilraggruppamento è operato su
uninsiemedido umentigiàrilevantirispettoallaquery sottoposta,rilevanza
determinatasullabasedelmodello on uivengonorappresentatiido umenti
emedianteilqualevienestabilitaunamisuradisimilaritàtraogni
do umen-to e la query stessa (si veda il modello vettoriale spiegato nel Capitolo 4).
Pertantosemoltido umentidiquestoinsiemeriferis onountermineinGene
Ontology , questo hapiù probabilitàdiessere importante he non un termine
s arsamente riferito. Sulla base della dimensione viene operato il ranking 3
degli stessi gruppi. I gruppi di dimensione maggiore vengono mostrati per
primi seguitidaquellididimensioneminore. I terminiriferitidaido umenti
hanno generalmente un signi ato spe i o . Gene Ontology è ostituito in
buona parte da nodi o termini asso iati a on etti piuttosto generali e non
molto informativi. Esempi e latanti sono i terminimole ular_fun tion,
bio-logi al_pro ess e ellular_ omponent olastessa radi e eti hettata ome all.
Questisononodiradi edi ategoriedi on ettimoltoampieehannolos opo
di onnettere eraggruppare tra loroi terminisottostanti. Sono inodipiù in
profondità e le foglie a ra hiudere la vera informazione. I do umenti delle
ban he dati tipi amente riferis ono termini maggiormente signi ativi, per
ui ilranking dei gruppisullabase dellasoladimensioneporta omunquead
elen areperprimiiterminipiùinformativi 4
. Seido umentiriferisseroan he
terminigeneri i,lasoladimensione nonsarebbe piùsu ienteagarantirela
bontà di un termine. Potrebbe infatti a adere he molti dei do umenti
re- uperatiriferis anountermines arsamenteinformativo he, di onseguenz a,
verrebbe proposto tra i primi suggerimenti rendendo il sistema meno
e - a e nella guida dell'utente. Il problema in questo aso sarebbe analogo al
ranking per importanza delle parole itatein un orpus dido umenti s ritti
in linguaggio naturale. Non sarebbe su iente elen are per primi i termini
he o orronopiùfrequentemente. Sirenderebbene essariomodularequesta
informazione onuna valutazione diquantolospe i o terminesiarilevante
rispetto a tutta la ollezione dei do umenti. Così, sead esempioun termine
è molto ripetuto, ome potrebbe a adere nel aso di un arti olo o di una
ongiunzione,questorisulterebbepo orilevanterispettoall'intero orpusper
il fatto he è un termineutilizzatonella maggioranza dei do umenti 5
.
Estrarredaido umentiritornatiiriferimentiaGeneOntology emostrare
lalorodistribuzionesutalivalori,produ eunalista dieti hettenon
gerar hi- a. Ogni eti hetta avrà asso iato almeno un do umento ed ogni do umento
potrà ri adere sotto una o più eti hette. I termini riferiti possono essere in
relazione tra di loro all'interno dell'ontologia. Quindi, per migliorare il
ri-sultato di questo raggruppamento,il sistema,una volta determinatala lista
dei termini, provvede a riorganizzarli gerar hi amente se ondo la relazione
4
È ne essario ri ordare he ogni gruppo viene des ritto on un termine di Gene
Ontology.
5
Figura 3.2: Risultatodel lusteringdei do umenti ritornatiper laqueryopsin nella
vista GOTerms.
is_a. Il bene io è quello di restituire all'utente una gerar hia di
on et-ti dai più generali ai più spe i i, si uramente più sempli e da onsultare.
Tale struttura viene mostrata on una vista ad albero 6
, per ui iò he
l'u-tente vede per primo è il livello più super iale della gerar hia, ostituito
generalmentedapo he eti hette. Questo miglioralaper ezione del risultato
in quantotalieti hette sonorapidamente onsultabili ed esprimono on etti
generi i. Rimane poi la possibilità di onsiderare un'eti hetta in maggiore
dettaglioaprendo ilnodonellavisualizzazione, ottenendo osìinformazioni
più spe i he e sempre attinenti ai primi do umenti più signi ativi. Per
in rementare ulteriormente la omprensione del risultato, il primo livello di
eti hette viene raggruppato in base ai tre ambiti di Gene Ontology ovvero
mole ular fun tion, ellular omponent e biologi al pro ess. Questo ulteriore
6
livello,introdottoarti ialmente, onsentealri er atoredifo alizzare
imme-diatamentel'attenzionesui on ettiperluipiù interessanti. Adesempioseè
interessato a apirequalifunzionimole olarisono svolte dadeterminate
pro-teine, potrà porre l'attenzione sulle eti hette del gruppo mole ular fun tion
ignorando le altre.
Un esempio è riportati in Figura 3.2, dove viene mostrato il risultato
del lustering dei do umenti ritornati per la query opsin, una proteina
fotore ettri e molto omune. Come si può notare i gruppi sono suddivisi
nei tre ambiti di Gene Ontology e le eti hette generate sono organizzate
gerar hi amentese ondo la relazione is_a.
Permaggioridettaglisull'implementazionedellefunzioniasupportodella
generazione diquesti risultatisi rimandaal apitolo 6.
3.3.1 Il metodo delle Upward Paths
Nella pre edente sezione è stato mostrato un sempli e modo per sfruttare i
riferimentiaGeneOntology ontenutineido umenti. Sitratta
essenzialmen-te diun raggruppamentoper termini omuni. Per ogni termine itato viene
reato un gruppoeti hettato on iltermine stesso inbase alla de nizionein
Gene Ontology ontenentetutti i do umenti on tale riferimento.
Sebbene il metodo sia sempli e da implementare e porti ad un risultato
apprezzabile,si ha he ido umenti vengono raggruppatinello stesso gruppo
solo qualora ondividano la stessa informazione. In altre parole non
vie-ne de nito un vero e proprio riterio di similarità, ma viene sempli emente
aermato he due do umenti possono appartenere al solito gruppo solo se
ontengono lamedesimainformazione. Èpossibile utilizzarean orauna
vol-taGeneOntologyperrealizzareunmetodopiùso sti atoal nediavvi inare
do-an ora onsiderato l'insieme dei termini in Gene Ontology riferitidai primi
n
do umentiritenutimigliori 7. Apartire daogniterminenell'insieme,viene
per orso all'indietro Gene Ontology mediante un algoritmo di visita di un
grafo (ad esempio depth rst). L'attraversamento ba kward del DAG viene
eseguito perun numero ssato dipassi. Durantel'attraversamento viene
te-nutatra iadei nodivisitatiedellelororelazioni osì dari reare, altermine
dell'algoritmo, una parte del grafo diGene Ontology relativoai soli termini
itati. Ogni termine visitato viene quindi onsiderato eti hetta di un
grup-po, ed ogni do umento viene asso iato a tanti gruppi quanti sono i termini
di Gene Ontology he riferis e. La struttura dati risultante sarà an ora un
DAG ostituitodaterminidiGeneOntologyriferitidirettamentedaiprimi
n
do umentioppuredatermini hesonoantenatidiquesti,organizzatitraloroin base alla relazione is_a. Adogni nodo/eti hetta sarannoasso iati tutti i
do umenti he riferis onodirettamentelospe i otermineoppuretuttii
do- umentiasso iati adogni nodoraggiungibile. All'utenteverrà mostratauna
struttura ad albero simile alla pre edente (vedi Figura 3.2) in ui le prime
eti hette sono i nodisu ui l'attraversamentosi è arrestato, e le eti hette ai
livelli sottostanti sono date dai nodi raggiungibili a partire da questi.
L'al-bero mostratorappresenta un DAG per ui potrà avere sottoalberiripetuti.
Una similestruttura unirà inuno stesso insiemetuttii do umenti he
riferi-s ono il medesimo termine in Gene Ontology (analogamentea quanto fatto
in pre edenza). Tuttavia i do umenti relativi a nodi/gruppi distinti ma
si-mili,inquantoriferis onoterminivi ininell'ontologia,verranno raggruppati
daun possibilenodopadre,alquale verranno asso iati tuttiido umentidei
gli. L'eti hetta del nodo padre avrà un signi ato più generale in grado
di des rivere tutti gli insiemi dei do umenti. Questo pertanto determinerà
un avvi inamentodei do umenti simili. I do umenti asso iati a gruppi
mol-to diversi tra loro possono essere asso iati solo da nodi padre a livelli più
super iali nel DAG, dal momento he solo un on etto molto ampio e
ge-neri o può des rivere il signi ato di gruppi eterogenei. Tuttavia le Upward
Path vengono generate per orrendo Gene Ontology per un numero di
pas-si su ientemente pi olo 8
da a orpare in un uni o gruppo nodi (e quindi
do umenti) molto simili tra loro. Ne onsegue he i do umenti asso iati a
gruppi piuttosto diversi tra loronon vengonoavvi inati.
Ilnumerodipassi on ui risalirel'ontologiarappresentaun trade o tra
prestazioni, qualitàdel lustering e numerodieti hette prodotte. Un
nume-ro molto altodi passi farà si he l'attraversamento del grafo pro eda no al
raggiungimento dei nodipiù super iali di GeneOntology . Questo di persé
allungaitempidi ompletamentodell'algoritmo. Diogninodovisitato sene
onsiderano ipadrie sipro ede onla loroesplorazione. Quindipiù sirisale
l'ontologia,piùnodisidovranno onsiderare. L'ontologia,essend o
struttura-ta sotto formadi DAG, presenterà una maggioredensità dinodi nella parte
entrale della struttura mentre nei livelli più altii nodi diverranno più radi,
noadarrivareallaradi edel grafo(ilnodoall). Questofaràsì he risalendo
il grafo per molti passi, si arrivi ai livelli più super iali, per ui le
eti het-te mostrate all'utente per prime, saranno po he e generi he. Dal punto di
vista della per ezione del risultatoquesto può essere un vantaggio visto he
l'utente non viene sommerso da troppi risultati. Tuttavia questo porta alla
generazione di una struttura troppo rami ata e profonda per essere
vera-menteutilizzata. All'opposto, risalireilgrafoperpo hipassi, sebbene renda
l'attraversamento più velo e, farà arrestare la visitasu più noditerminali,
per ui le eti hette mostrate per prime saranno in numero maggiore, ma la
struttura nel suo insieme sarà meno profonda e rami ata. Si tratta per iò
di trovare un ompromesso tra questi fattori. In base alleprove eettuatee
alleindi azioniri evutedalWeb (vedendo omeoperanoadesempioSnakeT
e Vivísimo) relative al tempo medio speso dagli utenti nella onsultazione
8
Figura3.3: Risultatodel lusteringmediantelate ni adelle upward paths.
dei risultati prodotti, si è ritenuto opportuno per orrere il grafoall'indietro
di
3
passi. Questo produ e un buon rapporto tra prestazioni, eti hette pro-dotte, gradodirami azione dellastruttura risultanteevisitabilitàdapartedegli utenti. In Figura 3.3 viene mostrato il risultato del lustering per la
query opsin già onsideratainpre edenza. Della lusterizzazionemostrata
in gura vogliamomettere in evidenzaal uni aspetti:
•
Solo inodifogliadell'alberomostrato orrispondonoaterminiinGene Ontology veramente riferiti dalle entry ritornate. I nodi non foglia(quelli on il simbolo + o -) sono i termini dell'ontologia esplorati
mediantel'algoritmo delle upward paths;
•
Il risultato prodotto è un DAG visualizzato on una struttura ad al-bero. Al uni sottoalberi sono pertanto dupli ati. Si veda ad esempio•
Il terminephtotrasdu tion èun on etto generi o he l'utente può esplorare s oprendo he rhodopsin mediated phototra sdu tion èunafunzionesimileaphototrasdu tion, UV ephototrasdu tion,
visible light sotto iqualiri adonorispettivamentedue e un
do u-mento.
•
I gruppigeneratisono ordinatiper ardinalitàde res entidegliinsiemi dei do umentiasso iati alleeti hette(inmanierasimileaquantofattoda Vivísimo e simili). Tali dimensioni sono riportate tra parentesi a
an o diogni eti hetta;
•
Èpresenteungruppoother topi s heradunainseido umenti he non trovano ollo azionealtrovema he, altempostesso, non trattanotemi rilevantial puntodagenerare una propriaeti hetta;
L'attraversamento del grafo a partire da eti hette poste a livelli diversi
dellastrutturaeperunnumero ssatodipassiportaadarrestarelavisitadel
grafosunodiantenatidiquellidipartenza. All'utenteverranno poimostrati
i gra di ui tali nodi terminali sono radi e. Essend o le radi i poste a
livelli diversi di Gene Ontology , può a adere he sia possibile organizzarle
ulteriormente se ondo la relazione is_a. Ad esempio può a adere he un
per orso porti alla determinazione della radi e binding e un altro a protein
binding. Le due radi i sono a loro volta in relazione padre/ glio. Tenendo
onto diquesto, sipuò migliorare il risultatogenerato riorganizzando an he
leradi i se ondo questa relazione. Pertanto,piuttosto he avere omeprimo
livello della struttura restituita la lista di tutti i nodi terminali, lista he
potenzialmente ontiene nodi in relazione is_a tra di loro, si avranno solo
i nodi più generi i, mentre gli altri saranno opportunamente spostati nel
sottografoinmanieradarispettarelerelazionitraterminiinGeneOntology .
