Multichromosomal genome
median and halving problems
E. Tannier C. Zheng D. Sankoff
Daniele Bevilacqua
Linda Orrù
I problemi analizzati
o
Median problem: Trovare il genoma G (mediano) che minimizza la
distanza tra genomi dati
o
Halving problem: Ricostruire il genoma originario prima della
duplicazione e la ricombinazione
o
Breakpoint problem: Individuare il numero di coppie consecutive tra
due permutazioni
Multichromosomal genome median and halving problems
2
Perché questi problemi?
Lo scopo è ricostruire i genomi antenati prima che gli eventi evolutivi
portassero alle attuali specie.
Attraverso lo studio e la comparazione di vari genomi è infatti possibile
individuare un antenato comune o trovare le mutazioni necessarie per
renderli simili, arrivando così a capire l’origine e l’evoluzione dei vari
organismi (filogenetica).
Ad esempio, è noto che l’uomo ed il topo sono geneticamente molto
simili, ed è stato stimato che essi si divisero geneticamente circa 80
Milioni di anni fa [Nadeu, Taylor, 1984]
Multichromosomal genome median and halving problems
3
Scopo dell’articolo
In questo articolo saranno studiati gli approcci ai vari problemi in casi
noti e la relativa complessità, riconducendo il problema biologico ad un
problema di assegnamento su un grafo, campo in cui l’informatica ha
validi strumenti per analizzare il problema.
Multichromosomal genome median and halving problems
4
Cenni di Biologia
DNA (acido deossiribonucleico): acido nucleico contenente le
informazioni genetiche necessarie alla sintesi di RNA e proteine,
indispensabili per lo sviluppo ed il funzionamento degli organismi
viventi.
Nell'ambito della bioinformatica è una stringa sull'alfabeto
{A,C,G,T}, che rappresenta le 4 basi azotate che lo costituiscono
(Adenina, Citosina, Guanina e Timina).
La disposizione in sequenza di queste quattro basi costituisce
l’informazione genetica.
Multichromosomal genome median and halving problems
5
Cenni di Biologia
Un gene è un segmento presente all’interno della molecola di DNA che
codifica una particolare informazione genetica.
Negli eucarioti il DNA si organizza all’interno del nucleo della cellula in
strutture chiamate cromosomi.
All’interno delle cellule degli esseri umani, ad esempio, ci sono 23
coppie di cromosomi.
Multichromosomal genome median and halving problems
6
Cenni di Biologia
Con cariotipo si indica la costituzione del patrimonio cromosomico di
una specie: per le cellule eucariote è dato dal numero e dalla
morfologia dei suoi cromosomi.
Il telomero è la regione terminale del cromosoma, composta da DNA
altamente ripetuto: non codifica alcun prodotto proteico ma ha lo scopo
determinante di evitare la perdita di informazioni durante la
duplicazione dei cromosomi.
Multichromosomal genome median and halving problems
7
Cenni di Biologia
Multichromosomal genome median and halving problems
8
L’evoluzione
Multichromosomal genome median and halving problems
9
L’evoluzione
L’evoluzione è il cambiamento del patrimonio genetico di una specie.
La mutazione consiste nella comparsa improvvisa, casuale ed
ereditabile nelle future generazioni, di caratteristiche non possedute
dagli antenati.
La ricombinazione genetica, che permette di creare nuove
combinazioni di caratteristiche ereditarie, può
aver luogo sia durante la meiosi (riproduzione
sessuata) sia per trasferimento di materiale
genetico da una cellula all’altra.
Sarà poi la selezione naturale a privilegiare il
successo riproduttivo di organismi della stessa
specie con differenti caratteristiche, facendo sì
che la mutazione si diffonda, se è vantaggiosa.
Multichromosomal genome median and halving problems
10
Le mutazioni
Per gli scopi di questo articolo ci limiteremo alle mutazioni
cromosomiche.
Le mutazioni cromosomiche sono un’alterazione nella struttura dei
cromosomi, in genere conseguenza di errori durante la divisione
cellulare o la ricombinazione del materiale genetico (crossing-over).
Si dividono in:
o
o
o
Inversione
Traslocazione
Duplicazione
Multichromosomal genome median and halving problems
11
Le mutazioni: inversione
Tale mutazione consiste nella rottura del filamento di DNA in due punti.
Il frammento così ottenuto viene poi reincorporato all’interno del
cromosoma, ma viene invertito di orientamento.
Multichromosomal genome median and halving problems
12
Le mutazioni: traslocazione
Tale mutazione consiste in un errato scambio di parti dei cromosomi
durante il riarrangiamento cromosomico. Sono molto importanti, come
tutte le mutazioni, nel ruolo dell’evoluzione sebbene questo tipo di
mutazione sia spesso molto dannosa.
Multichromosomal genome median and halving problems
13
Le mutazioni: duplicazione
Tale mutazione consiste nel raddoppiamento di un tratto del
cromosoma. Può essere il risultato di un crossing-over diseguale o
errato.
Multichromosomal genome median and halving problems
14
Formalismo utilizzato
Un gene A è quindi una sequenza ordinata di DNA, identificata da una
coda At ed una testa Ah.
Un’adiacenza è una coppia non ordinata di estremità. Un genoma è
quindi un insieme di adiacenze su un insieme di geni.
Un’adiacenza in un genoma significa che due estremità di un gene
sono consecutive in una molecola di DNA.
Ad esempio, sia Π il genoma definito sui geni {1..10}
{°2h,2t1h,1t9h,9tT,T10t,10h6h,6t4t,4h3h,3tT,T8t,8h5t,5h7t,7h°}
è il genoma lineare con tre cromosomi:
Π = { 2 1 9, 10 6 4 3, 8 5 7 }
Multichromosomal genome median and halving problems
15
Formalismo utilizzato
Sia Gp il grafo i cui vertici sono tutte le estremità dei geni e gli archi
rappresentano tutte le adiacenze del genoma Π unendo la testa e la
coda di ogni gene. Ogni componente connessa è un cromosoma di Π.
Un cromosoma è lineare se è un cammino, è circolare se è un ciclo.
Un genoma con un solo cromosoma è detto monocromosoma.
Un genoma con soli cromosomi lineari è detto genoma lineare.
Multichromosomal genome median and halving problems
16
Formalismo utilizzato
Un gene duplicato A è una coppia di
sequenze orientate omologhe di DNA,
identificate da due code A1t, A2t e due teste
A1h, A2h.
Un genoma all-duplicated Δ è un insieme di
adiacenze su un insieme di geni duplicati.
Ad esempio, il seguente genoma Δ rappresenta
un genoma all-duplicated sull’insieme dei geni
{1..5}
Δ={ 2 1 2 5, 4 3 4 1, 3 5 }
Multichromosomal genome median and halving problems
17
Formalismo utilizzato
Infine, per un genoma π su un insieme di geni G, un doubled-genoma
Π + Π è un genoma all-duplicated sull’insieme G tale che se AxBy è
un’adiacenza di Π, allora anche A1xB1y A2xB2y o A2xB1y A1xB2y sono
adiacenze di Π + Π.
Multichromosomal genome median and halving problems
18
Le distanze utilizzate
Per avere una misura della similarità di due genomi, quindi della loro
distanza, si utilizzano le seguenti misure:
o
Breakpoint distance
o
DCJ distance
o
Resersal/Translocation distance
Multichromosomal genome median and halving problems
19
Breakpoint distance
Dipende dalle adiacenze comuni, o meglio, alla loro assenza, nei
telomeri comuni a due genomi dati.
Siano Π e Γ due genomi rispettivamente con N Π e NΓ cromosomi. Sia
α il numero di adiacenze comuni, e ε il numero di telomeri comuni. La
Breakpoint distance sarà allora una formula del tipo:
dBP(Π, Γ)= n – αβ – εθ + (N Π + N Γ)γ + (|N Π – N Γ |)ψ
dove β, θ, γ e ψ sono i pesi dei vari parametri.
Multichromosomal genome median and halving problems
20
Breakpoint distance
Supponendo Π=Γ, quindi dBP(Π, Γ)= 0, si possono ricavare i valori
plausibili per i parametri di questa misura di distanza.
La formula finale della Breakpoint distance è quindi della forma
dBP(Π, Γ)= n – α – ε/2
Per un genoma all-duplicated Δ e un genoma ordinario Π, vale
dBP(Π ,Δ) = min (Π+ Π){dBP(Π+Π, Δ)}
Multichromosomal genome median and halving problems
21
Double-cut-and-join (DCJ) distance
Una double-cut-and-join (DCJ) è un’operazione R che agisce su due
adiacenze pq, rs di un genoma, avente l’effetto di mischiare le due
adiacenze, sostituendole con pr,qs oppure ps,qr.
Quindi, dati due genomi Π e Γ, la DCJ distance rappresenta il numero
minimo di operazioni DCJ (fusione, scissione, traslocazione)
necessarie per trasformare Π in Γ.
Per un genoma Δ all-duplicated e un genoma ordinario Π, la DCJ
distance vale dDCJ(Π, Δ) = min(Π+Π){dDCJ(Π+Π, Δ)}.
Multichromosomal genome median and halving problems
22
Reversal/Translocation distance
E’ l’equivalente della DCJ distance ma limitatamente ai soli genomi
lineari.
Durante le operazioni DCJ possono venirsi a creare delle situazioni
temporanee di cromosomi circolari: questa misura di distanza si limita
invece a considerare le sole operazioni che mantengono la linearità.
Quindi, dati due genomi lineari Π e Γ, la reversal/translocation distance
rappresenta il numero minimo di operazioni DCJ lineari necessarie per
trasformare Π in Γ.
Multichromosomal genome median and halving problems
23
Computational problems
o
o
o
o
o
Distance: dati due genomi Π e Γ, calcolare d(Π,Γ) e ricostruire gli
eventi che hanno differenziato i due genomi
Double distance: dato un genoma all-duplicated Δ e un genoma
ordinario Π, calcolare d(Δ, Π)
Median: dati tre genomi Π1, Π2 e Π3, trovare il genoma M che
minimizza d(Π1,M)+d(Π2,M)+d(Π3,M). Il median problem stima il
comune antenato dei genomi
Halving: dato un genoma all-duplicated Δ, trovare il genoma Π che
minimizza d(Δ ,Π). L’halving problem ricostruisce l’antenato di un
genoma all-duplicated al momento della sua duplicazione
Guided halving: dato un genoma all-duplicated Δ ed il genoma
ordinario Π, trovare il genoma ordinario M che minimizza
d(M,Π)+d(M,Δ). E’ simile al precedente, ma ipotizza la presenza di
un antenato comune con M
Multichromosomal genome median and halving problems
24
I cinque problemi appena presentati saranno discussi per le tre misure
di distanza introdotte, nel caso di genomi multicromosomici che
contengono cromosomi lineari.
Multichromosomal genome median and halving problems
25
Matching perfetto
Il genoma viene rappresentato come un grafo connesso.
I risultati che andremo ad esporre si basato sul concetto di matching
perfetto su grafo.
Dato un grafo G=(N,A), un matching M è un sottoinsieme di archi tale
che su ogni nodo di G incide al più
un solo arco di M.
Un matching si dice perfetto se ha
cardinalità pari a |N|/2
Multichromosomal genome median and halving problems
26
Breakpoint distance: distance, double distance
La computazione del problema della distance segue direttamente dalla
definizione, e può essere calcolata in tempo lineare.
Per la double distance è altrettanto semplice: sia ab è un’adiacenza nel
genoma ordinario. Allora, se a1b1 o a2b2 sono adiacenze nel genoma
all-duplicated, si sceglie a1b2 o a2b1 come adiacenze nel genoma
raddoppiato. I due casi sono mutuamente esclusivi, quindi non ci sono
ambiguità.
Multichromosomal genome median and halving problems
27
Breakpoint distance: median
Il problema è NP-completo per il caso dei genomi monocromosomici,
siano essi lineari o circolari.
Tuttavia, per il caso dei genomi multicromosomici vale il seguente
teorema:
Teorema 1
Esiste un algoritmo in tempo polinomiale per il multichromosomal
genome median problem
Multichromosomal genome median and halving problems
28
Breakpoint distance: median
Dimostrazione:
Siano Π1, Π2 e Π3 tre genomi su un insieme di geni ʛ, di lunghezza n.
Sia G il grafo completo il cui insieme dei vertici contiene gli estremi dei
geni in ʛ e un vertice supplementare tx per ogni estremità x del gene.
Per ogni coppia x,y, si pesa l’arco xy con il numero del genoma
(0,1,2,3) per cui xy è un arco. Poi per ogni vertice x si pesa l’arco xtx
con la metà del numero del genoma che ha x come telomero
(0,1/2,1,3/2). Tutti gli altri archi hanno valore 0.
Multichromosomal genome median and halving problems
29
Breakpoint distance: median
Dimostrazione (continua)
Sia M un perfect matching su G: gli archi tra le estremità dei geni
definiscono le adiacenze del genoma che possiamo indicare sempre
con M.
Il peso del perfect matching M vale esattamente
3n-(d(Π1,M)+d(Π2,M)+d(Π3,M))
Cioè, il problema del massimo perfect matching equivale è un
problema di minimo valore del mediano.
Dato che il problema del perfect matching è polinomiale, attraverso
questa riduzione è possibile risolvere il breakpoint median problem in
tempo polinomiale.□
Multichromosomal genome median and halving problems
30
Breakpoint distance: halving
Il problema non è ancora stato studiato. Per ottenere una facile
soluzione si possono combinare gli elementi del precedente teorema
con il calcolo della double distance.
Sia Δ il genoma all-duplicated su un insieme di geni ʛ, e sia G il grafo
costruito secondo i precedenti criteri: per ogni coppia x,y, si pesa l’arco
xy con (0,1,2) secondo quante volte l’adiacenza xy è presente in Δ, e si
pesa l’arco xtx con la metà della volte che x è un telomero in Δ. Tutti gli
altri archi hanno valore 0.
Il massimo peso del perfect matching su G definisce le adiacenze del
genoma M che minimizza d(Δ,M).
Multichromosomal genome median and halving problems
31
Breakpoint distance: guided halving
La soluzione, analogamente, combina gli elementi finora visti.
Sia Δ il genoma all-duplicated su un insieme di geni ʛ, e sia G il grafo
costruito secondo i precedenti criteri.
Gli archi sono pesati con il numero di volte che l’adiacenza xy è
presente sia in Δ che Π, e con la metà delle volte che x è un telomero
di entrambi i genomi. Tutti gli altri archi hanno valore 0.
Il massimo peso del perfect matching su G definisce le adiacenze del
genoma M che minimizza d(Δ,M)+d(M,Π).
Multichromosomal genome median and halving problems
32
Breakpoint distance lineare
Per i problemi qui analizzati considereremo solamente genomi lineari:
ciò permette una migliore modellazione dei genomi nucleari degli
eucarioti.
I risultati per la distance e la double distance sono analoghi al caso
precedente, dove erano ammesse circolarità; in contrasto con i risultati
appena mostrati però gli altri problemi risultano essere NP-complessi.
Multichromosomal genome median and halving problems
33
Breakpoint distance lineare: median
Teorema 2
Il problema del breakpoint median per i genomi lineari
multicromosomici è NP-complesso.
Per dimostrare questo teorema ci si basa sulla riduzione con il
problema delle permutazioni circolari mediane (CPM).
E’ noto che, dati tre genomi circolari Π1, Π2 e Π3 con un solo
cromosoma, trovare il genoma circolare M con un solo cromosoma che
minimizza d(Π1,M)+ d(Π2,M)+ d(Π3,M) è un problema NP-complesso
[Pe’er, Shamir, 1998]
Multichromosomal genome median and halving problems
34
Breakpoint distance lineare: median
Sia quindi Π1, Π2 e Π3 un’istanza del problema CPM su un insieme di
geni {1,…,n}. Sia n+1 un nuovo gene e sia Π’i il genoma costruito da Πi
dalla cancellazione dell’adiacenza x1t (dove x è l’estremità di un gene
in {2,…,n}), e aggiunge l’adiacenza x(n+1).
I genomi Π’1, Π’2 e Π’3 sono lineari. Sia poi k un intero positivo.
Allora esiste un genoma circolare multicromosomico M su {1,…,n} con
d(Π1, M) + d(Π2, M) + d(Π3, M) ≤ k se e solo se esiste un genoma
lineare e multicromosomico M’ su {1,…,n+1} con
d(Π’1, M) + d(Π’2, M) + d(Π’3, M) ≤ k.
Multichromosomal genome median and halving problems
35
Breakpoint distance lineare: halving, guided halving
Questi problemi non sono ancora stati trattati.
E’ possibile fare la congettura che esista una soluzione polinomiale,
dato che tali problemi per tutte le altre misure di distanza hanno una
soluzione polinomiale.
Tuttavia tentare di costruire una soluzione esula gli scopi di questa
presentazione, ed il problema rimane tutt’ora aperto.
Multichromosomal genome median and halving problems
36
DCJ distance: distance
Per questo problema si ha una facile soluzione lineare.
Il grafo breakpoint di due genomi Π e Γ, indicato con BP(Π,Γ), è un
grafo bipartito il cui insieme dei vertici è l’insieme delle estremità dei
geni.
I vertici in questo grafo hanno grado 0,1 o 2, così che il grafo è un
insieme di percorsi. Inoltre, è anche una valida rappresentazione
alternativa del grafo delle adiacenze.
Multichromosomal genome median and halving problems
37
DCJ distance: distance
Teorema 3
Per due genomi Γ,Π, sia c(Γ,Π) il numero di cicli di un grafo breakpoint
BP(Γ,Π) e sia p(Γ,Π) il numero di percorsi.
Allora vale
d(Γ,Π) = n – c(Γ,Π) – p(Γ,Π)/2
Si noti la somiglianza di questo risultato con la generale breakpoint
distance: esse differiscono nel modo in cui contano i cicli non semplici
ed i percorsi, ma per genomi molto distanti tra loro tendono a dare gli
stessi risultati.
Multichromosomal genome median and halving problems
38
DCJ distance: double distance
Teorema 4
Il problema DCJ double distance è NP-completo per genomi
multicromosomici.
Per dimostrarlo, ci si riduce al problema breakpoint graph
decomposition (BGD). Un grafo G è bicolore se tutti i suoi archi sono
rossi o blu.
E’ bilanciato se ogni vertice ha grado 2 o 4, ogni vertice è inerente dallo
stesso numero di percorsi rossi e blu e non ci sono cicli formati da archi
solo rossi o solo blu.
Multichromosomal genome median and halving problems
39
DCJ distance: double distance
Sia G un grafo bilanciato bicolore su n vertici, che definisce un’istanza
del problema BGD. Si definisce l’insieme del gene G come l’insieme
dei vertici in G.
Si costruisce un genoma all-duplicated Δ ed un genoma Π su G nel
seguente modo:
per ogni vertice x di G, alle estremità xtxh corrisponde un’adiacenza in
Π. Per ogni vertice x di G siano poi x1tx1h,x2tx2h le estremità del gene
duplicato x: per ogni arco blu xy in G si costruisce un’adiacenza in Δ
che unisce le teste dei geni x1 o x2 e y1 o y2.
Multichromosomal genome median and halving problems
40
DCJ distance: double distance
Se il vertice ha grado 4, una delle due adiacenze definita da due archi
blu implica x1h e l’altra x2h.
Se invece ha grado 2, definisce l’adiacenza con x1h ed aggiunge
un’altra adiacenza x1t x2h in Δ.
Gli archi rossi seguono lo stesso principio, ma uniscono le code dei
geni.
Con questa costruzione Π è composto da n cromosomi circolari, uno
per ogni gene, e né Π né Δ hanno telomeri.
Il numero massimo di archi-disgiunti è uguale a 2n-d(Δ,Π).
Multichromosomal genome median and halving problems
41
DCJ distance: median
Teorema 5
Il problema DCJ median per geni multicromosomici è NP-complesso.
Si utilizza una riduzione della decomposizione di un grafo breakpoint
simile alla precedente. Sia G un grafo bilanciato bicolore su n vertici. Si
definisce l’insieme dei geni come l’insieme contenente un gene x per
ogni vertice di G con grado 2, e due geni x,y per ogni vertice di G con
grado 4
Si applica la seguente trasformazione
al grafo:
Multichromosomal genome median and halving problems
42
DCJ distance: median
Sia v un vertice di grado 2 in G: si sostituisce v con due vertici
etichettati dalle due estremità del gene associato x. L’arco blu diventa
incidente su v per xh, quello rosso in xt. Si aggiungono quindi due archi
Π1 e Π2 per collegare queste estremità.
Se v è un vertice di grado 4 si sostituisce con 4 vertici etichettati con le
4 diverse estremità e si aggiungono gli archi Π1, Π2 e Π3 per collegarle.
Π1, Π2 e Π3 definiscono genomi su ʛ privi di telomeri. Sia ω2 il numero
di vertici di Γ di grado 2, e sia ω4 il numero di quello di grado 4.
Allora esiste un genoma M tale che
d(M, Π1) + d(M, Π2) + d(M, Π3) ≤ ω2 + 3 ω4 – k
se e solo se esiste almeno un arco-disgiunto k alternando i cicli in G
Multichromosomal genome median and halving problems
43
DCJ distance: halving, guided halving
Questo problema ha una soluzione polinomiale.
Gli algoritmi che lo risolvono si basano su versioni semplificate
dell’algoritmo di El-Mabrouk e Sankoff [2003] sviluppato per la distanza
RT.
Teorema 6
Il problema del guided halving è NP-complesso per genomi
multicromosomici.
L’analisi di questi ultimi risultati è omessa dall’articolo, ma si basa su
riduzioni analoghe a quelle precedentemente osservate.
Multichromosomal genome median and halving problems
44
DCJ, Reversal/Translocation distance: linear case
I problemi median e halving possono essere ridefiniti in termini di
cromosomi esclusivamente lineari, ma il problema rimane tutt’ora
aperto.
Sono state proposte valide euristiche, specie in molti articoli recenti
[Zheng, Zhu, Sankoff, 2008] ma le loro complessità non sono ancora note.
Multichromosomal genome median and halving problems
45
Conclusioni
La seguente tabella riassume la complessità dei problemi analizzati in
questo articolo.
I “?” rappresentano congetture, mentre ”open” sta ad indicare che il problema è
ancora in fase di discussione.
Problema
distance Halving
double distance
Median
guided halving
Breakpoint uni
Breakpoint general multi
Breakpoint linear multi
P
P
P
Open
P
P?
P
P
P
NP
P
NP
Open
P
NP
DCJ uni
DCJ general multi
DCJ linear multi
P
P
P
P
P
Open
Open
NP
Open
NP
NP
NP?
Open
NP
NP?
RT uni
RT multi
P
P
Open
P
Open
NP?
NP
NP?
Open
NP?
Multichromosomal genome median and halving problems
46
Conclusioni personali
o
o
o
I problemi biologici sui genomi possono essere ricondotti a problemi
matematici su grafi, e studiati mediante l’uso di un calcolatore
Alcuni problemi sono efficientemente risolvibili, “facili”.
Altri sono intrattabili anche con l’utilizzo di computer, “difficili” con le
attuali strategie, quindi dimostrabilmente intrattabili.
Multichromosomal genome median and halving problems
47
Multichromosomal genome median and halving problems
48