• albero PQ
• complessita'
• permutazione
• ripetizione
• sequenze genomiche

Questo lavoro prende spunto dall'interesse dimostrato da biologi, matematici e informatici nei confronti dello studio del genoma, di grande importanza per la conoscenza delle caratteristiche della nostra specie e per comprendere i mutamenti avvenuti nel corso del tempo. L'interesse dimostrato nasce dalla consapevolezza che una maggiore conoscenza del funzionamento del genoma permette passi avanti nel settore della salute, ma anche in quello della biotecnologia, con forti ricadute economiche. Purtroppo, per quel che riguarda lo studio del genoma, si sa ancora poco del funzionamento di un'enorme quantità di sequenze.
Dopo aver introdotto le basi biologiche e alcune nozioni sulla complessità computazionale dei problemi che ci saranno utili in seguito, approfondiremo alcuni approcci biologici di tipo ``discovery'', ovvero orientati all'identificazione di sequenze reputate interessanti, secondo un qualche criterio assegnato a priori.
La difficoltà, nell'analisi genomica, è dovuta alla sua struttura in sequenze, delle quali si vuole stabilire il grado di ``rilevanza'' dal punto di vista biologico. Da qui nasce il concetto di regioni ``interessanti'', ovvero cluster di geni. Per essere trattati, i cluster, vengono interpretati come permutazioni di elementi distinti o stringhe con ripetizioni.
Per l'analisi del primo dei due casi, è stata proposta una classificazione tramite gli alberi PQ. Questa struttura dati però era già stata introdotta per trattare problemi legati alla ricerca e alla rappresentazione di permutazioni ammissibili su un insieme U (cioè tali che, data una collezione S di sottoinsiemi di U, gli elementi di ogni parte di S occorrono come sottosequenze consecutive). Nel terzo capitolo verranno introdotte alcune proprietà e alcuni esempi di problemi che sfruttano tale struttura per ottenere una soluzione in un tempo ``ragionevole'': la proprietà degli uni consecutivi, i grafi a intervalli, i grafi planari.
Nel caso, invece, di stringhe con ripetizioni, il problema diventa assai più elaborato.
Rivedremo le definizioni e i risultati introdotti per gli alberi PQ per analizzare affinità e differenze con il nuovo caso considerato. Per poterlo studiare meglio lo abbiamo generalizzato. Gli alberi PQ, infatti, risolvono il seguente problema: dato un insieme R, sia F l'insieme di alcune sue parti; gli alberi PQ permettono di dare una numerazione da 1 a |R| agli elementi di R in modo che ciascuna parte Qi in F contenga un intervallo di interi consecutivo.
Dunque, se anzichè un insieme abbiamo un multinsieme, il problema è: dato un multinsieme R, sia F l'insieme di alcune sue parti. È possibile fornire una numerazione da 1 a |R| degli elementi di R in modo che ciascuna parte in F contenga un intervallo di interi consecutivo?
Un problema simile (che va sotto il nome di SET-ORDERING(R, F, K) e che noi indicheremo brevemente SO(R, F, K)) era stato posto in precedenza: L.T.Kou si era chiesto se, dato un insieme finito R, una famiglia F di sottoinsiemi di R e un intero positivo k, esiste una stringa x di lunghezza k nell'alfabeto R tale che, per ogni insieme in F, c'è una sottosequenza consecutiva di x che contenga esattamente i suoi elementi. Per questo problema si può provare l' NP-completezza, vale a dire che fa parte di una classe di problemi per i quali non si conoscono o non si sanno sfruttare delle proprietà matematiche; per risolverli, quindi, si fà ricorso a procedimenti di tipo non deterministico. Lo stesso sappiamo fare nel caso di multinsiemi (MULTISET-ORDERING(R, F, K) ovvero MO(R, F, K)).
Il problema che noi ci siamo posti è molto simile a questo: noi abbiamo già la sequenza da ordinare, conosciamo la sua lunghezza e gli elementi che la compongono. Apportando delle restrizioni a MO(R, F, K) otterremo il nostro caso particolare. Infatti, dato un multinsieme, enumerare i suoi elementi in modo che tutti gli insiemi in F appaiano con elementi consecutivi, equivale a cercare una stringa di lunghezza |R| che usi tutti e soli gli elementi in R, e nella quale tutti gli insiemi in F appaiano con elementi consecutivi.
La tesi si conclude con la dimostrazione che anche questo problema è NP-completo.