La Bioinformatica e' unna disciplina nata per risolvere problemi biologici a livello molecolare usando l'Informatica. Le principali tecniche sono quelle di impiegare i concetti e i metodi informatici per acquisire e organizzare grandi quantitài informazioni, per esempio una sequenza genomica, offrire metodi automatici per analizzare i dati di rilevante interesse biologico, fornire modelli statistici validi per l'interpretazione dei dati provenienti da esperimenti di Biologia molecolare e Biochimica. L'analisi di sequenze, per esempio, e' stata resa possibile da diversi algoritmi specializzati e sono stati fatti alcuni studi tra cui il sequenziamento del DNA e l'allineamento di sequenze. Tra di essi, sono stati forniti algoritmi per la ricerca della stringa piu' lunga ripetuta in una sequenza, per individuare le sequenze che si ripetono in una data sequenza genomica.

L'argomento di tesi si colloca proprio in questa area. Una molecola di DNA e' una sequenza di nucleotidi. Tutti i nucleotidi sono costituiti da tre componenti fondamentali: un gruppo fosfato, il deossiribosio (zucchero pentoso) e una base azotata. Le basi azotate sono adenina, citosina, guanina e timina (A,C,G,T). Alla base della struttura della doppia elica del DNA c'e' un legame che rispetta il principio di complementarieta' Watson-Crick: ogni tipo di base presente su un filamento forma un legame con la base posta sul filamento opposto in modo che l'Adenina e' sempre legata con la Timina e la Citosina e' sempre legata con la Guanina. Astrarre il concetto di molecola di DNA significa rappresentare il singolo filamento come una sequenza di lettere (parola), in cui i nucleotidi sono identificati dalle loro basi.

Il lavoro di tesi ha riguardato il problema di trovare le parole assenti in un genoma, in modo da ottenere sottosequenze che non si legano a nessuno dei due filamenti di DNA dal momento che non si forma il legame tra le basi perche' la parola assente non e' complementare a nessuno dei fattori presenti nella sequenza. Le parole assenti potranno essere utilizzate in altre applicazioni ed essere utili per la ricerca, considerando l'approccio di Adleman in "G. Paun, G. Rozenberg, A. Salomaa: DNA Computing, new computing paradigms", i problemi NP-completi su grafi, ad esempio, come il cammino hamiltoniano, venivano risolti codificando i vertici con sequenze casuali di DNA e usando l'ibridazione che consente di legare tra loro i vertici. La codifica dei vertici casuale pero' non garantisce che il risultato finale della computazione sia corretto perche', data la struttura del DNA, potrebbero essere generati falsi positivi o negativi per errato accoppiamento delle basi. Da qui tutta una letteratura che studia codifiche buone anche da un punto di vista di linguaggi formali. Il calcolo delle unwords potrebbe intervenire in questa fase: data una sequenza, le sue unwords potrebbero essere inserite nella codifica senza provocare banali accoppiamenti. Le absent words genomiche non possono avere un significato funzionale, ma devono avere rilevanza nella pratica e nella teoria. In "C. Acquisti, D. Curtiss, S. Kumar, G. Poste: Nullomers: really a matter of natural selection, PLoS ONE 2007, 2(10)", gli autori descrivono la metilazione e la conseguente mutazione che favoriscono le unwords contenenti dinucleotidi CG e portano ad una sovrabbondanza delle loro varianti mutate. I nullomers sono brevi sequenze di DNA che sono assenti nel genoma degli esseri umani e di altre specie. Supponendo che i nullomers sono le firme della selezione naturale contro le sequenze deleteri negli esseri umani, l'uso di nullomers serve nello sviluppo di pesticidi, nel controllo ambientale e in altre applicazioni. Queste osservazioni suggeriscono che la lunghezza e il numero di unwords e in particolare la loro deviazione dalla aspettativa in sequenze casuali, sono impronte statistiche del processo di evoluzione del genoma reale.

