UNIVERSITA’ DI MILANO-BICOCCA
LAUREA MAGISTRALE IN
BIOINFORMATICA
Corso di
BIOINFORMATICA: TECNICHE DI BASE
Prof. Giancarlo Mauri
Lezione 11
Distanza genomica
Introduzione
 Brassica Oleracea (cavolo) e Brassica Campestris (rapa): geni
mitocondriali per il 99% identici, ma in ordine molto diverso
 Nel cromosoma X dei mammiferi sono molto conservati i geni, ma
non il loro ordine
 Il confronto tra grandi porzioni di genomi può dare indicazioni
sull’evoluzione
 Si cercano quali operazioni possono trasformare un genoma in un
altro, spostando parti di genoma
2
Riarrangiamento genomico
Il riarrangiamento genomico è quel fenomeno per cui
alcune parti del genoma vengono duplicate e collocate
in posizioni lontane dalla loro origine
Operazioni possibili:

su un solo cromosoma

su due cromosomi
3
Riarrangiamento genomico
Operazioni su un solo cromosoma

Cancellazione


Inserimento


abcdefgh  abfedcgh
Trasposizione


abc  abbc, abcd  abcbd, abcd  acbcd
Inversione


ac  abc
Duplicazione (tandem o no)


abc  ac
abcd  acbd
Transversione
4
Riarrangiamento genomico
Operazioni su due cromosomi

Traslocazione
 scambio di “code”. Possibile solo se non si perde il centromero

Fusione
 due cromosomi si fondono

Fissione
 un cromosoma si divide in due
5
Riarrangiamento genomico con
inversioni
 Il problema studiato considera una sola tra le possibili
operazioni: l’inversione
 Dati due genomi si etichettano i geni che compongono il primo
con numeri crescenti da 1 a n. Il secondo genoma sarà
etichettato da una permutazione di {1,2,…,n}
 Un’inversione equivale al rovesciamento di una sequenza di numeri
6
Riarrangiamento genomico con
inversioni
Esempio
Genoma1:
1 2 3 4 5 6
Genoma2:
4 3 2 1 5 6
Genoma2 è stato ottenuto da Genoma1 tramite l’inversione del
segmento 1 2 3 4
7
Dal cavolo alla rapa
1
-5
4
-3
2
1
-5
4
-3
-2
1
-5
-4
-3
-2
1
2
3
4
5
8
Dal verme all’uomo
12 31 34 28 26 17 29 4 9 36 18 35 19 1 16 14 32 33 22 15 11 27 5 20 13 30 23 10 6 3 24 21 8 25 2
7
20 5 27 11 15 22 33 32 14 16 1 19 35 18 36 9 4 29 17 26 28 34 31 12 13 30 23 10 6 3 24 21 8 25 2
7
1 16 14 32 33 22 15 11 27 5 20 19 35 18 36 9 4 29 17 26 28 34 31 12 13 30 23 10 6 3 24 21 8 25 2
7
1 16 15 22 33 32 14 11 27 5 20 19 35 18 36 9 4 29 17 26 28 34 31 12 13 30 23 10 6 3 24 21 8 25 2
7
1 16 15 36 18 35 19 20 5 27 11 14 32 33 22 9 4 29 17 26 28 34 31 12 13 30 23 10 6 3 24 21 8 25 2
7
1 16 15 14 11 27 5 20 19 35 18 36 32 33 22 9 4 29 17 26 28 34 31 12 13 30 23 10 6 3 24 21 8 25 2
7
1 16 15 14 31 34 28 26 17 29 4 9 22 33 32 36 18 35 19 20 5 27 11 12 13 30 23 10 6 3 24 21 8 25 2
7
1 26 28 34 31 14 15 16 17 29 4 9 22 33 32 36 18 35 19 20 5 27 11 12 13 30 23 10 6 3 24 21 8 25 2
7
1 26 28 18 36 32 33 22 9 4 29 17 16 15 14 31 34 35 19 20 5 27 11 12 13 30 23 10 6 3 24 21 8 25 2
7
1 26 28 29 4 9 22 33 32 36 18 17 16 15 14 31 34 35 19 20 5 27 11 12 13 30 23 10 6 3 24 21 8 25 2
7
1 26 28 29 30 13 12 11 27 5 20 19 35 34 31 14 15 16 17 18 36 32 33 22 9 4 23 10 6 3 24 21 8 25 2
7
1 26 11 12 13 30 29 28 27 5 20 19 35 34 31 14 15 16 17 18 36 32 33 22 9 4 23 10 6 3 24 21 8 25 2
7
1 26 27 28 29 30 13 12 11 5 20 19 35 34 31 14 15 16 17 18 36 32 33 22 9 4 23 10 6 3 24 21 8 25 2
7
1 26 27 28 29 30 31 34 35 19 20 5 11 12 13 14 15 16 17 18 36 32 33 22 9 4 23 10 6 3 24 21 8 25 2
7
1 26 27 28 29 30 31 34 35 19 20 9 22 33 32 36 18 17 16 15 14 13 12 11 5 4 23 10 6 3 24 21 8 25 29
Distanza di inversione
Distanza di inversione tra le sequenze S1 e S2:
numero minimo di operazioni di inversione
necessarie per trasformare S1 in S2
Esempio:
S1
S2
1 2 3 4 5 6
1 2 3 4 5
1 4 3 2 5 6
1 4 3 2 5
1 4 6 5 2 3
1 4 6 5 2
6 4 1 5 2 3
6
6
d(S1,S2 ) = 3
3
10
Riarrangiamento genomico con
inversioni
INPUT:
una permutazione p dell’insieme {1,2,…,n}
OUTPUT:
la permutazione
identica è
distanza tra p e la permutazioneNB:
identica
I
I=1,2,…,n

Il problema è NP-hard

Esiste però la possibilità di approssimarlo
11
Riarrangiamento genomico con
inversioni
 Si definisca un breakpoint tra le posizioni i e i+1 di p se e
solo se
|p(i) - p(i+1)| ≠ 1
dove p(i) e p(i+1) sono gli elementi di p alle posizioni i e i+1
 La permutazione identica I non ha breakpoints, quindi il
riarrangiamento secondo I corrisponde all’eliminazione
dei breakpoints da p
 In generale ogni inversione toglie al più due breakpoint
 Ne segue che d(p)≥b(p)/2, dove d(p) è la distanza di p
da I e b(p) è il numero di breakpoints in p
12
L’euristica
Definizione:
una striscia in p è un sottointervallo massimale di p
senza breakpoints
 decrescente se formata da numeri in ordine
decrescente
Es: 7 9 6 5 4 3 8 1 2
 crescente se formata da numeri in ordine crescente
Es: striscia
7 9 6 di5 lunghezza
4 3 8 1 12è considerata decrescente
NB: una
13
L’euristica
while ci sono breakpoints in p do
begin
if c’è una striscia decrescente
then trovane una che riduca il numero di bp e invertila
(Lemma 1)
else1trova
inverti una
Lemma
- Se pe contiene
unastriscia
striscia crescente
decrescente, allora
esiste una inversione che riduce il numero di bp di almeno uno
(diventa decrescente; non aumenta i bp: Lemma 2)
Lemma 2 - ...
14
L’algoritmo
 Trovo la striscia decrescente con estremo più piccolo,
K
 Trovo K-1
 Inverto tutta la sequenza tra K e K-1

...... 7654........23.....--> ...... 765432..…

........23........... 7654..... --> ........234567........
15
Esempio
45321987  123549867  123459867 
 123459876  123456789
16
Riarrangiamento con permutazioni
con segno
 In questa versione del problema ogni numero è
dotato di segno (+ oppure -)
 Il segno cambia ogni volta che il numero è
contenuto in un intervallo di inversione
17
Riarrangiamento con permutazioni
con segno
 Il problema a differenza della versione priva di
segno non è NP-hard
 Esistono algoritmi risolutivi esatti in tempo
quadratico
18