Ricostruire la storia evolutiva: il problema dell'ordinamento per operazioni genomiche

Nella tesi si analizzano alcuni problemi d’ottimizzazione combinatoria in biologia computazionale legati al problema di ricostruire l’evoluzione di una specie tramite la valutazione della distanza genomica. Quest’ultima costituisce una misura delle mutazioni avvenute durante l'evoluzione delle specie, determinate da un fenomeno noto come riarrangiamento genomico: il cambiamento della disposizione dei geni sui cromosomi. La distanza genomica consiste, secondo il criterio della massima parsimonia comunemente adottato nell'ambito dello studio dell’evoluzione, nel minimo numero di riarrangiamenti necessari per passare da una specie ad un’altra.
Il problema di determinare la distanza genomica è stato formulato come problema d’ottimizzazione combinatoria da Kececioglu e Sankoff nel 1993. Essi considerano, per semplicità, un genoma P composto da un singolo cromosoma p. Un cromosoma p è una sequenza di geni che può essere rappresentata mediante una permutazione [p1, p2, …, pn] d’interi, dove ciascun intero pi rappresenta la posizione del singolo gene all’interno del cromosoma. Tale permutazione può essere segnata, in tal caso il segno + o – associato ad ogni elemento di p rappresenta l’orientazione del gene nel cromosoma.
Se consideriamo una coppia di genomi uni-cromosomici, P e S, dove P è rappresentato dalla permutazione p, e S è rappresentato dalla permutazione s, il problema di determinare la distanza genomica tra p e s, è quindi formulato come il problema di determinare la sequenza d’operazioni genomiche tramite le quali p può essere resa identica a s.
Le operazioni genomiche di base sono inserzione, delezione, inversione, trasposizione e traslocazione. Le prime due agiscono su un gene per volta, per questo motivo sono dette operazioni genomiche locali, le rimanenti sono operazioni che agiscono su più geni e per questo sono dette operazioni genomiche globali. Il problema di individuare la distanza genomica minima tra p e s può essere formulato come un problema d’ordinamento. Infatti, è possibile rietichettare la permutazione p trasformandola nella permutazione identica I (I= [1 2 … n], dove n è la lunghezza della permutazione). Poichè p e s hanno la medesima lunghezza e sono costituite dallo stesso insieme d’elementi base, {1, 2, …, n}, allora possiamo usare la rietichettatura utilizzata per p e trasformare s in una nuova permutazione s*. A questo punto il problema della minima distanza tra p e s si riduce al problema di calcolare il numero minimo di passi necessari per ordinare la permutazione s*, cioè trasformare s* nella permutazione identica. Nella presente tesi, per ogni tipo d’operazione genomica globale, inversione, trasposizione, e traslocazione, viene analizzato il problema associato d’ordinamento per inversione (SBR), ordinamento per trasposizione (SBT), e ordinamento per traslocazione (SBTL). Inoltre viene analizzato l’utilizzo di più operazioni globali usate simultaneamente per ordinare s*, questo è noto come il problema dell’ordinamento per inversione e trasposizione (SBRT).
Un primo obiettivo fondamentale della tesi è stato quello di analizzare la soluzione di questi problemi tramite algoritmi esatti o approssimanti. Si sono infatti confrontati tra loro diversi approcci algoritmici risolutivi, proposti in letteratura.
In diversi casi si sono dovuti analizzare algoritmi k-approssimanti, in quanto si è dimostrata l’intrattabilità di alcuni di questi problemi d’ordinamento (esempio (SBR)) oppure si congettura la non esistenza d’algoritmi efficienti per essi.
Un secondo obiettivo della presente tesi è stato quello di definire ed analizzare il problema d’ordinamento per inversione per un tipo particolare di cromosoma, il cromosoma circolare. Questo cromosoma è rappresentabile con una permutazione circolare c, cioè una permutazione dove l’elemento c1 e cn risultano contigui.
Poiché per questo tipo di cromosoma, il problema dell'ordinamento per operazioni genomiche non è stato ancora investigato nella letteratura informatica, nella tesi abbiamo dovuto innanzi tutto proporre una definizione adeguata di minima distanza per l’inversione. Quindi si è determinato un limite inferiore a tale distanza genomica sia per l’ordinamento per inversione che per trasposizione. Successivamente si è analizzato come sia possibile modificare gli algoritmi proposti in letteratura per risolvere i problemi d’inversione e trasposizione per cromosomi lineari, allo scopo di risolvere gli stessi problemi nel caso di cromosomi circolari.