Si e' studiato l'approccio di "J. Herold, S. Kurtz, R. Giegerich: Efficient computation of absent words in genomic sequences. BMC Bioinformatics 2008, 9:167" e l' implementazione in C. A differenza dei lavori precedenti, come "M. Abouelhoda, S. Kurtz, E. Ohlebusch: Replacing Suffix Trees with Enhanced Suffix Arrays. Journal of Discrete Algorithms 2004, 2:53.86", in cui gli autori descrivono la computazione efficiente di unwords utilizzando strutture dati a indice (e.g., alberi dei suffissi o un suffix array migliorato), non si usano strutture di appoggio per conservare la parola. Il fatto che la sequenza del genoma non ha bisogno di essere conservata in memoria rende il programma applicabile a volumi di dati ancora piu' grandi. Le absent words, per definizione, hanno sempre una lunghezza fissa (diciamo k) in un dato genoma. Calcolare parole assenti anche piu' lunghe, puo' essere interessante, ma possono essere facilmente determinate: bisogna aggiungere tutte le unwords come ulteriori sequenze del genoma e rieseguire il programma, produrra' tutte le parole assenti di lunghezza k + 1, dal momento che sono le unwords del genoma esteso.

L'algoritmo per il calcolo delle absent words inizia con una strategia di ricerca binaria per calcolare il valore di q (la dimensione della parola). Per ogni q-parola, letta dalla sequenza, viene calcolato un codice univoco con una particolare funzione di codifica (indicata con bar) che rispetta la codifica dei caratteri dell'alfabeto {a, c, g, t} considerando che sono mappati in questo modo: bar(a) = 0, bar(b) = 1, bar(c) = 2, bar(d) = 3 e la posizione i del carattere nella parola. Una volta calcolato il codice, si controlla la tabella di bit (bit table), dove ci sono 4q codici con un bit associato ad ogni codice. Inizialmente tutti i bit in tabella sono settati a 0. Se il bit corrispondente al codice calcolato e' 0, viene settato ad 1. Alla fine della lettura di sequenza, si controlla la situazione in tabella e il numero di entries 1 che corrispondono ai codici delle parole trovate nella sequenza. Se il numero di entries 1 e' minore del numero 4^q (tutte le possibili parole di lunghezza q), si continua la ricerca binaria per trovare un valore di q piu' piccolo, altrimenti se il numero di entries 1 e 4^q sono uguali, significa che non ci sono absent words per quel valore di q, si continua la ricerca binaria per cercare absent words piu' lunghe. Alla fine della ricerca binaria di q, si e' trrovato un valore tale che esistono absent words di dimensione q nella sequenza. L'ultima fase dell'algoritmo riguarda l'output: tutti i codici nella bit table che hanno i bit corrispondenti settati a 0, rappresentano i codici delle absent words. Dai codici, vengono costruite le parole con una opportuna funzione inversa di decodifica.

L'implementazione proposta e' in Java. Si inizia dalla ricerca binaria di q in entrambe le implementazioni (C e Java). In C, c'e' l'allocazione dei 4^q byte in memoria per la bit table (codice, bit) inizialmente tutti settati a 0, mentre in Java c'e' l'uso di una HashMap, inizialmente vuota. La lettura della sequenza avviene per singolo carattere in entrambe le implementazioni, lo spostamento della q-finestra di lettura in C viene implementato con operatori di bitwise shift mentre in Java lo spostamento di una q-finestra avviene con un ciclo for e l'incremento degli indici. Il codice della parola letta in C si calcola con operazioni bit a bit, mentre in Java il calcolo avviene con normali operazioni aritmetiche. In C, quando si arriva alla parola di lunghezza q nella sequenza, si calcola il codice e nella tabella si setta a 1 il bit corrispondente a quel codice mentre in Java si inserisce una entry (codice, occorrenze) nella mappa, se la parola letta occorre nella sequenza la prima volta, altrimenti si aggiorna soltanto il numero di occorrenze. Se ci sono absent words per q continua la ricerca binaria. In C per il salvataggio della bit table si copia la porzione di byte, allocata per la bit table, in un'altra area di memoria della stessa dimensione, mentre in Java si effettua il salvataggio della mappa in un'altra. Se non ci sono unwords per q, si recuperano i valori salvati in precedenza e si usano per il calcolo della absent words. In C si recuperano i valori di q e della bit table, si controllano tutte le entries 0, i codici con i bit settati a 0 si codificano e si stampano le absent words. In Java si recuperano i valori dei q e della mappa, tutte le entries nella mappa sono le parole incontrate nella sequenza, i codici non presenti nella mappa corrispondono alle absent words. Si passano i codici a una funzione di decodifica che calcola le parole assenti. Entrambe le soluzioni mostrano a video i risultati della computazione.