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

 1 - Introduzione 
2
una nuova permutazione σ
*
. A questo punto il problema della minima distanza tra σ e pi 
si riduce al problema di calcolare il numero minimo di passi necessari per ordinare la 
permutazione σ
*
, cioè trasformare σ
* 
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 
σ
*
, 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 pi, cioè una permutazione dove l’elemento pi
1
 e pi
n  
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. 
1.2 La genetica: cromosomi, geni 
La genetica, come tutti sappiamo, è la scienza che studia l’ereditarietà. I suoi fondamenti 
sono stati posti attorno al 1850 da un monaco di nome Gregorio Mendel che coltivava 
piselli nel giardino del suo monastero in Moravia. 
Mendel ibridava i suoi piselli, incrociando piselli a grani gialli con piselli a grani verdi.         
I grani ottenuti alla prima generazione erano tutti gialli, carattere che egli definì 
dominante; i piselli così ottenuti producevano, una volta incrociati tra loro, un grano 
verde ogni tre grani gialli. Il carattere verde che ricompariva dopo essere stato “nascosto” 
nella generazione precedente, fu chiamato carattere recessivo. 
Ma il lavoro di Mendel fu dimenticato; fu Thomas Hunt Morgan, con i suoi colleghi della 
Columbia University che, durante gli anni della prima guerra mondiale, stabilì i principi 
fondamentali della genetica moderna. 
Gli esperimenti d’incrocio erano la base per lo studio dell’ereditarietà, occorreva dunque, 
un animale che si riproducesse rapidamente, con facilità e in gran numero. A questo 
scopo fu scelto il moscerino della frutta, la Drosophila. Infatti, se mettiamo due moscerini 
della frutta in una bottiglia da mezzo litro con un pezzetto di banana o d’altro cibo, in 
dieci giorni si ottengono circa cinquecento giovani moscerini. 
 1 - Introduzione 
3
Si ipotizzò che i meccanismi fondamentali dell’eredità, una volta studiati in questo 
animale, si sarebbero rivelati simili nelle altre specie; cosa che fu in seguito verificata. 
Gli studi proseguirono rapidamente ed apparve subito evidente che l’ereditarietà non è 
come qualcuno pensava un fenomeno di mescolamento in cui la prole mostra alcuni 
caratteri intermedi tra quelli dei due genitori; si trovò invece 
che l’ereditarietà è determinata da un insieme di quantità 
particolari, alle quali fu dato il nome di “geni”. Più 
precisamente per gene si intende quella quantità di sostanza 
molecolare che identifica un determinato carattere ereditario. 
Le ricerche effettuate nel laboratorio di Morgan, inoltre, 
permisero di individuare la posizione di questi geni 
nell’organismo. In ogni cellula c’è un nucleo che controlla le 
attività cellulari; dentro il nucleo c’è un certo numero di 
strutture lunghe ed esili chiamate cromosomi.  
Esperimenti d’incrocio provarono che i geni sono disposti 
linearmente lungo i cromosomi. Ogni cromosoma è costituito 
da una lunga molecola ad elica filiforme di un              
composto complesso il cui nome per intero è acido 
desossiribonucleico, abbreviato “DNA” (Fig. 1.1). 
 
Fig. 1.1   Acido dessosiribonucleico (DNA) 
E’ importante notare che i geni non solo controllano lo sviluppo dell’individuo giovane, 
dimostrando così la sua eredità, ma continuano a controllare le attività dell’animale 
durante tutta la vita.  
Ogni volta che una cellula si divide, ogni cromosoma è in grado di formare un esatto 
duplicato della sua intera struttura cosicché ogni cellula figlia riceve una dotazione 
completa. Ogni cellula del corpo non ha soltanto una serie completa di cromosomi, ma ne 
ha ben due che provengono da ciascun genitore 
Se non ci fossero variazioni nei geni questo sistema di cromosomi e di geni “in doppio” 
non sembrerebbe avere un gran significato. Ma ciascun gene nella serie può variare nel 
modo di esprimersi. Per esempio per il moscerino 
della frutta c’è un gene che è importante nello 
sviluppo delle ali. E’ ovvio che se ambedue i geni di 
questo paio sono del tipo “normale”, il moscerino 
presenterà ali normali; se tutti e due i componenti del 
paio di geni appartengono alla variante con “ali non 
sviluppate” avremo moscerini con ali non sviluppate. 
Se abbiamo un gene di un tipo e uno di un altro, allora 
di solito, una delle due varianti domina sull’altra, in 
questo caso il gene di “ala ben sviluppata” è 
dominante sull’altra. 
Fig.  1.2   La struttura del DNA 
Come abbiamo già detto Morgan iniziò lo studio della genetica negli anni della prima 
guerra mondiale; successivamente nel 1953 nel laboratorio di Cavendish di Cambrige in 
Inghilterra due studiosi: J. D. Watson e F. Crick scoprirono mediante la diffrazione con i 
 1 - Introduzione 
4
raggi X la struttura del DNA. Esso si rivelò una lunga catena, costituita da due eliche tra 
loro avvolte, composte da nucleotidi (Fig. 1.2). 
Un nucleotide può a sua volta essere scomposto in tre parti: 
• Una molecola di acido fosforico 
• Uno zucchero a 5 atomi di carbonio (ribosio o dessossiribosio) 
• Una base azotata. 
Le basi azotate che si trovano negli acidi nucleici sono 5: 
• Adenina  (A) 
• Guanina  (G) 
• Citosina  (C) 
• Timina    (T) 
• Uracile    (U) 
Le tre parti del nucleotide sono saldate insieme in quest’ordine: base – zucchero – acido 
fosforico. I vari nucleotidi che formano un acido nucleico sono uniti fra loro attraverso 
l’acido fosforico il quale si lega alle molecole di zucchero di due nucleotidi diversi che 
risultano così saldati insieme. 
Nella materia vivente ci sono due tipi di acidi nucleici: l’acido dessossiribonucleico 
(DNA) e l’acido ribonucleico (RNA). 
I due tipi di acidi differiscono per i seguenti caratteri: 
a) Lo zucchero contenuto nell’RNA è il ribosio, quello contenuto nel DNA è 
il desossiribosio, che ha un’atomo di ossigeno in meno. 
b) Le basi azotate contenute nell’RNA sono Adenina (A), Guanina (G), 
Citosina (C), Uracile (U); quelle contenute nel DNA sono Adenina (A), 
Guanina (G), Citosina (C), Timina (T). 
c) La molecola dell’RNA è formata da un’unica catena di nucleotidi; quella 
del DNA è formata da due catene attorcigliate l’una attorno all’altra come 
due cordicelle. 
Nel DNA la sequenza delle basi di una catena è legata a quella dell’altra, i biologi dicono 
che le sequenze delle due catene sono complementari. 
Infatti, ad una molecola di Adenina (A) di una catena, corrisponde sempre una molecola 
di Timina (T) nella catena complementare, ed ad una molecola di Guanina (G) in una 
catena, corrisponde sempre una molecola di Citosina (C) nella catena complementare 
posta esattamente allo stesso livello, in modo che fra le due basi affacciate si stabiliscono 
deboli legami chimici. Di conseguenza se la sequenza di una catena è                       
A T T C G C C T G A A A G … allora la catena corrispondente risulterà essere:              
T  A A  G  C G  G  A C  T  T  T  C … 
Un altro motivo per cui il DNA è molto importante è dato dal fatto che al suo interno 
sono depositate le istruzioni per fabbricare tutte le proteine dell’organismo e di 
conseguenza, poiché le altre molecole sono fabbricate attraverso reazioni chimiche 
catalizzate da enzimi e gli enzimi sono proteine, si può concludere che nel DNA di un 
 1 - Introduzione 
5
individuo sono contenute istruzioni sufficienti per fabbricare tutte le molecole di cui è 
formato. 
Il DNA può essere visto come un “codice cifrato” in cui ogni amminoacido è 
simboleggiato da un gruppo di tre basi consecutive: per esempio l’amminoacido glicina è 
composto dalle tre basi C C G, l’amminoacido arginina dalle 3 basi G C T. 
L’unione di più amminoacidi formano le proteine, la loro sintesi è un processo 
complicato, infatti, bisogna prendere gli amminoacidi giusti, allinearli nel modo previsto 
dalle istruzioni contenute nel DNA e infine formare tra loro dei legami peptidici. Tutta 
questa operazione può essere paragonata al montaggio di una macchina partendo dai 
pezzi staccati che devono essere riuniti insieme secondo un’istruzione dettagliata. 
Le proteine vengono fabbricate nel citoplasma ed è quindi necessario che le informazioni 
contenute nel DNA passino dal nucleo al citoplasma.  
Per questo, le istruzioni contenute nel DNA non vengono direttamente usate per la sintesi 
delle proteine. La sequenza di basi di una delle due catene di DNA viene “trascritta” in 
una sequenza di basi di una molecola di RNA, detto RNA messaggero.  
 
Fig.  1.3   Trasmissione dell’informazione 
L’RNA messaggero passa dal nucleo al citoplasma, dove si forma una vera linea di 
montaggio delle proteine che consente la sintesi di diverse catene polipeptidiche su 
un’unica molecola di RNA messaggero. Al montaggio delle proteine partecipano i 
ribosomi, granuli fatti di RNA e proteine. 
Ogni ribosoma è fatto di due pezzi: uno più piccolo che si lega all’RNA messaggero ed 
uno più grande che dà attacco alle molecole di RNA di trasferimento che arrivano dal 
citoplasma portando gli amminoacidi. Il ribosoma avanza lungo la molecola di RNA 
messaggero trasportando la catena polipeptidica già sintetizzata e fermandosi in 
corrispondenza di ogni gruppo di tre basi, per consentire la formazione del legame 
peptidico con il nuovo amminoacido portato dal suo RNA di trasferimento. 
Una volta completa, la molecola proteica si stacca dalla catena di montaggio. In questo 
modo una molecola di RNA messaggero può servire come stampo per un gran numero di 
molecole proteiche. Dopo un certo periodo di “funzionamento”, le molecole di RNA 
messaggero vengono demolite da enzimi presenti nel citoplasma. 
 1 - Introduzione 
6
1.3 Le mutazioni 
La molecola di DNA è notevolmente stabile, e su questa stabilità si fonda la continuità 
delle caratteristiche ereditarie. Alcune volte però anche il DNA contenuto in un gene può 
subire delle alterazioni, che si manifesta come la variazione del carattere che questo gene 
normalmente determina. Queste variazioni del materiale genetico vengono dette 
mutazioni. L’insorgere delle mutazioni è del tutto casuale e quindi imprevedibile. 
Possiamo paragonare una molecola di DNA ad un messaggio in cui ad ogni lettera 
corrisponde una terna di nucleotidi. Se in una delle parole si sostituisce a caso una lettera 
è piuttosto difficile che la nuova parola possa inserirsi logicamente in una frase 
preesistente. Analogamente, se in una molecola di DNA si sostituisce una base ad 
un’altra, l’enzima sintetizzato in base alle istruzioni contenute in quella molecola avrà un 
amminoacido al posto di un altro. 
Le mutazioni possono essere classificate: 
1. Geniche 
2. Cromosomiche 
3. Genomiche 
1. Le mutazioni geniche interessano un singolo gene (sostituzione, delezione, 
inserzione di una sola coppia di basi). 
Singoli geni possono mutare quando delle modificazioni compaiono 
spontaneamente o per effetto di fattori esterni. Poiché l’informazione genetica di 
un gene si trova in una sequenza di circa 2000 nucleotidi le mutazioni possono 
consistere in una sottrazione, in un’aggiunta o nella sostituzione di uno o più 
nucleotidi. 
La sostituzione di una sola base nucleotidica può avvenire utilizzando due 
tecniche diverse: 
a. Gli analoghi delle basi 
b. Trasformazione chimica di basi normali 
a. Se consideriamo una configurazione chimica analoga a quella delle basi 
naturali dei nucleotidi, questi analoghi possono essere incorporati al 
posto delle basi reali e provocare delle mutazioni. Mentre le basi naturali 
hanno una configurazione chimica molto stabile, gli analoghi possono 
presentarsi in forma enolica e chetonica, per cui viene modificata la 
scelta della base complementare al momento dell’appaiamento durante la 
sintesi del DNA. 
Il 5-bromo-uracile, per esempio, può sostituire la timina, nella forma 
chetonica si unisce all’adenina, mentre nella forma enolica si unisce alla 
guanina. Se la forma enolica compare al momento della duplicazione del 
DNA la catena complementare avrà una guanina al posto di un’adenina 
(errore di duplicazione) e nel ciclo questa guanina si appaierà con una 
citosina. Come risultato finale avremo una coppia C-G al posto di una 
coppia A-T e quindi si ha una mutazione. 
 
 1 - Introduzione 
7
b. Alcuni prodotti chimici agiscono direttamente sul DNA, altri invece 
come le acridine (ad esempio la proflavina) tolgono alcuni nucleotidi dal 
DNA introducendone altri e modificando tutta la sequenza (spostamento 
delle triplette), altri mutageni, per esempio l’idrossilammina e l’acido 
nitroso, agiscono su un solo nucleotide. 
Mediante la nitrosazione si ha una deamminazione, cioè una sostituzione 
del gruppo amminico con un –OH, e l’adenina, la citosina e la guanina si 
trasformano in ipoxantina, uracile e xantina. 
L’ipoxantina si comporta come la guanina, l’uracile come la timina e 
l’xantina non si appaia, determinando delle mutazioni letali. 
 
2. Le mutazioni cromosomiche rappresentano alterazioni più estese della struttura 
dei cromosomi. Esse possono essere suddivise in due grossi gruppi, a seconda 
che interessino un solo cromosoma o più cromosomi. 
Tra le prime si possono elencare: delezione, duplicazione, inversione e 
trasposizione. 
Tra le seconde si possono distinguere: traslocazione semplice, traslocazione 
doppia, traslocazioni multiple e inserzione. 
Radiazioni ionizzanti (ricche di energia) o sostanze particolari (per esempio 
iprite) possono provocare variazioni nell’ordine lineare dei geni lungo un 
cromosoma. Queste alterazioni della struttura di un cromosoma dipendono da una 
rottura e da una ristrutturazione anomala degli stessi cromosomi. Quasi sempre si 
ha a che fare con una perdita di un frammento cromosomico (delezione), per cui 
l’estremità spezzata o un segmento intermedio di un cromosoma non viene 
trasmessa alla cellula figlia. 
Se si tratta di frammenti molto piccoli tale delezione è letale solo nel caso in cui 
l’individuo sia omozigote, cioè un individuo che presenta nel suo patrimonio 
genetico alleli uguali per un determinato carattere, ma se i frammenti perduti 
sono sufficientemente lunghi, essa è letale anche nel caso di un individuo 
eterozigote, cioè un individuo che presenta nel suo patrimonio genetico alleli 
diversi che controllano un determinato carattere. 
Quando avviene un crossing-over tra cromosomi omologhi, cioè uno scambio di 
materiale genetico, in tratti non corrispondenti otteniamo una delezione nel primo 
cromosoma ed una duplicazione nel secondo. 
Se il frammento si riattacca ad un cromosoma non omologo o se due cromosomi 
non omologhi si scambiano un segmento, si parla di traslocazione. 
Infine, si può avere il fenomeno dell’inversione cioè il distacco ed il riattacco di 
un segmento cromosomico in direzione invertita. 
 
3. Le mutazioni genomiche consistono in alterazioni non della struttura ma del 
numero dei cromosomi. 
In questo gruppo di anomalie si distinguono le poliploidie e le aneuploidie. 
Con poliploidie si intende la presenza di un multiplo intero, superiore a due, di un 
insieme cromosomico aploide normale. Poiché nell’uomo quest’ultimo è 
costituito da 23 cromosomi, si possono osservare, in teoria, triploide 
corrispondenti alla presenza di 3x23 = 69 cromosomi, tetraploidie corrispondente 
alla presenza di 4x23=92 cromosomi. 
 1 - Introduzione 
8
Con il termine aneuploidie si definisce un insieme cromosomico in cui il numero 
di cromosomi varia di un’unità in più o in meno rispetto al normale. Si parla di 
trisomia quando il genoma dell’individuo ha un cromosoma in sovrannumero, 
ossia 47 cromosomi come ad esempio la trisomia 21, anche detta sindrome di 
Down. Si parla invece di monosomia quando l’individuo ha 45 cromosomi come 
ad esempio la sindrome di Turner caratterizzata dalla presenza di un solo 
cromosoma sessuale, il cromosoma X. 
1.4  Il problema biologico 
Tutte le piante e tutti gli animali hanno nelle loro cellule un determinato numero di 
cromosomi, diverso per ogni specie, che rimane costante in tutte le cellule dell’organismo 
ad eccezione dai gameti in cui il numero cromosomico è la metà esatta di quello            
delle altre cellule. Il numero di cromosomi contenuti nel nucleo dei gameti si chiama 
aploide o “n”. Questi “n” cromosomi sono tutti diversi tra loro, essendo portatori di 
caratteri ereditari differenti. L’insieme dei cromosomi viene detto genoma. 
Il problema che vogliamo affrontare è quello dell’evoluzione, cioè se le specie diverse 
esistenti oggi sulla terra, siano il frutto di mutazioni avvenute nei millenni precedenti su 
genomi presenti all’inizio dei tempi. 
 
 
Fig.  1.4   L'albero evolutivo 
L’evoluzione viene solitamente rappresentata tramite un albero, al quale viene aggiunto 
un ramo ogni qualvolta, grazie ad una nuova mutazione, si forma una nuova specie: 
questo albero è denominato albero evolutivo (Fig. 1.4). 
In particolare il cambiamento della disposizione dei geni sui cromosomi, noto come 
riarrangiamento genomico, è uno dei fenomeni legati al processo evolutivo descritto negli 
alberi evolutivi e che spiega la vicinanza in tali alberi di specie diverse. 
 1 - Introduzione 
9
Se consideriamo due specie molto differenti come il topo e l’uomo e percorriamo a 
ritroso l’albero evolutivo, ci rendiamo conto che geneticamente risultano essere molto 
simili.  
Nel 1984 Nadeu e Taylor stimarono con sorpresa che non ci sono molte mutazioni tra 
l’uomo e il topo, e si riuscì a stabilire che essi si divisero geneticamente circa 80 milioni 
di anni fa.  
Il minimo numero di riarrangiamenti necessari per passare da una specie ad un’altra è 
denominato distanza evolutiva. Questa evoluzione è un’evoluzione parsimoniosa poiché 
consideriamo la distanza fra due specie come il minimo numero di mutazioni per passare 
dalla prima alla seconda. 
Se pensiamo di paragonare una sequenza di geni ad una parola, allora la distanza 
evolutiva può essere paragonata al numero di lettere sostituite necessarie per passare da 
una parola ad un’altra, aventi entrambe un significato ben preciso. 
Esempio 
Tonno →  Tondo →  Fondo 
Quindi la distanza tra “Tondo” e “Fondo” è due. 
1.5 La rappresentazione dei cromosomi 
Il problema di confrontare le mappe fisiche di specie diverse, allo scopo di individuare 
una storia evolutiva descritta da un possibile riarrangiamento genomico, è stato formulato 
come problema combinatorio da Kececioglu e Sankoff nel 1993. 
Essi hanno pensato di considerare per semplicità un genoma uni-cromosomico, ovvero un 
genoma formato da una sola coppia di cromosomi, quindi il genoma Γ è costituito da un 
solo cromosoma, σ. A sua volta un cromosoma σ è una sequenza di geni e quindi 
ciascuna sequenza, può  essere  rappresentata  mediante una permutazione [σ
1
, σ
2
, …, σ
n
] 
di interi, dove ciascun intero σ
i
 rappresenta la posizione del singolo gene all’interno del 
cromosoma. 
La permutazione identità,  risulta essere: 
I = [1, 2, ……, n] 
Nella realtà biologica, più rilevante è il caso delle permutazioni segnate, infatti, i geni 
sono frammenti “direzionati” del DNA e una sequenza in un genoma è rappresentata da 
una permutazione su {1, 2, ……, n} con segno + o – associato ad ogni elemento di σ. La 
permutazione identità in questo caso risulta essere: 
I
*
 = [+1, +2, ……, +n] 
Esempio: 
Se consideriamo il seguente gene con segno positivo [A  C  T  A  G  A] allora 
il gene corrispondente con segno negativo risulta essere: [A  G  A  T  C  A]. 
 1 - Introduzione 
10
1.6 Le operazioni genomiche 
Le operazioni genomiche, necessarie per il riarrangiamento genomico, si dividono in: 
• Locali 
• Globali 
Le operazioni locali sono operazioni che agiscono su un solo gene, di queste fanno parte: 
inserzione e delezione, mentre le globali sono operazioni che agiscono su sequenze di 
geni, di queste fanno parte: inversione, trasposizione e traslocazione. 
• Inserzione: inserisce un gene nella sequenza considerata. 
5   3   2   4   1  5   3   2   4   6   1 
 
• Delezione: cancella un gene dalla sequenza considerata. 
5   3   2   4   1  3   2   4   1 
 
• Inversione:      inverte la posizione degli elementi di una sottosequenza. 
1  2  3  4  5  6  7  8  9  1  7  6  5  4  3  2  8  9 
 
• Trasposizione:  sposta una sottosequenza all’interno della sequenza stessa. 
1  2  3  4  5  6  7  8  9  6  7  8  9  1  2  3  4  5 
 
• Traslocazione: scambia il prefisso o il suffisso di una sequenza con il prefisso o 
il suffisso di un’altra sequenza. 
1  2  8  9  10  6  7  8  9  10 
6  7  3  4   5  1  2  3  4   5 
 
 1 - Introduzione 
11
1.7 Il riarrangiamento genomico ed i relativi problemi di 
ordinamento 
Generalmente, i biologi adottano il criterio della massima parsimonia, che ritiene 
l’evoluzione un processo in cui gli eventi più probabili hanno determinato il minimo 
numero di mutazioni. A tal fine si assume più precisamente come distanza genomica tra σ 
e µ il minimo numero di operazioni necessarie per trasformare σ in µ. Il problema di 
individuare la distanza genomica è trattato come un problema di ordinamento. Infatti 
trasformare la permutazione σ nella  permutazione µ equivale a rietichettare, tramite f, la 
permutazione  µ trasformandola nella permutazione identica: 
    µ
1  
µ
2  
…… µ
n
 
   f = 
1   2  ……  n 
Poiché σ e µ hanno la medesima lunghezza e sono costituite dallo stesso insieme di 
elementi base, {1, 2, …, n}, allora possiamo pensare di utilizzare la stessa rietichettatura  
e trasformare σ in σ
*
. A questo punto il problema si riduce a trasformare σ
*
 in I e quindi 
il problema della minima distanza si riduce al problema di calcolare il numero minimo di 
passi necessari per ordinare la permutazione σ
*
. 
Per esempio, se abbiamo σ = [3 2 4 5 1],  e µ = [4 1 5 3 2], possiamo rietichettare 
gli elementi delle permutazioni di modo che µ
*
 = I = [
    ]. E quindi  4 è 
rietichettato  con  
,  1 con , 5 con , 3 con  e 2 con . Con la stessa 
rietichettatura σ
*
 = [  
  ], e quindi trovare la distanza tra σ e µ è 
equivalente a trovare la sequenza minima di operazioni per ordinare σ
*
.   
Notiamo che σ
*
= µ
−1
⋅σ = [4 5 1 3 2], dove µ
-1
 è la posizione di i in µ, cioè 
l’elemento 1 in µ occupa la seconda posizione, l’elemento 2 in µ occupa la quinta 
posizione e così via, ed otteniamo µ
-1
=[2 5 4 1 3]. La distanza tra σ e µ è uguale 
alla distanza tra pi=µ
−1
⋅σ e I. 
Se consideriamo una permutazione pi, possiamo dire che la distanza tra I e pi è uguale alla 
distanza tra pi
-1
 e I. 
Per ogni operazione globale X, consideriamo il problema di determinare la sequenza più 
corta di X per ordinare la permutazione: tale problema sarà chiamato ordinamento per X. 
Dalle operazioni inversione, trasposizione, e traslocazione otterremo rispettivamente 
ordinamento per inversione (SBR), ordinamento per trasposizione (SBT), e 
ordinamento per traslocazione (SBTL). 
Si studia anche l’utilizzo di più operazioni globali usate simultaneamente per lo stesso 
problema di ordinamento:  ordinamento per inversione e trasposizione (SBRT). 
Per ogni problema SBX bisogna distinguere i due casi: 
• Sequenza senza segno 
• Sequenza con segno 
Quindi il problema SBX si trasforma  in USBX (ordinamento per X di una sequenza 
senza segno) e SSBX (ordinamento per X di una sequenza con segno).  
 1 - Introduzione 
12
1.7.1 Ordinamento per inversione  
In un primo tempo, l’ordinamento per inversione si limitava alle sequenze senza segno 
(USBR). La trattazione del USBR è iniziata nel 1982 da Watterson & al. [WEHM82], i 
quali, ipotizzando che i cromosomi erano di forma circolare, implementarono un 
algoritmo euristico. Successivamente, Kececioglu e Sankoff [KS93] nel 1993 iniziarono 
uno studio formale sulla complessità computazionale di questo problema e progettarono 
due algoritmi: il primo era un algoritmo 2-approssimante, mentre il secondo era un 
algoritmo esatto, che è applicabile solo per permutazioni di lunghezza limitata. Questo 
algoritmo sfrutta la tecnica branch and bound.  
Bafna e Pevzner nel 1993 [BP93], utilizzando l’approccio delle permutazioni segnate, 
progettarono un algoritmo 
7
/
4
-approssimante e Christie [CH98], nel 1998, presentò un 
algoritmo  
3
/
2
-approssimante. 
Per quanto riguarda il problema SSBR, nel 1993, Bafna e Pevzner [BP93] descrissero un 
algoritmo 
3
/
2
-approssimante. Successivamente, Hannenhalli e Pevzner nel 1995 [HP95b] 
hanno dimostrato che SSBR è risolvibile in tempo polinomiale che determina la distanza 
di inversione in O(n
4
), mentre Kaplan, Shamir e Tarjan, nel 1997, implementarono un 
algoritmo polinomiale che determina la distanza di inversione in O(n
2
) [KST97]. 
Caprara nel 1997 provò che il problema generale dell’ordinamento per inversione è          
NP-Hard [CA97a]. 
1.7.2 Ordinamento per trasposizione  
I primi a trattare il problema dell’ordinamento per trasposizione (SBT) sono stati Bafna e 
Pevzner nel 1995 [BP95]. Essi hanno introdotto l’importante concetto di grafo ciclico di 
trasposizione, e progettarono un algoritmo 
3
/
2
-approssimante. Guyer, Heath e Vergara nel 
1995 [GHV95] descrissero degli algoritmi euristici per l’ordinamento per trasposizione. 
Nel 1997 Meidanis, Walter e Diaz [MWD97a] implementarono un algoritmo per il 
calcolo della distanza di trasposizione tra una permutazione e la sua inversa. 
Successivamente Christie [CH98] ha implementato un algoritmo 
3
/
2
-approssimante, più 
semplice di quello di Bafna e Pevzner. 
1.7.3 Ordinamento per traslocazione  
Il problema della distanza di traslocazione (SBTL) è stato studiato per la prima volta da 
Kececioglu e Ravi nel 1995 [KR95], che progettarono un algoritmo 2-approssimante. 
Hannenhalli [HA95a] descrisse un algoritmo polinomiale per l’ordinamento per 
traslocazione con segno. Più recentemente, El-Mabrouk, Bryant e Sankoff [EBS99] 
descrivono un algoritmo esatto. 
1.7.4 Ordinamento per inversione e trasposizione  
Questo è un tipo di problema che utilizza due tipi di operazioni globali: l’inversione e la 
trasposizione. 
Gu, Peng, Sudborough [GPS96] hanno implementato un algoritmo 2-approssimante per 
questo problema. 
 1 - Introduzione 
13
 
1.8 I cromosomi circolari 
Il capitolo 6 di questa tesi è dedicato ai cromosomi circolari, cioè un cromosoma che si 
forma quando si verifica una rottura seguita dalla perdita di sostanza (delezione) alle due 
estremità del cromosoma stesso, queste successivamente si saldano tra loro realizzando 
una struttura ad anello. Questo tipo di cromosoma è tipico dei procarioti (cioè organismi 
che sono costituiti da cellule che non hanno un nucleo delimitato da una membrana e il 
cui citoplasma è privo di mitocondri, organuli cellulari che servono come sorgente di 
energia della cellula). 
Nel 1994 Kececioglu e Sankoff [KS94] implementarono un algoritmo per l’ordinamento 
per inversione in un cromosoma circolare orientato.  
Nel capitolo 6, introdurremo innanzi tutto una nuova definizione di breakpoint e 
adiacenza, sia per il problema dell’ordinamento per inversione che per il problema 
dell’ordinamento per trasposizione e per ognuno di questi determineremo un limite 
inferiore per la distanza genomica. Infine analizzeremo come è possibile dare una 
rappresentazione di permutazioni lineari in termini di permutazioni circolari, valutando la 
relazione tra la distanza genomica nel primo e nel secondo tipo di rappresentazione del 
cromosoma. 
  
In questo capitolo analizzeremo il problema dell’ordinamento per inversione.  
• Per prima cosa, introdurremo le definizioni basilari per la trattazione del 
problema dell’ordinamento per inversione (Par. 2.1), successivamente 
introdurremo la nozione di grafo d’inversione, che è lo strumento 
fondamentale per la trattazione dei vari algoritmi che vedremo in seguito       
(Par. 2.2). 
• Presenteremo alcuni algoritmi per ordinare le permutazioni senza segno. Più 
precisamente analizzeremo l’algoritmo 2-approssimante e l’algoritmo branch 
and bound entrambi implementati da Kececioglu e Sankoff (Par. 2.3.1 e 2.3.2) 
ed infine analizzeremo l’algoritmo 
2
3
-approssimante recentemente 
implementato da Christie (Par. 2.3.3). 
• Presenteremo due algoritmi per ordinare le permutazioni con segno. Più 
precisamente analizzeremo l’algoritmo 
2
3
-approssimante implementato da 
Bafna e Pevzner (Par. 2.4.1) e l’algoritmo polinomiale implementato da 
Pevzner e Hannenhalli (Par. 2.4.2). 
2.1 Definizioni 
Data una permutazione pi di lunghezza n, l’inversione ρ = ρ(i, j) (dove 1≤ i < j ≤ n) 
trasforma pi in pi⋅ρ = [pi
0
 … pi
i-1
 pi
j
 … pi
i
 pi
j+1
 … pi
n+1
], più precisamente, questa operazione, 
inverte le posizioni degli elementi pi
i
 … pi
j
. 
La distanza di inversione, d(pi), tra pi ed I è il numero minimo di inversioni necessarie per 
trasformare pi in I. L’ordinamento per inversione è il problema di trovare una sequenza 
di inversioni di lunghezza d(pi) che ordina pi. Definiamo ora cosa si intende per 
breakpoint e adiacenza. 
 
 2 – Ordinamento per inversione 
 
15
Una coppia (pi
i
, pi
i+1
), con ni0 ≤≤ , è un breakpoint (che indicheremo con pi
i
 
 pi
i+1
) se: 
 
|pi
i 
- pi
i+1
| ≠ 1 
 
mentre, diremo che la coppia (pi
i
, pi
i+1
) è una adiacenza (che indicheremo con pi
i+1 
~ pi
i
) se: 
 
|pi
i 
- pi
i+1
| = 1 
 
Il numero di breakpoint è identificato con b(pi). Ogni inversione agisce su due breakpoint 
alla volta e di conseguenza il numero di breakpoint può diminuire di al più due unità, per 
questo vale il seguente limite inferiore:                   
2
)(b
)(d
pi
≥pi  
2.2 Il grafo di breakpoint 
Il grafo di breakpoint, G(pi), è un grafo ad archi colorati formato da n+2 vertici,               
{pi
0
, pi
1
, …, pi
n
, pi
n+1
}, dove pi
0
 = 0 e pi
n+1
 = n+1. 
Due vertici, pi
i
 e pi
j
, sono connessi da un arco nero, se la coppia (pi
i
, pi
j
) è un breakpoint, 
mentre pi
i
 e pi
j
 sono connessi da un arco grigio, se la coppia (pi
i
, pi
j
) è un’adiacenza, e pi
i
 e 
pi
j
 non sono consecutivi.  
Un ciclo di G(pi) è detto alternato se due archi consecutivi hanno colori distinti. La 
lunghezza di un ciclo C, l(C), è data dal numero di archi neri in C. Notiamo che G(pi) è un 
grafo bilanciato, qualunque sia la permutazione pi. Per questa ragione, esiste un ciclo 
Euleriano alternato per ogni componente connessa di G(pi) e di conseguenza la massima 
decomposizione in cicli disgiunti è unica. Il numero massimo di cicli disgiunti è indicato 
con c(pi). Come abbiamo già detto in precedenza b(pi) è il numero d’archi neri 
(breakpoint), a(pi) è il numero d’archi grigi (adiacenze) in G(pi). Determinata 
un’inversione ρ, definiamo con ∆b(pi, ρ)=b(pi⋅ρ)–b(pi), la variazione del numero di 
breakpoint, con ∆a(pi, ρ)= a(pi⋅ρ)–a(pi), la variazione del numero d’adiacenze e con        
∆c(pi, ρ)= c(pi⋅ρ)–c(pi), la variazione del numero di cicli in G(pi). Per ogni inversione si 
avrà: 
∆b(pi)  ∈ { - 2  -1   0   1   2} 
 
Ad esempio, data la permutazione 
 
pi = [3   5   1   4   2] 
 
la massima decomposizione in cicli di G(pi) risulta essere: 
            0          3          5          1          4          2          6 
 
 
Il massimo numero di cicli disgiunti, c(pi) = 2.