Facoltà di Ingegneria dell’Informazione
Corso di Laurea in Ingegneria Informatica
ACCELERAZIONE DELL’ALGORITMO
“MULTIFACTOR DIMENSIONALITY REDUCTION”
Relatore: Prof.ssa Donatella SCIUTO
Correlatore: Ing. Fabio CANCARE’
Tesi di Laurea di:
Alessandro MARIN
Matricola n. 725513
...se un uomo non si batte per le proprie idee, o non vale l’uomo, oppure non valgono le sue idee... (Ezra Pound)
Ringraziamenti
Sommario
Il rapido sviluppo di nuovi marcatori genetici e la possibilità di ave-re a disposizione metodiche di genotipizzazione rapide e poco costose, ci pone nella possibilità di affrontare la sfida della ricerca dei geni respon-sabili di malattie complesse. Uno degli strumenti di analisi, proposti per svelare le interazioni non lineari tra gene-gene e gene-ambiente, caratte-ristiche delle malattie complesse, è l’algorimo Multifactor Dimensionality Reduction (MDR) che elabora un modello, atto a facilitare la previsione del-l’insorgere della malattia. Tuttavia, i lunghi tempi di elaborazione dell’algo-ritmo ne limitano l’applicazione in campo medico/genetico. L’obiettivo di questo lavoro è l’individuazione e la realizzazione di sistemi capaci di ab-battere i tempi di computazione di MDR, al fine di renderlo uno strumento utile all’identificazione delle componenti genetiche delle malattie comples-se. Attraverso la metodologia co-design, è possibile progettare una serie di sistemi, caratterizzati da componenti hardware e software, implementabili su Field Programmable Gate Array (FPGA), per conseguire soluzioni che implementano l’algoritmo MDR, con diverse caratteristiche prestazionali e di costi. L’analisi mira ad identificare i punti critici architetturali di ogni si-stema, al fine di indirizzare l’esplorazione nello spazio delle soluzioni, nella direzione che permetta di trovare architetture sempre migliori. Attraverso questo percorso si vuole individuare il sistema ottimale, che garantisca il miglior compromesso tra prestazioni e costi.
Questo lavoro analizza l’algoritmo MDR per individuarne le funzioni iv
critiche, le dipendenze dei dati e le dipendenze funzionali. E’ stato crea-to un modello ad-hoc in grado di simulare il tempo di esecuzione dell’al-goritmo, in relazione al tipo di partizionamento hardware e software, allo speed-up tra il modulo hardware e la sua implementazione in software e la velocità di trasferimento dei dati tra diverse partizioni.
Simulando il modello è possibile identificare quale sia la migliore parti-zione in relaparti-zione ai vincoli del sistema, con l’obiettivo di creare una prima versione di acceleratore hardware, che implementa le funzioni critiche dal software all’hardware, utilizzando il linguaggio VHDL.
La prima architettura analizzata, è stata sviluppata impiegando come dispositivo una FPGA XC5VFX70T di Xilinx, ed è composta da un pro-cessore hardcore (PowerPC440), connesso ad un singolo acceleratore hard-ware collegato al bus Processor Local Bus (PLB). Questa architettura, che ha ottenuto uno speed-up di circa 60x, rispetto alla soluzione software, è il punto di partenza dell’esplorazione nello spazio di progettazione, per la ricerca di una soluzione con il migliore compromesso in termini di presta-zioni e costi.
L’esplorazione ha portato alla creazione e alla successiva valutazione di vari sistemi. La prima soluzione realizzata è caratterizzata dall’inserimen-to di ulteriori acceleradall’inserimen-tori hardware, all’interno dell’architettura di parten-za, ottenendo uno speed-up massimo di circa 115x, rispetto alla soluzione software.
Sostituendo il processore PowerPC (PPC) con un softcore (MicroBlaze (MB)), è stato possibile implementare il sistema sulla FPGA XC5VLX110T di Xilinx, priva del processore hardcore, e analizzare la scalabilità degli ac-celeratori hardware, collegati al MB tramite un bus punto a punto chiamato Fast Simplex Link (FSL). La soluzione composta con tre moduli hardware connessi, ha ottenuto il migliore risultato con uno speed-up pari a circa 74x, rispetto alla soluzione software.
vi
Aumentando il numero di processori in relazione al numero di acce-leratori collegati ad ognuno, è risultato che un’architettura composta, da due MB collegati ognuno a tre moduli hardware, ottiene uno speed-up di circa 146x, rispetto alla soluzione software. Tale soluzione risulta essere la più performante, con uno speed-up di circa 2,36x, rispetto alle prestazioni ottenute dall’architettura di partenza.
I principali contributi innovativi di questo lavoro sono:
1. l’individuazione delle caratteristiche principali e più ricorrenti che ca-ratterizzano l’algoritmo MDR, la valutazione delle dipendenze dato e di funzione e la quantità di dati trasferiti tra le varie funzioni;
2. l’analisi e l’ottimizzazione di una prima versione di acceleratore crea-to ad-hoc su FPGA dell’algoritmo MDR;
3. la realizzazione di architetture con differenti configurazioni in modo da popolare il design space, con varie e possibili soluzioni; le archi-tetture sono state realizzate considerando diversi tipi di FPGA, pro-cessori, numero di propro-cessori, bus di collegamento, numero e tipo di acceleratori hardware dell’algoritmo;
4. l’esplorazione del design space per identificare quali sono le architet-ture migliori in relazione ai costi e alle prestazioni.
Nel capitolo 2 si presentano i principali concetti biologici che accom-pagnano la descrizione delle malattie semplici e di quelle complesse e gli strumenti e le tecniche utilizzate per studiarle. Viene introdotto l’algorit-mo MDR che risulta essere il miglior strumento per l’identificazione delle interazioni gene-gene e gene-ambiente (caratteristiche delle malattie com-plesse) e in grado di elaborare un modello per prevedere l’insorgere della malattia. Il capitolo si conclude con la descrizione del limite di MDR che consiste nell’elevato tempo di elaborazione, quando considerevoli quantità
di dati devono essere prese in considerazione. Tale limite ne compromette l’utilizzo in ambito medico genetico.
Il capitolo 3 si occupa dell’evoluzione nel campo tecnologico dei princi-pali dispositivi e delle tecniche per ottenerne le migliori prestazioni in rela-zione alle risorse disponibili. In questo capitolo vengono presentati i sistemi embedded e in particolare la metodologia di progettazione co-design; inol-tre vengono presentati i principali dispositivi programmabili, focalizzando l’attenzione sulle tecnologie riconfigurabili FPGA. Questi dispositivi sono in grado di fornire speed-up di uno, due e talvolta tre ordini di grandezza, ma richiedono la modifica del codice sorgente dell’applicazione e lo svi-luppo di componenti hardware per renderla compatibile con l’architettura scelta.
Nel capitolo 4 viene presentata una metodologia per la selezione delle funzioni dell’algoritmo MDR che devono essere implementate in hardware oppure in software. I passaggi che portano a tale risultato sono: l’analisi dell’algoritmo con l’identificazione delle dipendenze di dato e di funzione e la determinazione della quantità di dati trasferiti da funzione a funzio-ne. Attraverso queste informazioni è possibile creare un modello parame-trico del sistema, che simula il comportamento dell’algoritmo, in relazio-ne al tipo di partizionamento hardware e software scelto. La simulaziorelazio-ne considera: la velocità di trasferimento dei dati da una partizione all’altra, l’accelerazione dei moduli hardware in relazione alle corrispondenti fun-zioni software e la possibilità di stabilire quali funfun-zioni implementare in software e quali in hardware. L’analisi relativa ai tempi di esecuzione del-l’algoritmo permette di creare un insieme di possibili soluzioni di parti-zionamento hw/sw che garantiscono i migliori risultati in termini di pre-stazione. In questo capitolo, si analizza inoltre come queste soluzioni di partizionamento influenzino i costi di sistema. Attraverso quest’analisi è possibile scegliere i dispositivi più vantaggiosi per l’implementazione dei
viii
moduli hardware, al fine di sviluppare un sistema con il migliore parti-zionamento hw/sw, garantendo elevate prestazioni e bassi costi. L’analisi viene effettuata considerando come dispositivi per l’implementazione dei moduli hardware, le FPGA prodotte da Xilinx.
A partire dai risultati, ottenuti in fase di analisi, sulle prestazioni e sui costi, è auspicabile ottenere un insieme di possibili sistemi, in grado di im-plementare l’algoritmo MDR garantendo prestazioni e costi differenti, che popoleranno lo spazio delle soluzioni. Tramite una successiva esplorazione del design space è possibile identificare le soluzioni dominanti in termini di prestazioni e costi.
Il capitolo 5 descrive nel dettaglio alcune soluzioni trovate in fase di analisi; tali soluzioni, realizzate a partire da un’architettura già esistente, opportunamente analizzata e migliorata, sono tutte caratterizzate da un vantaggioso rapporto tra prestazioni e costi. Il capitolo presenta i sistemi realizzati, descrivendone le caratteristiche architetturali e valutandone i da-ti estratda-ti durante la loro esecuzione. Per ogni soluzione trovata è stata effet-tuata un’analisi per determinarne i possibili punti critici e miglioramenti, volti alla successiva esplorazione nello spazio di design, per la ricerca e realizzazione di migliori soluzioni.
Il capitolo 6 ripercorre i principali passi svolti in questo lavoro, che han-no contribuito a ridurre i tempi di esecuzione dell’algoritmo MDR, quando considerevoli quantità di dati devono essere prese in considerazione. Ven-gono presentati i migliori risultati in termine di prestazione e costi, ottenuti in fase di pianificazione attraverso la metodologia di co-design. Inoltre, vie-ne descritta l’esploraziovie-ne fatta vie-nello spazio delle soluzioni, riportandovie-ne le principali considerazioni e confrontandone i risultati con quelli che si ot-terrebbero impiegando tecnologie differenti da quelle analizzate in questo lavoro. Il capitolo si conclude con la proposta di possibili sviluppi futuri.
Indice
1 Introduzione 1
2 Concetti biologici 5
2.1 Malattie mendeliane e complesse . . . 5
2.2 Strumenti di analisi genetica . . . 7
2.2.1 I problemi nell’analisi statistica . . . 8
2.3 Multifactor Dimensionality Reduction . . . 12
2.3.1 Esempio di utilizzo dell’algoritmo . . . 13
2.3.2 Applicazione dell’algoritmo in ambito medico-genetico 16 2.3.3 Descrizione dell’algoritmo . . . 18 3 Concetti tecnologici 22 3.1 I sistemi embedded . . . 22 3.2 Co-Design . . . 24 3.2.1 Passi di progettazione . . . 25 3.3 Partizionamento hardware/software . . . 28
3.3.1 Problema del partizionamento . . . 28
3.3.2 Tecniche di partizionamento hardware/software . . 29
3.4 Processo di scheduling . . . 32
3.5 Design Space Exploration . . . 32
3.5.1 Ottimizzazione Multi-Obiettivo . . . 32
3.5.2 Popolazione del Design Space . . . 35
INDICE x
3.6 Dispositivi Programmabili . . . 37
3.6.1 FPGA Xilinx . . . 39
3.6.2 I modelli di FPGA impiegati . . . 41
4 Analisi dell’algoritmo MDR 43 4.1 Metodologia per il partizionamento . . . 44
4.1.1 Profiling dei dati . . . 44
4.1.2 Analisi dati . . . 45
4.1.3 Analisi dipendenze tra funzioni . . . 45
4.1.4 Creazione modello . . . 45
4.1.5 Analisi prestazioni . . . 46
4.1.6 Analisi costi . . . 46
4.1.7 Identificazione partizionamento hw/sw . . . 46
4.2 Analisi per il partizionamento dell’algoritmo . . . 46
4.3 Architettura del sistema base . . . 56
4.4 Valutazione dati . . . 59
4.4.1 Analisi bus . . . 64
4.4.2 Analisi tipologia processore . . . 67
4.4.3 Analisi del sistema in relazione al numero di moduli hardware . . . 69
4.4.4 Analisi miglioramento sistema . . . 73
5 Risultati sperimentali 80 5.1 Architettura di partenza . . . 81
5.1.1 Tecniche per il calcolo delle prestazioni . . . 83
5.1.2 Testing dell’architettura . . . 84
5.1.3 Analisi del componente divisore . . . 86
5.2 Soluzioni alternative sulla FPGA XC5VFX70T . . . 88
5.2.1 Inserimento di ulteriori acceleratori hardware . . . . 89
5.3 Soluzioni alternative sulla FPGA XC5VLX110T . . . 94
5.3.1 Sostituzione del dispositivo . . . 95
5.3.2 Sostituzione del bus di comunicazione . . . 97
5.3.3 Inserimento di ulteriori Processori . . . 102
5.4 Analisi delle soluzioni realizzate . . . 106
6 Conclusioni 111 6.1 Contributi innovativi . . . 115
Elenco delle figure
2.1 Modulo di interazione gene-gene . . . 10
2.2 Rappresentazione grafica della funzione dell’operatore logico OR esclusivo . . . 14
2.3 Passi principali che caratterizzano l’esecuzione dell’algoritmo Multifactor Dimensionality Reduction (MDR) . . . 19
3.1 Processo di design: design classico e co-design . . . . 23
3.2 System Design . . . 26
3.3 Esempio di un’ottimizzazione multi-obiettivo . . . 33
3.4 Esempio di design space . . . . 34
3.5 Tipologie di differenti criteri per la selezione dei punti all’interno del design space . . . 36
3.6 Esempio di struttura di una slice . . . . 40
3.7 Field Programmable Gate Array (FPGA) Virtex-5 prodotte da Xilinx 41 4.1 Distribuzione di tutte le istruzioni chiamate dall’algoritmo MDR, analizzando un dataset costituito da 1.000 attributi per 1.600 pa-zienti diversi . . . 48
4.2 Tempi di esecuzione dell’algoritmo MDR, analizzando un dataset costituito da 1.000 attributi per 1.600 pazienti diversi. . . 49
4.3 Grafo delle chiamate - mostra le dipendenze temporali e di dato . . 51
4.4 Dati relativi alla simulazione del modello, impostando una velocità di trasferimento dei dati, tra nodo hardware e software, pari a 40, 65, 80 e 120MB/s . . . 54 4.5 Schema del sistema base composto da un processore PPC collegato,
tramite il canale di comunicazione PLB, a un acceleratore hardware 57 4.6 Schema del componente mdr_core . . . . 58 4.7 Speed-up delle varie soluzioni analizzate, in funzione del numero
di moduli mdr_block inseriti in parallelo . . . 70 4.8 Prestazioni dell’architettura base quando i moduli sono in parallelo
anzichè che in serie . . . 72 4.9 Utilizzo del processore in relazione al numero di acceleratori
hard-ware mdr_block inseritei nell’architettura . . . 72 4.10 Design Space delle soluzioni di partizionamento hw/sw, valutate
in termini di prestazioni (confrontate con la soluzione completa-mente software) e di costi (relativi al dispositivo utilizzato) . . . . 79 5.1 Istruzioni chiamate dalle principali funzioni (facenti parte della
partizione chiamata model building) dell’algoritmo MDR, analiz-zando un dataset costituito da 1.000 attributi per 1.600 pazienti diversi e uno costituito da 20 attributi per 400 pazienti diversi . . 85 5.2 Tempi di esecuzione delle principali funzioni (facenti parte della
partizione chiamata model building) dell’algoritmo MDR, analiz-zando un dataset costituito da 1.000 attributi per 1.600 pazienti diversi e uno costituito da 20 attributi per 400 pazienti diversi . . 86 5.3 Schema del sistema composto da un processore PowerPC (PPC)
collegato a due moduli mdr_block tramite bus Processor Local Bus (PLB). L’interfaccia master del processore (MPLB), comunica con le due interfacce slave (SPLB) dei due acceleratori hardware, at-traverso l’arbitro del canale di trasmissione PLB . . . 90
ELENCO DELLE FIGURE xiv
5.4 Speed-up relativo alla soluzione con un processore PPC che adotta come bus di comunicazione il PLB sul dispositivo di Xilinx FPGA XC5VLX70T . . . 91 5.5 Speed-up relativo alla soluzione con un processore MicroBlaze (MB)
che adotta come bus di comunicazione il PLB sul dispositivo di Xi-linx FPGA XC5VLX70T. Lo speed-up è confrontato con le presta-zioni ottenute dalla soluzione con un solo acceleratore hardware . 93 5.6 Speed-up relativo alla soluzione con processore MB che adotta
co-me bus di comunicazione il PLB sul dispositivo di Xilinx FPGA XC5VLX110T. Lo speed-up è confrontato con le prestazioni otte-nute dalla soluzione con un solo acceleratore hardware . . . 97 5.7 Schema del sistema composto da un processore MB collegato a
due moduli mdr_block tramite bus di comunicazione Fast Simplex Link (FSL). Ogni acceleratore hardware per comunicare con il pro-cessore necessita di 2 canali FSL, connessi ognuno all’interfaccia master del modulo mdr_block (MFSL) all’interfaccia slave della CPU (SFSL) e dall’interfaccia master del processore (MFSL) a quella slave dell’acceleratore hardware (SFSL) . . . 99 5.8 Speed-up relativo alla soluzione con un processore MB che adotta
come bus di comunicazione FSL sul dispositivo di XilinX FPGA XC5VLX110T. Lo speed-up è confrontato con le prestazioni otte-nute dalla soluzione con un solo acceleratore hardware . . . 100 5.9 Differenza di uitilizzo del processore tra la soluzione che adotta
come bus di comunicazione il PLB e la soluzione che impiega il bus FSL . . . 101 5.10 Schema del sistema composto da due processori MB, collegati
ognu-no ad un modulo mdr_block tramite bus FSL, e comunicanti tra loro attraverso il componente MailBox collegato alle CPU tramite bus PLB . . . 102
5.11 Speed-up relativo alla soluzione con due processori MB che adotta-no come bus di comunicazione il bus FSL su dispositivo XC5VLX110T. Lo speed-up è confrontato con le prestazioni ottenute dalla soluzio-ne con un solo acceleratore hardware consoluzio-nesso a ogni processore . 105 5.12 Tempi di esecuzione di tutte le soluzioni analizzate su dispositivo
XC5VFX70T e XC5VLX110T . . . 107 6.1 Speed-up relativo alle soluzioni sviluppate con diverse tecnologie
(multi-core, General-Purpose computing on Graphics
Pro-cessing Units (GPGPU), FPGA). Lo speed-up è confrontato con
le prestazioni ottenute dalla soluzione sviluppata interamente in software . . . 115
Elenco delle tabelle
2.1 Tabella di verità dell’operatore logico OR esclusivo. La tabella di verità della funzione logica XOR non permette di separare le uscite mediante una retta. Perciò la disequazione esclusiva non può essere considerata una funzione linearmente separabile. . . 14 2.2 Confronto tra il risultato dell’operatore logico OR esclusivo e il
risultato dell’esecuzione dell’algoritmo MDR . . . 15 3.1 Caratteristiche principali di alcune delle principali FPGA Virtex-5
di Xilinx. . . 42 4.1 Insieme di tutte le procedure che costituiscono l’algoritmo MDR . 47 4.2 Dati di profiling dell’algoritmo MDR, analizzando un dataset
co-stituito da 1.000 attributi per 1.600 pazienti diversi. Sono ripor-tati i dati relativi alle funzioni più significative (model building
functions) . . . 49
4.3 Dati ottenuti dalla simulazione del modello considerando una velo-cità di trasferimento dei dati da un nodo software a un nodo hard-ware di 65MB/s e una velocità di elaborazione del nodo hardhard-ware di 100 volte più veloce rispetto allo stesso nodo implementato in soft-ware. La tabella mostra come il tempo di esecuzione camba quando viene utilizzato un differente partizionamento hw/sw . . . 52
4.4 Indici che identificano il tipo di partizionamento hardware/soft-ware adottato . . . 53 4.5 Componenti utilizzati per l’implementazione di un singolo
mo-dulo mdr_block – implementazione hardware del blocco model building e del blocco model_evaluation . . . 60 4.6 Componenti utilizzati per l’implementazione di un divisore . . . . 61 4.7 Componenti utilizzati per l’implementazione di un singolo
modu-lo mdr_bmodu-lock – implementazione hardware del somodu-lo bmodu-locco model
building . . . 62
4.8 Componenti utilizzati per l’implementazione dell’intero sistema – implementazione hardware dell’architettura base composta da un singolo modulo mdr_block che svolge sia il compito di model
building sia quello di model evaluation . . . 63
4.9 Dati di occupazione del processore PowerPC e MicroBlaze . . . . 68 4.10 Analisi delle prestazioni del processore in relazione al numero di
moduli hardware mdr_block . . . 71 4.11 Prestazione, confrontate con la soluzione puramente software, e
costi relativi al partizionamento hardware del solo blocco model
building, su differenti dispositivi . . . 74
4.12 Prestazione, confrontate con la soluzione puramente software, e co-sti relativi al partizionamento hardware del blocco model building e del blocco model evaluation, su differenti dispositivi . . . 76 5.1 Risorse utilizzate per la realizzazione dell’intera architettura. Il
dispositivo impiegato è una FPGA Virtex-5 XC5VFX70T di Xilinx 83 5.2 Componenti necessari per implementare il modulo mdr_block con
algoritmo HighRadix e con algoritmo Radix-2. Il dispositivo uti-lizzato è una FPGA di Xilinx della famiglia Virtex-5 chiamata XC5VFX70T . . . 89
ELENCO DELLE TABELLE xviii
5.3 Dati relativi all’architettura costituita da un processore PPC con-nesso a 1-4 moduli hardware mdr_block tramite un bus di comu-nicazione PLB sul dispositivo di Xilinx FPGA XC5VFX70T. Lo speed-up è confrontato con le prestazioni ottenute dalla soluzione con un solo acceleratore hardware . . . 90 5.4 Dati relativi all’architettura costituita da un processore MB
con-nesso a 1-3 moduli hardware mdr_block tramite un bus di comu-nicazione PLB sul dispositivo di Xilinx FPGA XC5VFX70T. Lo speed-up è confrontato con le prestazioni ottenute dalla soluzione con un solo acceleratore hardware . . . 92 5.5 Dati relativi all’architettura costituita da un processore MB
con-nesso a 1-6 moduli hardware mdr_block tramite un bus di comu-nicazione PLB sul dispositivo di Xilinx FPGA XC5VLX110T. Lo speed-up è confrontato con le prestazioni ottenute dalla soluzione con un solo acceleratore hardware . . . 95 5.6 Dati relativi all’architettura costituita da un processore MB
con-nesso a 1-6 moduli hardware mdr_block tramite un bus di comu-nicazione FSL sul dispositivo di Xilinx FPGA XC5VLX110T. Lo speed-up è confrontato con le prestazioni ottenute dalla soluzione con un solo acceleratore hardware . . . 99 5.7 Dati relativi all’architettura costituita da due MB connessi con
1-3 moduli per ogni processore, tramite FSL su XC5VLX110T. Lo speed-up è confrontato con le prestazioni ottenute dalla soluzione con un solo acceleratore hardware connesso a ogni processore . . . 104
Elenco delle abbreviazioni
ANN Artificial Neural NetworksASIC Application Specific Integrated Circuit
CAD Computer Aided Design
CLB Configurable Logic Block
CPLD Complex Programmable Logic Device
DMA Direct Memory Access
DOE Design Of Experiments
DSE Design Space Exploration
DSP Digital Signal Processing
GPGPU General-Purpose computing on Graphics Processing Units
CPU Central Processing Unit
FPGA Field Programmable Gate Array
FIFO First In First Out
FSL Fast Simplex Link
FSM Finite State Machine
ELENCO DELLE TABELLE xx
ILP Integer Linear Programming
IOB I/O Block
IPM Integer Programming Models
ISA Instruction Set Architecture
LMB Local Memory Bus
LUT LookUp Table
MB MicroBlaze
MDR Multifactor Dimensionality Reduction
NRE Non Recurring Engineering
PAL Programmable Array Logic
PLA Programmable Logic Array
PLB Processor Local Bus
PPC PowerPC
RAM Random Access Memory
SDL Specification and Description Language
Introduzione
L’identificazione della componente genetica delle malattie complesse costituisce una delle principali sfide della medicina dei prossimi anni. La possibilità di avere test genetici capaci di determinare il grado di suscet-tibilità al cancro, all’infarto o al morbo di Alzheimer, avrebbe un enorme impatto positivo sulla salute pubblica.
Negli ultimi anni sono state sviluppate e migliorate tecniche capaci di rica-vare le principali informazioni di carattere biologico dei pazienti, a partire dall’elaborazione dei dati acquisiti sperimentalmente in laboratorio. Dall’a-nalisi di questi dati è possibile studiare la correlazione tra le caratteristiche fenotipiche e le caratteristiche genotipiche d’interesse. Da studi recenti, re-lativi a pazienti con malattie complesse, si è giunti alla conclusione che gran parte delle espressioni fenotipiche (affetto o non affetto) è causata dalla com-plessa interazione non-lineare tra differenti fattori genetici e ambientali che vengono comunemente chiamati fattori di suscettibilità. Per determinare la suscettibilità alle malattie complesse è quindi necessario sviluppare tecni-che in grado di creare modelli e strutture di interazione tra le caratteristitecni-che genetiche e i fattori ambientali e di valutarne la loro accuratezza.
La bioinformatica, disciplina scientifica dedicata alla risoluzione di proble-mi biologici a livello molecolare attraverso metodi informatici, ha adattato
CAPITOLO 1. INTRODUZIONE 2
tecniche sviluppate nel campo del data mining capaci di esplorare automa-ticamente lo spazio delle possibili interazioni non lineari tra variabili mul-tiple, per identificare i modelli dei sistemi biologici.
L’algoritmo Multifactor Dimensionality Reduction (MDR) [1] si presenta essere una soluzione a tale problema, identificando le interazioni non li-neari tra gene-gene e gene-ambiente, che influenzano la suscettibilità alle malattie complesse, attraverso una strategia di riduzione della dimensio-nalità che si basa sull’identificazione di particolari associazioni tra fattori ad alto rischio e a basso rischio. Il risultato dell’algoritmo è la creazione di una rappresentazione che facilita l’individuazione delle interazioni non-lineari tra i vari attributi, in modo tale che la previsione dell’insorgere della malattia sia migliore rispetto a quella della rappresentazione originale dei dati. Tale algoritmo è stato impiegato con successo in alcuni studi; ad esem-pio è stato applicato per analizzare i dati di pazienti soggetti al tumore al seno [2], trovandone un modello capace di predire la malattita con un ac-curatezza prossima all’80%. Tuttavia, per ottenere un modello accurato è necessario che l’algoritmo analizzi grandi quantità di dati; ne consegue che l’esecuzione di MDR sia computazionalmente onerosa e i tempi di elabora-zione limitino gravemente l’applicaelabora-zione in campo medico/genetico. Per far fronte a questo problema, riscontrato in molte applicazioni di bio-informatica, i ricercatori hanno iniziato a considerare le nuove piattaforme
tecnologiche, che promettono sempre maggiori riduzioni di tempi e di
co-sti. Una prima soluzione è stata trovata con l’impiego dei sistemi comune-mente chiamati grid computing, capaci di utilizzare le risorse di calcolo di sistemi eterogenei situati in luoghi diversi. Tali sistemi permettono la con-divisione coordinata di risorse all’interno di un’organizzazione virtuale e funzionano molto bene se le applicazioni da eseguire hanno determina-te caratdetermina-teristiche: possono essere scomposdetermina-te in processi indipendenti l’uno dall’altro, i dati da trasferire attraverso la rete non sono confidenziali e la
loro quantità non deve essere elevata. La maggior parte delle applicazioni di bioinformatica, tra cui MDR, non dispongono di queste caratteristiche, motivo per cui i sistemi grid computing non risultano essere la soluzione mi-gliore per la risoluzione di tale problema.
Le recenti ricerche nell’ambito delle tecnologie digitali, hanno portato alla realizzazione e allo sviluppo di differenti soluzioni, che garantiscono ele-vata capacità di calcolo: come i dispositivi hardware riconfigurabili (Field Programmable Gate Array (FPGA)), unità di elaborazione grafica applicata al calcolo general purpose (General-Purpose computing on Graphics Pro-cessing Units (GPGPU)) e processori multi-core/many-core. Tuttavia, per ottenere un rilevante incremento delle prestazioni degli algoritmi è neces-sario conoscere a fondo sia le loro caratteristiche, sia quelle del dispositivo adottato, in modo tale da realizzare una soluzione capace di eseguire le funzionalità dell’algoritmo sfruttando al meglio le risorse messe a disposi-zione dal dispositivo.
Questo lavoro di tesi si propone di migliorare le prestazioni dell’algorit-mo di bioinformatica MDR, per ridurne i lunghi tempi di esecuzione che ne limitano l’applicazione in campo medico/genetico. La soluzione a ta-le probta-lema si può trovare studiando una metodologia per la realizzazio-ne di soluzioni che riescano a garantire elevate prestazioni dell’applicazio-ne in relaziodell’applicazio-ne ai costi dei dispositivi impiegati. Per ottedell’applicazio-nere tale risultato viene adottato in fase di progettazione del sistema la metodologia, chia-mata co-design, che ricerca un giusto compromesso tra il partizionamen-to hardware e quello software. Lo studio ha l’obiettivo di massimizzare le prestazioni dell’algoritmo, considerando il vincolo dei costi e delle risor-se disponibili e contemporaneamente di minimizzare i costi di sistema, in relazione al vincolo delle prestazioni, per ottenere sistemi con i requisiti ri-chiesti sfruttando le potenzialità dell’hardware e del software, attraverso una loro progettazione concorrente. L’analisi viene effettuata considerando
CAPITOLO 1. INTRODUZIONE 4
come dispositivo le FPGA, per l’implementazione dei moduli hardware e dei moduli software. Il processo di progettazione del sistema, per l’esecu-zione dell’algoritmo MDR, può essere considerato come un problema di ottimizzazione multi-obiettivo che cerca di individuare una soluzione otti-male, tenendo conto di vincoli come: le prestazioni, l’utilizzo di risorse, i costi e il consumo di potenza. Al fine di ricercare le soluzioni ottimali è ne-cessario valutare e considerare una serie di varianti, per realizzare differenti soluzioni che garantiscano diversi compromessi tra prestazioni e costi, con l’obiettivo di popolare il design space. Esplorando lo spazio delle soluzio-ni è possibile trovare l’implementazione ottimale in relazione ai requisiti di progetto.
Concetti biologici
Questo capitolo si pone l’obiettivo di descrivere i principali concetti bio-logici e bioinformatici per la prevenzione e diagnosi delle malattie geneti-che, presentando gli strumenti per il recupero e l’identificazione dei dati di carattere genotipico e fenotipico dei vari pazienti.
2.1 Malattie mendeliane e complesse
Il progresso della ricerca in ambito genetico e la realizzazione di metodi affidabili di analisi molecolare ha consentito e consentirà di ottenere enor-mi progressi sia nel campo diagnostico che terapeutico. Il genetista Fran-cis Collinsafferma che: “praticamente ogni malattia (a parte forse il trauma) ha una componente genetica, e la sua decodificazione costituisce una priorità della medicina moderna” [3].
Nel corso degli ultimi anni, la ricerca genetica ha ottenuto ottimi risul-tati analizzando le malattie genetiche individuandone due grosse famiglie, la prima classificata come malattie semplici o mendeliane mentre la seconda come malattie complesse o multifattoriali.
E’ soprattutto sulle malattie semplici o mendeliane che si sono ottenu-ti otottenu-timi risultaottenu-ti. Esse tendono generalmente a essere rare, con frequenze
CAPITOLO 2. CONCETTI BIOLOGICI 6
nelle popolazioni inferiori allo 0,05%. Sono malattie dovute alla mutazio-ne di un singolo gemutazio-ne (per esempio la fibrosi cistica, l’emofilia, la malattia di Huntington e la sindrome dell’X fragile). Queste malattie si trasmetto-no secondo modalità relativamente semplici (mendeliane): autosomiche a carattere dominante, recessivo o codominante oppure legate al cromosoma X.
Al secondo gruppo appartengono le cosiddette malattie
multifattoria-li, anche definite come malattie complesse. La ricerca su tali malattie risulta
essere più complicata e le applicazioni bioinformatiche in questo settore so-no ancora molto poche. Queste patologie rappresentaso-no un pericolo molto più grave per la salute pubblica rispetto alle malattie mendeliane, poiché sono più diffuse e sono spesso caratterizzate da frequenze pari o superiori all’1%. Di questa categoria fanno parte patologie come il diabete, la schi-zofrenia, l’obesità, un numero rilevante di patologie del sistema cardiova-scolare [4] come l’infarto, la sclerosi multipla [5] [6], l’aterosclerosi, la scle-rodermia [7], l’ictus [8] [9], l’autismo [10] [11], l’ipertensione, il cancro e la depressione. L’identificazione dei geni responsabili di queste malattie viene considerata come una delle grandi sfide della medicina. Una caratteristica comune a tutte le malattie complesse è il fatto di presentare una marcata “familiarità”. Si è dimostrato che in una famiglia di un paziente soggetto a malattia complessa sono presenti spesso altri casi tra i parenti, senza pe-rò riconoscere caratteristiche riconducibili a una dominanza, o recessività o a un tratto legato al sesso, come invece accade nelle malattie semplici. Un’altra caratteristica importante delle malattie complesse è che esse sono determinate dall’interazione di diversi fattori genetici e diversi fattori am-bientali [12] che vengono comunemente chiamati fattori di suscettibilità. Un altro aspetto da prendere in esame è che tali fattori agiscono con combina-zioni diverse da individuo a individuo. Per ottenere la stessa suscettibilità in un individuo possono cooperare alcuni fattori che invece non sono
ca-suali in un altro. Due insiemi di fattori di suscettibilità in comune devono avere soltanto il fatto di determinare in entrambi i casi il superamento di una soglia chiamata soglia di suscettibilità che determina l’insorgere della malattia.
2.2 Strumenti di analisi genetica
Negli ultimi anni i geni responsabili di più di 1.500 malattie genetiche umane sono stati isolati e riconosciuti. La maggior parte di queste malattie rientrano nella categoria delle malattie semplici o mendeliane.
Questo grande risultato della ricerca genetica si deve sostanzialmente a una metodica chiamata clonaggio posizionale [13]. Questa tecnica preve-de l’isolamento di un gene, responsabile di una malattia, basandosi esclu-sivamente sulla sua posizione sul cromosoma, senza alcuna conoscenza a priori della sua struttura o funzione. Il clonaggio posizionale si basa sul-l’analisi del linkage. Due loci genetici si dicono in linkage quando tendono a conservarsi nelle generazioni più frequentemente di quanto dimostrato dalla seconda legge di Mendel. Uno dei loci può essere il locus di una malat-tia mendeliana, con una posizione sconosciuta nel genoma, mentre l’altro può essere un marcatore genetico collocato in una posizione conosciuta. Quindi un linkage significativo localizza una malattia su un segmento di cromosoma che può essere ulteriormente studiato fino ad arrivare al ge-ne in esso mutato. L’analisi di linkage non può essere facilmente impiegata nell’ambito delle malattie complesse. Le principali motivazioni sono:
• Un individuo può essere malato per gli effetti non di un solo, ma di più geni localizzati su cromosomi differenti.
• L’analisi di linkage prevede che la modalità di trasmissione (domi-nante, recessivo, x-linked) sia conosciuta. Questa fa si che l’analisi
CAPITOLO 2. CONCETTI BIOLOGICI 8
di linkage rientri nella categoria di tecniche parametriche. Una pos-sibile alternativa è quella di un approccio attraverso il linkage dise-quilibrium, tecnica che conserva il primo limite dell’analisi linkage ma risulta essere non parametrica.
Un altro metodo è quello del gene candidato [14]. Questo approccio prevede una prima fase in cui si candida un gene la cui alterazione può essere responsabile della malattia sulla base della sua funzione. Come se-condo passo si procede a cercare variazioni del gene candidato che siano presenti nella popolazione degli affetti e assenti nella popolazione dei casi di controllo, questo permette di analizzare i livelli di espressione di geni specifici in uno studio caso-controllo. L’analisi del gene candidato ha fat-to la sfat-toria della genetica precedente al clonaggio posizionale. Gli esempi più noti sono l’identificazione dei geni responsabili delle emoglobinopatie. Questa tecnica è poi diventata di marginale importanza per l’identificazio-ne delle malattie mendelial’identificazio-ne a causa dell’avvento del clonaggio posizionale. Tale approccio è tornato, in una versione leggermente modificata, dopo il completamento della sequenza del genoma umano, proprio come metodo di approccio alle malattie complesse. Le ragioni di questo ritorno risiedono nella scoperta dei SNP, nella disponibilità di metodi di analisi di varianti alleliche con elevata produttività e di nuovi strumenti di analisi statistica. La scoperta della SNP risulta essere un potente strumento per candidare variazioni genetiche potenzialmente in grado di determinare suscettibilità alle malattie complesse. Inoltre è fondamentale sottolineare il ruolo rivesti-to dall’innovazione tecnologica che promette sempre maggiori riduzioni di tempi e di costi per quanto riguarda il problema da affrontare nell’analisi statistica.
2.2.1 I problemi nell’analisi statistica
L’analisi di associazione che si effettua applicando la strategia del ge-ne candidato è dal punto di vista teorico di grande semplicità. Infatti non si tratterebbe altro che di valutare la differenza di frequenza allelica di un genetra una popolazione di individui affetti e una di controllo. Se quella variante allelica fosse maggiormente presente tra gli affetti in maniera sta-tisticamente significativa, si potrebbe suggerire un suo ruolo nella suscet-tibilità alla malattia. Questo approccio è tuttavia caratterizzato da diverse problematiche [15]; le principali sono: il problema del test multiplo, quello della stratificazione, quello dell’epistasi e quello della dimensionalità.
Il problema del test multiplo Quando vengono testati diversi geni
candi-dati c’è una probabilità che la soglia statistica venga superata a causa di errori che aumentano all’aumentare dei geni che vengono analizza-ti. Esistono metodi che servono a modificare la soglia di significatività in relazione al numero di ipotesi valutate. Il più conosciuto di questi metodi è quello di Bonferroni [16]. Un’alternativa a questi metodi so-no le tecniche di permutazione, attraverso le quali la tabella originale dei dati viene permutata automaticamente un certo numero di volte e per ogni nuova configurazione viene ricalcolata la statistica. Si ot-tiene così una valutazione empirica della significatività. Queste me-todiche liberano il ricercatore dalla necessità di focalizzarsi su misure statistiche le cui proprietà teoretiche possono, alcune volte, essere di non semplice comprensione e non perfette.
Il problema della stratificazione Negli individui affetti da malattie
com-plesse ci si aspetta che non tutti abbiano gli stessi geni di suscetti-bilità, una popolazione di affetti in realtà è composta da differenti gruppi con differenti componente genetiche di suscettibilità. Questi gruppi non sono riconoscibili istantaneamente, è quindi necessario
CAPITOLO 2. CONCETTI BIOLOGICI 10
farlo per tentativi. È fondamentale stratificare il campione nella ma-niera più razionale possibile, per ridurlo a sottogruppi, che risultino il più omogenei possibili dal punto di vista genetico. Un importante problema nell’approccio del gene candidato è quello dell’eterogeneità genetica, tramite i sistemi di stratificazione è possibile risolverlo.
Il problema dell’epistasi Col termine epistasi si definisce quel fenomeno
per il quale il risultato fenotipico di un gene viene influenzato dal va-lore fenotipico di un altro gene. Tutte le conoscenze accumulate negli ultimi anni sul funzionamento dei geni hanno dimostrato un eleva-to grado di interazione gene-gene. L’interazione epistatica dei geni porta a stabilire che una variante allelica di un gene potrebbe avere influenza nella suscettibilità a una malattia solo se presenti altre va-rianti di altri geni. È ovvio che l’esistenza dell’epistasi complica l’a-nalisi, anche perché la natura e gli effetti di queste interazioni sono ancora lontani dall’essere completamente definiti e per larga misu-ra, rimangono non prevedibili. In ogni caso nasce la necessità non più di associare a una malattia una forma allelica, ma la presenza contemporanea di più forme alleliche.
Figura 2.1: Modulo di interazione gene-gene
A) potrà essere divisa in tre gruppi (omozigoti AA, eterozigoti Aa e omozigoti aa), analizzando due varianti insieme i gruppi diventano 9, con tre diventano 27 e così via. La figura 2.1 illustra questo problema. È ovvio che il numero dei pazienti analizzati per gruppo diminui-sce a causa della complessità del problema, rendendo difficile se non impossibile il raggiungimento di una significatività statistica.
Il problema della dimensionalità La necessità di stratificare insieme con
quella di tenere in considerazione l’effetto epistatico, sono le princi-pali cause che determinano quella che alcuni chiamano la maledizione della dimensionalità. La necessità di analizzare sottogruppi spesso ha risultati statistici insoddisfacenti anche quando si considerano cam-pioni di dimensioni enormi [17]. Esistono diversi approcci a questo problema.
La regressione logistica multipla [18] è la metodica più classica per l’analisi delle possibili associazioni tra i geni candidati e le malattie complesse. Essa è orientata a trovare la probabilità di un oggetto di essere classificato all’interno di una categoria, in relazione a una com-binazione di fattori di predizione. Purtroppo questa metodica soffre di gravi limitazioni. Prima di tutto essa è dipendente dalla numero-sità del campione, e per gli argomenti riportati in precedenza, risulta evidente quanto ciò sia limitante. In aggiunta essa impone relazioni fisse tra genotipo e fenotipo. Anche questo scenario potrebbe non es-sere realistico alla luce delle riflessioni sull’effetto epistatico. In con-clusione, per quanto ancora molto usata, tale metodica non risulta perfettamente adeguata agli scopi dell’analisi dei geni responsabili di malattie complesse.
Artificial Neural Networks (ANN) [19] viene considerato come uno
CAPITOLO 2. CONCETTI BIOLOGICI 12
non lineare.
Gli algoritmi a priori [20] sono basati su metodi Bayesiani, sono stru-menti di pattern recognition sperimentati nell’associazione tra SNP e malattie complesse [21]. La loro funzione è sostanzialmente quella del cosiddetto data mining, cioè l’esplorazione di dati complessi al-la ricerca di associazioni, da validare in una seconda fase con altre metodiche statistiche.
Multifactor Dimensionality Reduction (MDR) [22] [23] [24] [25]
agi-sce attraverso una strategia di riduzione della dimensionalità che si basa sull’identificazione di particolari associazioni tra fattori ad alto rischioo a basso rischio. Questa nuova variabile mono-dimensionale è valutata per la sua capacità di predire lo stato di salute o di malat-tia. MDR è stato pensato per essere in grado di svelare le interazio-ni non lineari gene-gene e gene-ambiente utilizzando un approccio non-parametrico e model-free con l’obiettivo di risolvere il problema dell’epistasi. Nella metodica sono previsti sistemi che consentono una convalida interna del fattore. Inoltre, attraverso tecniche di permu-tazione per eliminare il problema del test multiplo, possono essere de-rivati dei valori di probabilità dell’accuratezza del risultato. MDR è stato adoperato con successo in alcuni studi [26] [27] e molta attenzio-ne è riservata alle possibili applicazioni future [28] [29] [30]. Risulta essere un metodo in grado di affrontare il problema della dimensionali-tà, infatti all’aumentare dei fattori analizzati diviene repentinamente insuperabile rispetto agli altri metodi analizzati.
2.3 Multifactor Dimensionality Reduction
MDR è un approccio non parametrico e model-free di data mining per individuare le combinazioni di attributi o variabili indipendenti che
intera-giscono tra loro in modo non lineare al fine di determinare il valore assunto da una variabile di classe. MDR è stato progettato per identificare le inte-razioni tra le variabili discrete che influenzano un risultato binario, ed è considerato una valida alternativa non parametrica, ai tradizionali metodi statistici (vedi sottosezione 2.2.1).
La base del metodo MDR è un algoritmo di induzione che converte due o più variabili in un singolo attributo. Questo processo per la realizzazio-ne di un nuovo attributo modifica lo spazio di rappresentaziorealizzazio-ne dei dati. L’obiettivo finale è quello di creare una rappresentazione che facilita l’in-dividuazione delle interazioni non-lineari tra i vari attributi, in modo tale che la previsione della variabile di classe sia migliore rispetto a quella della rappresentazione originale dei dati.
2.3.1 Esempio di utilizzo dell’algoritmo
Di seguito viene riportato un semplice esempio per facilitare la com-prensione dell’algoritmo MDR. Si consideri la funzione dell’operatore logi-co chiamato OR esclusivo (XOR o disgiunzione esclusiva). La disgiunzione esclusiva viene utilizzata come esempio di una funzione che non è linear-mente separabile1 (vedi figura 2.2) [31]. La tabella 2.1 rappresenta la
tabel-la di veritàrelativa alla disgiunzione esclusiva: viene riportata la funzione XOR che relaziona gli attributi (X1 e X2) con la variabile di classe (Y).
Per risolvere la funzione un algoritmo di data mining avrebbe bisogno di scoprire o approssimare la funzione di XOR, al fine di prevedere con precisione le informazioni Y in relazione alla variazione degli attributi X1 e X2. Una possibile alternativa è quella di cambiare prima la rappresenta-zione dei dati usando l’indurappresenta-zione per facilitare la modellarappresenta-zione predittiva.
1La funzione XOR vale uno quando gli ingressi sono differenti, zero quando sono uguali
(vedi tabella 2.1). Non esiste alcuna retta che separi il piano in due regioni l’una contenente solo le coppie di ingresso corrispondenti a un’uscita uguale a uno, l’altra contenente solo quelle la cui uscita è pari a zero
CAPITOLO 2. CONCETTI BIOLOGICI 14
Tabella 2.1: Tabella di verità dell’operatore logico OR esclusivo. La tabella di verità della funzione logica XOR non permette di separare le uscite mediante una retta. Perciò la disequazione esclusiva non può essere considerata una funzione linearmente separabile
X1 X2 Y 0 0 0 0 1 1 1 0 1 1 1 0 X2 X1 1 1 0
Figura 2.2: Rappresentazione grafica della funzione dell’operatore logico OR esclusivo
Il problema si risolve tramite MDR nel seguente modo: l’algoritmo inizia selezionando due attributi. In questo semplice esempio, X1 e X2 sono sele-zionati. Viene analizzata ogni combinazione di valori per X1 e X2 e contato il numero di volte in cui il risultato Y risulta uguale a 1 e contemporanea-mente qunte volte risulta uguale a 0. Nel caso in esempio, per la prima combinazione ove X1 e X2 sono entrambi uguali a 0, risulta che Y = 1 si verifica zero volte mentre Y = 0 si verifica una volta . Il rapporto di questi conteggi viene calcolato e confrontato con una soglia fissa. In questo caso di esempio il rapporto tra il numero è 0 / 1, che è inferiore alla nostra so-glia fissata a 1. Poiché 0 / 1 <1 possiamo codificare un nuovo attributo (che
chaiameremo Z) come uno 0. Quando il rapporto è superiore a 1 allora al nuovo attributo Z assoceremo il valore di 1. Questo processo viene ripetuto per tutte le combinazioni dei valori per gli attributi di X1 e di X2. La tabella 2.2 illustra la nostra nuova trasformazione dei dati in seguito all’esecuzione dell’algoritmo MDR.
Tabella 2.2: Confronto tra il risultato dell’operatore logico OR esclusivo e il risultato dell’esecuzione dell’algoritmo MDR Z Y 0 0 1 1 1 1 0 0
In questo esempio molto semplice, la funzione Y = Z ha una precisione di classificazione pari a 1, ovvero si è trovato il risultato ottimale. Una ca-ratteristica dei metodi di induzione come MDR è la possibilità di utilizzare qualsiasi metodo di data mining o machine learning per analizzare la nuo-va rappresentazione dei dati attravero l’impiego di alberi decisionali, reti neurali o attravero metodi Bayesiani.
L’algoritmo MDR trova un vasto impiego nell’ambito medico - geneti-co, per l’individuazione delle interazioni gene-gene e gene-ambiente e per risolvere il problema dell’epistasi e della dimensionalità, che influenzano la suscettibilità alle malattie complesse umane. Tali scoperte costituirebbe-ro un pcostituirebbe-rogresso eccezionale in quanto consentirebbecostituirebbe-ro la prevenzione o la diagnosi precoce delle malattie genetiche complesse multifattoriali. Tut-tavia, MDR può essere applicato anche ad altri settori come l’economia, ingegneria, meteorologia, ecc. dove le interazioni tra gli attributi discreti possono essere importanti per prevedere un risultato binario.
CAPITOLO 2. CONCETTI BIOLOGICI 16
2.3.2 Applicazione dell’algoritmo in ambito medico-genetico
L’identificazione e la caratterizzazione dei geni di suscettibilità per le malattie complesse umane è una delle maggiori sfide dei genetisti in questi ultimi anni. Questa sfida è in parte causata dai limiti dei metodi parametrici-statistici per la rilevazione degli effetti del gene che sono dipendenti esclu-sivamente o in parte dalle interazioni con altri geni e con fattori ambientali. Per esempio, la regressione logistica è un metodo comunemente usato per modellare le relazioni tra i predittori discreti, come i genotipi, e i risultati clinici. Tuttavia, la regressione logistica, come la maggior parte dei meto-di parametrici-statistici, è meno pratica per trattare dati meto-di elevata meto- dimen-sione. Infatti, quando una grande quantità di interazioni viene modellata, ci sono molte celle della tabella che non contengono osservazioni. Que-sto può portare a stime dei coefficienti molto grandi ed errori standard. Una soluzione a questo problema è raccogliere un gran numero di cam-pioni per permettere di avere stime robuste in relazione agli effetti di inte-razione, tuttavia può accadere che il numero di campioni da raccogliere sia proibitivo. Una soluzione alternativa è sviluppare nuovi metodi sta-tistici e computazionali che migliorino il potere di individuare gli effetti multi-locus.
Per risolvere questo problema, si utilizza l’algoritmo MDR [32], meto-do per individuare e caratterizzare le interazioni non lineari tra gene-gene e tra gene-ambiente utilizzando un approccio non-parametrico. MDR è stato proposto quale metodo in grado di affrontare il problema della dimensio-nalità. Agisce attraverso una strategia di riduzione della dimensionalità, che si basa sull’identificazione di particolari associazioni tra fattori ad alto rischioo a basso rischio. Il risultato, di questa riduzione della dimensionali-tà, è una nuova variabile mono-dimensionale valutata per la sua capacità di predire lo stato di salute o di malattia, attraverso la cross-validazione [33] e i test di permutazione.
L’algoritmo MDR è stato ampiamente utilizzato in campo medico - ge-netico per studiare le malattie genetiche multifattoriali anche chiamate com-plesse. Molte malattie sono state analizzate da tale algoritmo a partire dal cancro al seno [2], recentemente è stato impiegato per studiare l’autismo [34], le malattie cardiovascolari [35] come l’infarto [36], il diabete di ti-po 2 [37], la depressione [38], l’epilessia [39], la sclerosi multipla [40] e l’asma [41].
La prima versione dell’algoritmo MDR [2] sembra molto promettente, tuttavia vi è una enorme limitazione dovuta alla complessità esponenziale dell’algoritmo rispetto al numero di varianti prese in considerazione. Per dimostrare l’accuratezza di MDR sono stati effettuati test su una serie di vari dati costruiti sulla base di modelli predefiniti per lo studio dell’epi-stasi, l’algoritmo è stato in grado di identificare le interazioni all’interno del dataset di analisi con una precisione compresa tra 80% e il 90%. In questi primi esperimenti effettuati, si sono considerate solo dieci varianti costi-tuite da cinque geni differenti. Questa prima versione dell’algoritmo non può identificare tutte le malattie complesse, poiché il numero di varianti da prendere in considerazione potrebbe essere molto più grande di dieci (in alcuni casi è necessario valutare un milione di varianti) e utilizzando tale versione i tempi di esecuzione sarebbero computazionalmente spropositati. Successivamente, gli stessi autori hanno rilasciato l’implementazione software dell’algoritmo [42] e hanno pubblicato alcune considerazioni sulla complessità: analizzando un caso reale, utilizzando un dataset sul cancro al seno contenente informazioni su 200 pazienti, il risultato di MDR è stato l’identificazione di un modello a quattro loci caratterizzato da un potere predittivo superiore all’80%.
I risultati ottenuti, utilizzando PC Pentium III da 600 MHz relativi al tempo di esecuzione dell’algoritmo sono risultati inferiori a 6 ore. Si è sti-mato che se il dataset fosse costituito da 1000 variabili, il numero di
com-CAPITOLO 2. CONCETTI BIOLOGICI 18
binazioni potrebbero aumentare fino a oltre 8.000 miliardi. La velocità di elaborazione necessaria per analizzare dataset così grandi sarà sempre ina-deguata impiegando solo l’implementazione software dell’algoritmo.
Questo spiega perché gli autori hanno cominciato a indagare sui possi-bili miglioramenti del algoritmo, in particolare, hanno deciso di sperimen-tare strategie di apprendimento automatico (machine learning strategies [43]) per la selezione degli attributi [44]. Hanno ottenuto significativi incrementi nella velocità (50x), tuttavia, la complessità è ancora elevata e la necessità di acceleratori hardware e l’impiego di tecniche di co-design è evidente.
2.3.3 Descrizione dell’algoritmo
L’algoritmo MDR è costituito da sei passaggi (vedi figura 2.3) raggrup-pate in tre macro-fasi [45].
L’algoritmo prevede come input un insieme di dati che riportano le in-formazioni relative ad un certo numero di casi (persone affette dalla ma-lattia analizzata) e controlli (persone non affette dalla mama-lattia analizzata). Per ogni persona vengono inserite tutte le sue caratteristiche genotipiche e fenotipiche o parte di queste caratteristiche in relazione al tipo di malattia considerata, insieme con lo stato della malattia (affetto o non affetto). L’al-goritmo cerca il modello N-dimensionale che rappresenta meglio l’insieme dei dati selezionati.
Primo passo – selection: i dati vengono divisi casualmente in p parti (es. in
10 parti uguali) per creare due insiemi complementari: uno chiamato training set(es. 9/10 dei dati) mentre un secondo chiamato testing set (es. 1/10 dei dati). MDR viene eseguito per ogni combinazione dei casi presenti nel primo insieme e impiegato per fare previsione circa lo stato della malattia per tutti i possibili casi contenuti nel secondo insieme; questo consente di eseguire una validazione incrociata dei
Passaggio 1 Passaggio 2 Passaggio 3
Passaggio 6 Passaggio 5 Passaggio 4
1 2 3 4 5 6 7 8 9 10 Fattori Locus 1 Locus 2 Locus 3 Locus 4 Locus 5 Locus 6 … Locus n Modelli Fattori Errori 1,6 19,25 1,3 22,12 2,4 24,33 2,3 28,14 …. … bb Bb BB AA Aa aa 2 0 0 2 1 2 1 2 1 0 2 0 0 2 2 1 1 0 bb Bb BB AA Aa aa 12 4 0 2 8 7 15 20 12 3 8 3 14 11 7 13 0 0 bb Bb BB AA Aa aa 3,00 0,42 1,14 0,75 4,00 2,66 1,27 0,54
Figura 2.3: Passi principali che caratterizzano l’esecuzione dell’algoritmo MDR
dati (passaggio 1, figura 2.3). La proporzione di soggetti per i quali è stata fatta una previsione errata è una stima dell’errore di previsione che verrà successivamente eseguita al termine del terzo passo. I pa-rametri N sono scelti dal pool di tutti i papa-rametri (passaggio 2, figura 2.3), la selezione può essere esaustiva (cioè tutte le combinazioni di parametri sono esplorate) o guidata dall’utente.
Secondo passo – model building: definizione di un modello cioè uno
spa-zio N-dimensionale equivalente al prodotto cartesiano dei parametri del domino selezionati nel passo 1 (passaggio 3, figura 2.3; le barre relative ad ogni cella rappresentano le distribuzioni dei casi ipotetici (a
si-CAPITOLO 2. CONCETTI BIOLOGICI 20
nistra) e dei controlli (a destra) con ogni possibile combinazione dei fattori). La dimensione di un parametro genetico di un dominio è il numero di valori che una variante genetica può assumere (negli esseri uma-ni questo numero è fissato a tre). Le variabili fenotipiche invece sono quasi sempre delle variabili booleane. Durante questa fase ogni da-to è classificada-to all’interno di una cella dello spazio N-dimensionale, per ogni cella due contatori tengono traccia del numero di casi e di controlli.
Terzo passo – model evaluation: per ogni cella del modello, se il rapporto
caso/controllo è superiore o uguale a una soglia predefinita (di solito 1.0) la cella è etichettato come ad alto rischio, altrimenti è etichetta-to come a basso rischio (passaggio 4, figura 2.3; Le celle grigio scuro rappresentano le combinazioni del genotipo ad alto rischio, mentre le celle colorate di grigio chiaro rappresentano combinazioni a basso rischio. Le cel-le bianche rappresentano combinazioni del genotipo per cel-le quali non è stato osservato alcun dato). In questo modo, un modello per entrambi i casi ed i controlli è formato da un primo insieme di celle ad alto rischio e da un secondo insieme di celle a basso rischio. Questo consente di ri-durre il modello n-dimensionale ad un modello mono-dimensionale cioè ottenere una variabile con due classi di rischio multifattoriale etichettate come alto e basso rischio. Una volta che tutte le celle sono etichettate, il modello viene valutato stimando il suo errore di previ-sione (passaggi 5-6, figura 2.3). Questo processo viene ripetuto finché tutte le possibili combinazioni di parametri vengono elaborate.
In relazione alla descrizione dell’algoritmo, a partire da un dataset r di pazienti aventi c variabili genotipiche/fenotipiche, è possibile calcolare la
O c n ∗ N ∗ r (2.1) Il coefficiente binomiale rappresenta il numero di combinazioni da ve-rificare dell’algoritmo. Ogni combinazione è costituita da N attributi e per ogni combinazione, i parametri N di ogni paziente devono essere estratti e valutati.
Da questa analisi si nota che il parallelismo dei dati è enorme: non ci sono dipendenze tra le diverse combinazioni, quindi possono essere elabo-rate in parallelo; inoltre, anche i gruppi di righe possono essere trattati in modo indipendente aggregando i loro risultati parziali per poi calcolare la precisione finale del modello.
Data la natura combinatoria dell’algoritmo, il numero di variabili che influenzano il modello è generalmente limitato a un massimo di tre. Inol-tre, sia il numero di variabili genotipiche e fenotipiche, che il numero di casi e di controlli, è di solito limitato a poche centinaia a causa della comples-sità dell’algoritmo. Queste limitazioni sono inaccettabili dal punto di vista dell’accuratezza del risultato finale poiché limitando il numero di variabili all’interno del dataset, per ovviare al problema della complessità compu-tazionale dell’algoritmo riducendo i tempi di esecuzione, non si sfruttano le più recenti tecniche dei microarray che consentono il recupero di centi-naia di migliaia di variabili genotipiche in una sola analisi [46]. Alla luce delle considerazioni sopra riportate, le seguenti parti di questo lavoro si concentrano su come le recenti tecnologie hardware e tecniche di co-design possano essere sfruttate per accelerare il processo di identificazione del-le interazioni tra geni e fattori ambientali, che possono causare malattie genetiche multifattoriali comuni.
Capitolo 3
Concetti tecnologici
Questo capitolo descrive la grande diffusione nel mercato, in questi ul-timi anni, dei sistemi embedded. Tali sistemi elettronici di elaborazione a mi-croprocessore, progettati appositamente per una determinata applicazione, ovvero non riprogrammabili dall’utente per altri scopi, riescano a garanti-re elevate pgaranti-restazioni delle applicazioni in garanti-relazione ai costi dei disposi-tivi impiegati. Per ottenere tale risultato è necessario, in fase di progetta-zione del sistema, effettuare uno studio sul co-design che ricerca un giusto compromesso tra il partizionameto hardware e quello software.
3.1 I sistemi embedded
Negli ultimi anni i sistemi embedded hanno avuto una grande diffu-sione, sia in applicazioni industriali sia in applicazioni consumer, il loro massiccio utilizzo ne garantisce una continua evoluzione tecnologica e pre-stazionale. I sistemi embedded costituiscono una grossa percentuale, pros-sima al 98%, dei sistemi utilizzati al giorno d’oggi [47]. I dispositivi ultra-small come i telefoni cellulari o i cercapersone, i sistemi di controllo e mo-nitoraggio dei processi industriali, i dispositivi di domotica e i dispositivi
di elettronica di consumo come videocamere digitali, DVD player, console giochi e tanti altri, sono oggigiorno realizzati con piattaforme embedded.
Con il termine sistema embedded si intende tutti quei componenti elet-tronici a microprocessore progettati appositamente per una determinata applicazione, spesso tramite una piattaforma hardware costruita ad-hoc, integrati nel sistema che controllano e in grado di gestirne tutte o parte del-le funzionalità. La definizione di sistema embedded che segue del-le specifiche IEEE è la seguente: ”An Embedded Computer System: A computer system that is part of a larger system and performs some of the requirements of that system; for example, a computer system used in an aircraft or rapid transit system“ [48].
A differenza dei general-purpose, i sistema embedded hanno compiti pre-cisi, noti già durante la fase di sviluppo, che viene studiata ed effettuata in modo specifico grazie ad una combinazione tra hardware e software per ottenere le migliori prestazioni in relazione ai vincoli fisici e di progetto.
Figura 3.1: Processo di design: design classico e co-design
Per ottenere i migliori risultati in un sistema embedded è necessario trovare un giusto compromesso tra hardware e software in modo da ridurre
CAPITOLO 3. CONCETTI TECNOLOGICI 24
ai minimi termini l’utilizzo del o dei componenti hardware per ridurne lo spazio occupato, i consumi ed il costo di fabbricazione, mantenendo alte le prestazioni in relazione ai vincoli.
La progettazione dei sistemi embedded richiede la fusione dei paradig-mi di progettazione hardware con la progettazione software, che devono essere gestiti da una nuova metodologia (co-design) che fonda contempo-raneamente sia le tecniche del mondo hardware sia quelle del mondo soft-ware (vedi figura 3.1), in modo da creare un dispositivo che sfrutti appieno tutti i benefici offerti sia dal software che dall’hardware.
3.2 Co-Design
Esistono diverse definizioni per il software-hardware co-design in cui diversi aspetti vengono evidenziati.
Lockheed Martin definisce co-design come una considerazione
simulta-nea di hardware e software all’interno del processo di progettazione. Sottolinea che essa consiste nella co-sviluppo e co-verifica di hard-ware e softhard-ware attraverso l’uso della simulazione e/o emulazione [49].
Assimakopoulos afferma che le prestazioni di co-design di ingegneria per
la realizzazione di sistemi efficienti è possibile solo se durante tutto il ciclo di vita del prodotto, la comunicazione e l’interazione tra i team di sviluppo è continua e produttiva [50].
In conclusione il co-design hardware e software è una nuova metodolo-gia di progetto, che si contrappone alla metodolometodolo-gia classica, dove la realiz-zazione dell’hardware e del software viene fatta indipendentemente (vedi figura 3.1), per ottenere sistemi con i requisiti richiesti sfruttando le po-tenzialità dell’hardware e del software, attraverso una loro progettazione concorrente.
Il problema principale nell’analisi co-design è la gestione della grande quantità di informazioni coinvolte che rendono difficile ottimizzare tutti gli obiettivi di progetto, portando spesso alla realizzazione di prodotti il cui rendimento è inferiore a quello potenziale.
Il recente aumento dell’interesse per il co-design hardware/software è la causa dell’introduzione di strumenti di progettazione Computer Aided Design (CAD) per lo studio di co-design e dell’aspettativa che tali strumen-ti introducano soluzioni anche per i nuovi problemi di co-design, in modo tale da alzare la qualità dei progetti e accorciare i tempi di sviluppo dei prodotti.
Il co-design hardware/software è una disciplina complessa è quindi fondamentale seguire una metodologia che supporti la fase di progetta-zione del sistema.
3.2.1 Passi di progettazione
La progettazione di sistemi hardware/software prevede: la modellizza-zione, la verifica e l’implementazione.
Modellizzazione processo di pianificazione che descrive in modo
forma-le i requisiti di progetto producendo un modello hardware e soft-ware. Le fasi iniziali di definizione dei requisiti e delle specifiche devono essere fatte con l’apporto sia dei progettisti dei componen-ti hardware, sia dei progetcomponen-tiscomponen-ti dei componencomponen-ti software. Il processo di modellizzazione può essere effettuato tramite uno stile omogeneo o eterogeneo.
Utilizzando uno stile di modellizzazione omogeneo si utilizza un unico linguaggio di modellizzazione per rappresentare sia l’hardware che il software (per esempio, il linguaggio di programmazione C) o un formalismo grafico (per esempio, stateCharts, Specification and Description Language (SDL)o data flow models).
CAPITOLO 3. CONCETTI TECNOLOGICI 26
Legenda Specifica
Sintesi del Sistema
Compilazione Software ISA
Stima
Codice macchina Net lists
Software proprietario
Sintesi Hardware
Pianificazione Esecuzione Monitoraggio e controllo
Hardware proprietario
Figura 3.2: System Design
Il problema del partizionamento hardware/software può trovare so-luzione individuando quelle parti del modello meglio implementa-te in hardware e quelle meglio implementaimplementa-te in software. La sud-divisione può essere sia decisa dal progettista, con un raffinamento progressivo a partire dal modello iniziale o attraverso uno strumento CAD.
Utilizzando uno stile di modellizzazione eterogeneo, la partizione hardware/software è descritta dal modello stesso e i componenti hard-ware e softhard-ware devono essere espressi nei linguaggi corrispondenti. Tuttavia, i progettisti possono esplorare implementazioni alternative nello spazio delle soluzioni. Ad esempio, la prima release di un pro-dotto può avere una componente software considerevole (per ragioni di tempi di mercato e di flessibilità) mentre le successive release pos-sono realizzare parte di questo software in hardware (per ragioni di prestazioni e/o di costo).
Implementazione processo di esecuzione dove viene realizzato fisicamente
l’hardware e creato l’eseguibile software.
L’implementazione di un sistema hardware/software è costituita da numerose attività, le principali sono la sintesi hardware e la compilazio-ne software(vedi figura 3.2).
In relazione ai requisiti e alle specifiche individuate in fase di piani-ficazione viene determinata l’architettura del sistema da sviluppare ed eseguite due importanti attività: la progettazione dei componenti hardware e la progettazione dei componenti software. La progetta-zione hardware e software possono essere eseguite separatamente, ma è presente sempre un’azione di interfacciamento tra le due atti-vità, per assicurare il rispetto dei requisiti e dei vincoli di progetto, per effettuare delle operazioni di debugging, in modo tale da ridurre al minimo la possibilità di introdurre difetti, incongruenze o malfun-zionamenti. Al termine dell’implementazione hardware e software, si esegue l’integrazione dei componenti per ottenere il sistema finale. Terminata la fase di esecuzione con la realizzazione del prodotto fi-nale del progetto, si passa alla fase di monitoraggio e controllo con la verifica del prodotto.
Verifica processo di monitoraggio e controllo che si assicura che i vari
requi-siti vengano rispettati e non ci siano difetti all’interno del sistema che possano introdurre malfunzionamenti.
La complessità sempre più crescente dei sistemi fa sì che la fase di verifica risulti essere un passo fondamentale per assicurare la corret-tezza delle funzionalità implementate, e validare il prodotto in re-lazione alla soddisfazione dei requisiti pianificati. Inoltre, la verifica esamina vari aspetti dipendenti dal dominio d’applicazione del siste-ma ad esempio, la soddisfazione di obiettivi di prestazioni è
estre-CAPITOLO 3. CONCETTI TECNOLOGICI 28
mamente importante nella progettazione dei processori. La verifica delle prestazioni è spesso basata sulla co-simulazione hardware/soft-ware. D’altra parte, i controllori embedded possono dover soddisfare requisiti di prestazioni non stringenti, ma la correttezza delle opera-zioni deve essere soddisfatta sotto condiopera-zioni ambientali diverse, per assicurare la sicurezza e l’affidabilità del sistema.
Nel co-design assumono particolare importanza i processi di
partizio-namento hardware/software e il processo di scheduling.
3.3 Partizionamento hardware/software
Il partizionamento hardware/software è quella fase in cui si stabilisce quali funzionalità devono essere implementate da componenti hardware e quali da componenti software. Il problema del partizionamento assume un ruolo fondamentale nello sviluppo di un sistema, un errore o un ripensa-mento sulla suddivisione può far sì che il processo debba essere ripetuto con conseguenti impatti sui costi di progetto e tempi di sviluppo. Il parti-zionamento hardware/software dipende direttamente dai requisiti del si-stema, per questo motivo questa fase viene eseguita dopo la definizione delle specifiche e dei requisiti del sistema. Molte volte si effettua il parti-zionamento trattando quest’attività come un problema di programmazio-ne matematica, ma per sistemi complessi si può non avere una risoluzioprogrammazio-ne semplice e quindi ci si accontenta di procedimenti euristici.
3.3.1 Problema del partizionamento
Il problema del partizionamento [51] consiste nell’assegnare n oggetti O = {o1, ..., on} a m blocchi (chiamati anche partizioni) P = {p1, ..., pm}, in modo tale da soddisfare:
