Redisposizione Genomica
Gotzone Ortega
Bioinformatica
2008/2009
INTRODUZIONE

Due genomi hanno gli stessi geni ma in diverso
ordine  Sono diversi



Ordinare uno dei genomi  Sono uguali



A {x, y, z}
B {x, z, y}
A {x, y, z}
B {x, y, z}
Capire come i genomi hanno evoluto.

“We know, for example, that human and mouse have a common ancestor.
If we can transform the genome of a mouse into the genome of a human,
then somewhere in the process, we should form the genome of our
common ancestor” Anne Bergeron.
GENI, CROMOSOME e
GENOMI

Gene: Si rappresenta con 2 estremi




Coda = Tail = estremo 3' = at
Testa = Head = estremo 5' = ah
Estremi adiacenti = adiacenze
{ah, bt}, {ah, bh}, {at, bt}, {at, bh}
Estremi no adiacenti = telomeri
{ah}, {at}

Cromosoma: Si rappresentano le adiacenze e i telomeri come vertici e si
uniscono. Un cromosoma è un componente del grafo

Genoma: Il grafo
GENI, CROMOSOME e
GENOMI
Esempio:
A={{at}, {ah, ct}, {ch, dh}, {dt}, {bh, et}, {eh, bt}, {ft},
{fh, gt}, {gh}}
7 geni = {a, b, c, d, e, f, g}

VERTICI


Grado 1  {p} = esterno
Grado 2  {p, q} = interno
COMPONENTI DEL GRAFO

Secondo il tipo di vertici



Circolare = Ciclo
Lineare = cammino
Secondo il numero di lati


Pari
Dispari
OPERAZIONE “DCJ”



DCJ = “Double Cut and Join”
“Doppio taglio e Unione”
Sopra 2 vertici di grado 1 o 2
3 modi:



(a) u={p, q}, v={r, s}  {p, r}, {s, q} | {p, s}, {q, r}
(b) u={p, q}, v={r}  {p, r}, {q} | {q, r}, {p}
(c) u={q}, v={r}  {q, r} *
OPERAZIONI

Vertici in diversi cammini





Vertici nello stesso cammino






Traslocazione
Identità
Fusione
Fisione
Inversione
Escisione
Integrazione
Circolarizzazione
Linearizzacione
Vertici in cicli



Inversione
Fusione
Fisione
VERTICI IN DIVERSI CAMMINI




Traslocazione
Identità
Fusione
Fisione
VERTICI NELLO STESSO
CAMMINO





Investimento
Scissione
Integrazione
Circolarizzazione
Linearizzazione
VERTICI IN CICLI



Investimento
Fusione
Fisione
DISTANZA DCJ

dDCJ (A, B) = Distanza DCJ tra A e B.
Sequenza più corta di operazioni DCJ per trasformare
A in B.
Esempio:
A = {{at}, {ah, ct}, {ch, dh}, {dt}, {bh, et}, {eh, bt}, {ft}, {fh, gt}, {gh}}
{{at},
{{et},
{{et},
{{et},
B = {{et},
{ah,
{ah,
{ah,
{ah,
{ah,
bt},
bt},
bt},
bt},
bt},
{ch,
{ch,
{ch,
{ch,
{ch,
dh}, {dt},
dh}, {dt},
dt}, {dh},
dt}, {dh},
dt}, {dh},
{bh,
{bh,
{bh,
{bh,
{bh,
et},
at},
at},
at},
at},
-Distanza DCJ tra A e B è dDCJ(A,B) = 5
{eh, ct}, {ft}, {fh, gt}, {gh}}
{eh, ct}, {ft}, {fh, gt}, {gh}}
{eh, ct}, {ft}, {fh, gt}, {gh}}
{eh}, {ct}, {ft}, {fh, gt}, {gh}}
{eh}, {ct}, {ft, gh}, {fh, gt}}
GRAFO DI ADIACENZA


A=B?
Se A<>B, trasformare A in B.
GRAFO DI ADIACENZA

Esempio:
A = {{at}, {ah, ct}, {ch, dh}, {dt}, {bh, et}, {eh, bt}, {ft}, {fh, gt}, {gh}}
B = {{ah, bt}, {bh, at}, {ct}, {ch, dt}, {dh}, {et}, {eh}, {fh, gt} , {gh, ft}}
Algoritmo 1 (Costruzione del grafo)
1:
2:
3:
4:
5:
6:
7:
8:
Creare un vertice por ogni adiacenza e ogni telomero in genomi A e B
for each adiacenzia {p, q} nel genoma A do
creare un ramo collegando {p, q} con il vertice del genoma B in ciu si trova p
creare un ramo collegando {p, q} con il vertice del genoma B in cui si trova q
end for
for each telomero {p} del genoma A do
creare un ramo collegando {p} con il vertice del genoma B in cui si trova p
end for
A=B?


A e B due genomi con lo stesso insieme di N geni.
A = B  N = C + I/2
(C = nº di cicli; I = nº di cammini dispari)
C=1
I=2
7=1+2/2
C=5
I= 4
7=5+4/2
TRASFORMARE A IN B
Algoritmo 2 (Redisposizione)
1: for each adiacenza {p, q} nel genoma B do
2: c’è u, un elemento del genoma A dove si trova p
3: c’è v, un elemento del genoma A dove si trova q
4: if u <> v then
5:
sostituire u e v in A per {p, q} y (u \ {p}) U (v \ {q})
6: end if
7: end for
8: for each telomero {p} nel genoma B do
9: c’è u, un elemento del genoma A dove si trova p
10: if u è una adiacenza then
11:
sostituire u in A por {p} y (u \ {p})
12: end if
13: end for
TRASFORMARE A IN B
Esempio:

Algoritmo 2 (Redisposizione)
1: for each adiacenza {p, q} nel genoma B do
2: c’è u, un elemento del genoma A dove si trova p
3: c’è v, un elemento del genoma A dove si trova q
4: if u <> v then
5:
sostituire u e v in A per {p, q} y (u \ {p}) U (v \ {q})
6: end if
7: end for
8: for each telomero {p} nel genoma B do
9:
c’è u, un elemento del genoma A dove si trova p
10: if u è una adiacenza then
11:
sostituire u in A por {p} y (u \ {p})
12: end if
13: end for
TRASFORMARE A IN B
Esempio:

Algoritmo 2 (Redisposizione)
1: for each adiacenza {p, q} nel genoma B do
2:
c’è u, un elemento del genoma A dove si trova p
3:
c’è v, un elemento del genoma A dove si trova q
4:
if u <> v then
5:
sostituire u e v in A per {p, q} y (u \ {p}) U (v \ {q})
6:
end if
7: end for
8: for each telomero {p} nel genoma B do
9: c’è u, un elemento del genoma A dove si trova p
10: if u è una adiacenza then
11:
sostituire u in A por {p} y (u \ {p})
12: end if
13: end for