Multichromosomal genome median and halving problems E. Tannier C. Zheng D. Sankoff Daniele...

Multichromosomal genome median and halving problems

E. Tannier C. Zheng D. Sankoff

Daniele Bevilacqua Daniele Bevilacqua Linda OrrùLinda Orrù

2Multichromosomal genome median and halving problems

I problemi analizzatiI problemi analizzati

o Median problem: Median problem: Trovare il genoma G (mediano) che Trovare il genoma G (mediano) che minimizza la distanza tra genomi datiminimizza la distanza tra genomi dati

o Halving problem: Halving problem: Ricostruire il genoma originario prima della Ricostruire il genoma originario prima della duplicazione e la ricombinazioneduplicazione e la ricombinazione

o Breakpoint problem: Breakpoint problem: Individuare il numero di coppie Individuare il numero di coppie consecutive tra due permutazioniconsecutive tra due permutazioni


Perché questi problemi?Perché questi problemi?

Lo scopo è ricostruire i genomi antenati prima che gli eventi evolutiviLo scopo è ricostruire i genomi antenati prima che gli eventi evolutivi

portassero alle attuali specie.portassero alle attuali specie.

Attraverso lo studio e la comparazione di vari genomi è infatti Attraverso lo studio e la comparazione di vari genomi è infatti possibilepossibile

individuare un antenato comune o trovare le mutazioni necessarie individuare un antenato comune o trovare le mutazioni necessarie perper

renderli simili, arrivando così a capire l’origine e l’evoluzione dei varirenderli simili, arrivando così a capire l’origine e l’evoluzione dei vari

organismi (organismi (filogeneticafilogenetica).).

Ad esempio, è noto che l’uomo ed il topo sono geneticamente moltoAd esempio, è noto che l’uomo ed il topo sono geneticamente molto

simili, ed è stato stimato che essi si divisero geneticamente circa 80simili, ed è stato stimato che essi si divisero geneticamente circa 80Milioni di anni fa Milioni di anni fa [[Nadeu, Taylor, 1984]Nadeu, Taylor, 1984]


Scopo dell’articoloScopo dell’articolo

In questo articolo saranno studiati gli approcci ai vari problemi In questo articolo saranno studiati gli approcci ai vari problemi in casiin casi

noti e la relativa complessità, riconducendo il problema noti e la relativa complessità, riconducendo il problema biologico ad unbiologico ad un

problema di assegnamento su un grafo, campo in cui problema di assegnamento su un grafo, campo in cui l’informatica hal’informatica ha

validi strumenti per analizzare il problema.validi strumenti per analizzare il problema.


Cenni di BiologiaCenni di Biologia

DNA (DNA (acido deossiribonucleicoacido deossiribonucleico): acido nucleico contenente ): acido nucleico contenente lele

informazioni genetiche necessarie alla sintesi di informazioni genetiche necessarie alla sintesi di RNARNA e e proteineproteine,,

indispensabili per lo sviluppo ed il funzionamento degli indispensabili per lo sviluppo ed il funzionamento degli organismi organismi

viventi.viventi.

Nell'ambito della bioinformatica è una stringa sull'alfabeto Nell'ambito della bioinformatica è una stringa sull'alfabeto

{A,C,G,T}, che rappresenta le 4 basi azotate che lo {A,C,G,T}, che rappresenta le 4 basi azotate che lo costituiscono costituiscono

((AdeninaAdenina, , CitosinaCitosina, , GuaninaGuanina e e TiminaTimina).).

La disposizione in sequenza di queste quattro basi La disposizione in sequenza di queste quattro basi costituiscecostituisce

l’l’informazione geneticainformazione genetica..



Un Un genegene è un segmento presente all’interno della molecola di è un segmento presente all’interno della molecola di DNA cheDNA che

codifica una particolare informazione genetica.codifica una particolare informazione genetica.

Negli Negli eucarioti eucarioti il DNA si organizza all’interno del nucleo della il DNA si organizza all’interno del nucleo della cellula incellula in

strutture chiamate strutture chiamate cromosomicromosomi..

All’interno delle cellule degli esseri umani, ad esempio, ci sono All’interno delle cellule degli esseri umani, ad esempio, ci sono 23 23

coppie di cromosomi.coppie di cromosomi.



Con Con cariotipocariotipo si indica la costituzione del patrimonio si indica la costituzione del patrimonio cromosomico di cromosomico di

una specie: per le cellule eucariote è dato dal numero e dalla una specie: per le cellule eucariote è dato dal numero e dalla

morfologia dei suoi cromosomi.morfologia dei suoi cromosomi.

Il Il telomerotelomero è la regione terminale del cromosoma, composta è la regione terminale del cromosoma, composta da DNA da DNA

altamente ripetuto: non codifica alcun prodotto proteico ma altamente ripetuto: non codifica alcun prodotto proteico ma ha lo scopo ha lo scopo

determinante di evitare la perdita di informazioni durante la determinante di evitare la perdita di informazioni durante la

duplicazione dei cromosomi.duplicazione dei cromosomi.


L’evoluzioneL’evoluzione


L’evoluzione è il cambiamento del patrimonio genetico di una L’evoluzione è il cambiamento del patrimonio genetico di una specie.specie.

La La mutazione mutazione consiste nella comparsa improvvisa, casuale ed consiste nella comparsa improvvisa, casuale ed ereditabile nelle future generazioni, di caratteristiche non ereditabile nelle future generazioni, di caratteristiche non

possedute possedute dagli antenati.dagli antenati.La La ricombinazione geneticaricombinazione genetica, che permette di creare nuove , che permette di creare nuove combinazioni di caratteristiche ereditarie, può combinazioni di caratteristiche ereditarie, può aver luogo sia durante la aver luogo sia durante la meiosimeiosi (riproduzione (riproduzione sessuata) sia per trasferimento di materiale sessuata) sia per trasferimento di materiale genetico da una cellula all’altra.genetico da una cellula all’altra.Sarà poi la selezione naturale a privilegiare il Sarà poi la selezione naturale a privilegiare il successo riproduttivo di organismi della stessasuccesso riproduttivo di organismi della stessaspecie con differenti caratteristiche, facendo sì specie con differenti caratteristiche, facendo sì che la mutazione si diffonda, se è vantaggiosa.che la mutazione si diffonda, se è vantaggiosa.

L’evoluzioneL’evoluzione


Le mutazioniLe mutazioni

Per gli scopi di questo articolo ci limiteremo alle mutazioni Per gli scopi di questo articolo ci limiteremo alle mutazioni

cromosomichecromosomiche..

Le mutazioni cromosomiche sono un’alterazione nella Le mutazioni cromosomiche sono un’alterazione nella struttura dei struttura dei

cromosomi, in genere conseguenza di errori durante la cromosomi, in genere conseguenza di errori durante la divisione divisione

cellulare o la ricombinazione del materiale genetico (cellulare o la ricombinazione del materiale genetico (crossing-crossing-overover).).

Si dividono in:Si dividono in:

o InversioneInversioneo TraslocazioneTraslocazioneo DuplicazioneDuplicazione


Le mutazioni: inversioneLe mutazioni: inversione

Tale mutazione consiste nella rottura del filamento di DNA in Tale mutazione consiste nella rottura del filamento di DNA in due punti. due punti.

Il frammento così ottenuto viene poi reincorporato all’interno Il frammento così ottenuto viene poi reincorporato all’interno del del

cromosoma, ma viene invertito di orientamento.cromosoma, ma viene invertito di orientamento.


Le mutazioni: traslocazioneLe mutazioni: traslocazione

Tale mutazione consiste in un errato scambio di parti dei Tale mutazione consiste in un errato scambio di parti dei cromosomi cromosomi

durante il riarrangiamento cromosomico. Sono molto durante il riarrangiamento cromosomico. Sono molto importanti, come importanti, come

tutte le mutazioni, nel ruolo dell’evoluzione sebbene questo tutte le mutazioni, nel ruolo dell’evoluzione sebbene questo tipo di tipo di

mutazione sia spesso molto dannosa.mutazione sia spesso molto dannosa.


Le mutazioni: duplicazioneLe mutazioni: duplicazione

Tale mutazione consiste nel raddoppiamento di un tratto del Tale mutazione consiste nel raddoppiamento di un tratto del

cromosoma. Può essere il risultato di un crossing-over cromosoma. Può essere il risultato di un crossing-over diseguale o diseguale o

errato.errato.


Formalismo utilizzatoFormalismo utilizzato

Un gene A è quindi una sequenza ordinata di DNA, identificata da Un gene A è quindi una sequenza ordinata di DNA, identificata da una una

coda coda AAt t ed una ed una testatesta A Ahh..

Un’Un’adiacenzaadiacenza è una coppia non ordinata di estremità. Un genoma è è una coppia non ordinata di estremità. Un genoma è

quindi un insieme di adiacenze su un insieme di geni.quindi un insieme di adiacenze su un insieme di geni.

Un’adiacenza in un genoma significa che due estremità di un gene Un’adiacenza in un genoma significa che due estremità di un gene

sono consecutive in una molecola di DNA.sono consecutive in una molecola di DNA.

Ad esempio, sia Ad esempio, sia ΠΠ il genoma definito sui geni {1..10} il genoma definito sui geni {1..10}

{°2{°2hh,2,2tt11hh,1,1tt99hh,9,9ttT,T10T,T10tt,10,10hh66hh,6,6tt44tt,4,4hh33hh,3,3ttT,T8T,T8tt,8,8hh55tt,5,5hh77tt,7,7hh°}°}

è il genoma lineare con tre cromosomi:è il genoma lineare con tre cromosomi:

ΠΠ = { = { 22 11 99, 10 , 10 66 4 4 33, 8 5 7 }, 8 5 7 }



Sia GSia Gpp il grafo i cui vertici sono tutte le estremità dei geni e gli il grafo i cui vertici sono tutte le estremità dei geni e gli archiarchi

rappresentano tutte le adiacenze del genoma rappresentano tutte le adiacenze del genoma ΠΠ unendo la unendo la testa e la testa e la

coda di ogni gene. Ogni componente connessa è un coda di ogni gene. Ogni componente connessa è un cromosoma cromosoma di di ΠΠ..

Un cromosoma è lineare se è un cammino, è circolare se è un Un cromosoma è lineare se è un cammino, è circolare se è un ciclo.ciclo.

Un genoma con un solo cromosoma è detto Un genoma con un solo cromosoma è detto monocromosoma.monocromosoma.

Un genoma con soli cromosomi lineari è detto Un genoma con soli cromosomi lineari è detto genoma linearegenoma lineare..



Un gene Un gene duplicatoduplicato A è una coppia di A è una coppia disequenze orientate omologhe di DNA, sequenze orientate omologhe di DNA,

identificate da due code Aidentificate da due code A1t1t, A, A2t2t e due teste e due teste

AA1h1h, A, A2h2h..

Un genoma Un genoma all-duplicated all-duplicated ΔΔ è un insieme di è un insieme di adiacenze su un insieme di geni duplicati.adiacenze su un insieme di geni duplicati.

Ad esempio, il seguente genoma Ad esempio, il seguente genoma ΔΔ rappresenta rappresentaun genoma un genoma all-duplicatedall-duplicated sull’insieme dei geni sull’insieme dei geni{1..5}{1..5} ΔΔ={ ={ 22 11 2 2 55, 4 , 4 33 4 4 11, 3 5 }, 3 5 }



Infine, per un genoma Infine, per un genoma ππ su un insieme di geni su un insieme di geni GG, un , un doubled-doubled-genomagenoma

ΠΠ + + ΠΠ è un genoma è un genoma all-duplicatedall-duplicated sull’insieme sull’insieme GG tale che se tale che se AAxxBByy è è

un’adiacenza di un’adiacenza di ΠΠ, allora anche A, allora anche A1x1xBB1y 1y AA2x2xBB2y 2y o Ao A2x2xBB1y 1y AA1x1xBB2y 2y

sono sono adiacenze di adiacenze di ΠΠ + + ΠΠ..


Le distanze utilizzateLe distanze utilizzate

Per avere una misura della similarità di due genomi, quindi Per avere una misura della similarità di due genomi, quindi della loro della loro

distanza, si utilizzano le seguenti misure:distanza, si utilizzano le seguenti misure:

o Breakpoint distanceBreakpoint distance

o DCJ distanceDCJ distance

o Resersal/Translocation distanceResersal/Translocation distance


Breakpoint distanceBreakpoint distance

Dipende dalle Dipende dalle adiacenzeadiacenze comuni, o meglio, alla loro assenza, comuni, o meglio, alla loro assenza, nei nei

telomeri comuni a due genomi dati.telomeri comuni a due genomi dati.

Siano Π e Γ due genomi rispettivamente con N Siano Π e Γ due genomi rispettivamente con N ΠΠ e N e NΓΓ cromosomi. Sia cromosomi. Sia

αα il numero di adiacenze comuni, e il numero di adiacenze comuni, e εε il numero di telomeri il numero di telomeri comuni. La comuni. La

Breakpoint distanceBreakpoint distance sarà allora una formula del tipo sarà allora una formula del tipo::

ddBPBP(Π, Γ)= (Π, Γ)= n – n – ααβ – β – εεθ + (Nθ + (N ΠΠ + N + N ΓΓ)γ + (|N)γ + (|N ΠΠ – N – N ΓΓ |)ψ |)ψ

dove dove β, θ, γ e ψ β, θ, γ e ψ sono i pesi dei vari parametri. sono i pesi dei vari parametri.


Breakpoint distanceBreakpoint distance

Supponendo Π=Γ, quindi dSupponendo Π=Γ, quindi dBPBP(Π, Γ)= 0, si possono ricavare i (Π, Γ)= 0, si possono ricavare i valori valori

plausibili per i parametri di questa misura di distanza.plausibili per i parametri di questa misura di distanza.

La formula finale della La formula finale della Breakpoint distanceBreakpoint distance è quindi della è quindi della formaforma

ddBPBP(Π, Γ)= (Π, Γ)= n – n – αα – – εε/2/2

Per un genoma Per un genoma all-duplicated all-duplicated Δ Δ e un genoma ordinario e un genoma ordinario Π, Π, vale vale

ddBPBP(Π ,Δ) = min (Π+ Π){d(Π ,Δ) = min (Π+ Π){dBPBP(Π+Π, Δ)}(Π+Π, Δ)}


Double-cut-and-join (DCJ) distanceDouble-cut-and-join (DCJ) distance

Una Una double-cut-and-join double-cut-and-join (DCJ) è un’operazione (DCJ) è un’operazione RR che agisce su che agisce su due due

adiacenze adiacenze pq, rs pq, rs di un genoma, avente l’effetto di mischiare le di un genoma, avente l’effetto di mischiare le due due

adiacenze, sostituendole con adiacenze, sostituendole con pr,qspr,qs oppure oppure ps,qrps,qr..

Quindi, dati due genomi Quindi, dati due genomi Π e Γ, la Π e Γ, la DCJ distanceDCJ distance rappresenta il rappresenta il numero numero

minimo di operazioni minimo di operazioni DCJDCJ (fusione, scissione, traslocazione) (fusione, scissione, traslocazione)

necessarie per trasformare Π in Γ.necessarie per trasformare Π in Γ.

Per un genoma Δ Per un genoma Δ all-duplicatedall-duplicated e un genoma ordinario Π, la e un genoma ordinario Π, la DCJ DCJ

distancedistance vale d vale dDCJDCJ(Π, Δ) = min(Π+Π){d(Π, Δ) = min(Π+Π){dDCJDCJ(Π+Π, Δ)}.(Π+Π, Δ)}.


Reversal/Translocation distanceReversal/Translocation distance

E’ l’equivalente della E’ l’equivalente della DCJ distance DCJ distance ma limitatamente ai soli ma limitatamente ai soli genomi genomi

lineari. lineari.

Durante le operazioni Durante le operazioni DCJ DCJ possono venirsi a creare delle possono venirsi a creare delle situazioni situazioni

temporanee di cromosomi circolari: questa misura di distanza si temporanee di cromosomi circolari: questa misura di distanza si limita limita

invece a considerare le sole operazioni che mantengono la invece a considerare le sole operazioni che mantengono la linearità.linearità.

Quindi, dati due genomi lineari Quindi, dati due genomi lineari Π e Γ, la Π e Γ, la reversal/translocation reversal/translocation distancedistance

rappresenta il numero minimo di operazioni rappresenta il numero minimo di operazioni DCJDCJ lineari necessarie per lineari necessarie per

trasformare Π in Γ.trasformare Π in Γ.


Computational problemsComputational problems

o DistanceDistance: dati due genomi Π e Γ, calcolare d(Π,Γ) e ricostruire gli : dati due genomi Π e Γ, calcolare d(Π,Γ) e ricostruire gli eventi che hanno differenziato i due genomieventi che hanno differenziato i due genomi

o Double distanceDouble distance: dato un genoma : dato un genoma all-duplicatedall-duplicated Δ Δ e un genoma e un genoma ordinario Π, calcolare d(ordinario Π, calcolare d(Δ, Δ, Π)Π)

o Median: Median: dati tre genomi Πdati tre genomi Π11, Π, Π22 e Π e Π33, trovare il genoma , trovare il genoma MM che che minimizza d(Πminimizza d(Π11,M)+d(,M)+d(ΠΠ22,M)+d(Π,M)+d(Π33,M). Il ,M). Il median problem median problem stima il stima il comune antenato dei genomicomune antenato dei genomi

o HalvingHalving: dato un genoma : dato un genoma all-duplicatedall-duplicated Δ, Δ, trovare il genoma Π che trovare il genoma Π che minimizza d(minimizza d(ΔΔ ,Π). L’ ,Π). L’halving problem halving problem ricostruisce l’antenato di un ricostruisce l’antenato di un genoma genoma all-duplicatedall-duplicated al momento della sua duplicazione al momento della sua duplicazione

o Guided halvingGuided halving: dato un genoma : dato un genoma all-duplicatedall-duplicated Δ Δ ed il genoma ed il genoma ordinario Π, trovare il genoma ordinario ordinario Π, trovare il genoma ordinario M M che minimizza d( che minimizza d(M,M,Π)Π)+d(+d(M,Δ)M,Δ). E’ simile al precedente, ma ipotizza la presenza di un . E’ simile al precedente, ma ipotizza la presenza di un antenato comune con antenato comune con MM


I cinque problemi appena presentati saranno discussi per le tre misure I cinque problemi appena presentati saranno discussi per le tre misure

di distanza introdotte, nel caso di genomi multicromosomici che di distanza introdotte, nel caso di genomi multicromosomici che

contengono cromosomi lineari.contengono cromosomi lineari.


Matching perfettoMatching perfetto

Il genoma viene rappresentato come un grafo connesso.Il genoma viene rappresentato come un grafo connesso.I risultati che andremo ad esporre si basato sul concetto di I risultati che andremo ad esporre si basato sul concetto di matching matching perfetto su grafoperfetto su grafo..Dato un grafo Dato un grafo G=(N,A)G=(N,A), un , un matchingmatching M è un sottoinsieme di archi tale M è un sottoinsieme di archi tale che su ogni nodo di G incide al più che su ogni nodo di G incide al più un solo arco di M.un solo arco di M.Un matching si dice perfetto se haUn matching si dice perfetto se ha cardinalità pari a cardinalità pari a |N|/2|N|/2


Breakpoint distance: distance, double Breakpoint distance: distance, double distancedistance

La computazione del problema della La computazione del problema della distancedistance segue direttamente dalla segue direttamente dalla

definizione, e può essere calcolata in tempo lineare.definizione, e può essere calcolata in tempo lineare.

Per la Per la double distance double distance è altrettanto semplice: sia è altrettanto semplice: sia ab ab è un’adiacenza nel è un’adiacenza nel

genoma ordinario. Allora, se genoma ordinario. Allora, se aa11bb11 o a o a22bb22 sono adiacenze nel genoma sono adiacenze nel genoma

all-duplicatedall-duplicated, si sceglie a, si sceglie a11bb22 o a o a22bb11 come adiacenze nel genoma come adiacenze nel genoma

raddoppiato. I due casi sono mutuamente esclusivi, quindi non ci sono raddoppiato. I due casi sono mutuamente esclusivi, quindi non ci sono

ambiguità.ambiguità.


Breakpoint distance: medianBreakpoint distance: median

Il problema è NP-completo per il caso dei genomi monocromosomici, Il problema è NP-completo per il caso dei genomi monocromosomici,

siano essi lineari o circolari.siano essi lineari o circolari.

Tuttavia, per il caso dei genomi multicromosomici vale il seguente Tuttavia, per il caso dei genomi multicromosomici vale il seguente

teorema:teorema:

Teorema 1Teorema 1

Esiste un algoritmo in tempo polinomiale per il multichromosomal Esiste un algoritmo in tempo polinomiale per il multichromosomal

genome median problemgenome median problem



Dimostrazione:Dimostrazione:

Siano Siano ΠΠ11, , ΠΠ22 e e ΠΠ33 tre genomi su un insieme di geni ʛ, di lunghezza n. tre genomi su un insieme di geni ʛ, di lunghezza n.

Sia G il grafo completo il cui insieme dei vertici contiene gli estremi dei Sia G il grafo completo il cui insieme dei vertici contiene gli estremi dei

geni in ʛ e un vertice supplementare tgeni in ʛ e un vertice supplementare tx x per ogni estremità x del gene.per ogni estremità x del gene.

Per ogni coppia x,y, si pesa l’arco xy con il numero del genoma 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 xt(0,1,2,3) per cui xy è un arco. Poi per ogni vertice x si pesa l’arco xtx x

con la metà del numero del genoma che ha x come telomero 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.(0,1/2,1,3/2). Tutti gli altri archi hanno valore 0.



Dimostrazione (continua)Dimostrazione (continua)

Sia M un perfect matching su G: gli archi tra le estremità dei geni Sia M un perfect matching su G: gli archi tra le estremità dei geni

definiscono le adiacenze del genoma che possiamo indicare sempre definiscono le adiacenze del genoma che possiamo indicare sempre

con M.con M.

Il peso del perfect matching M vale esattamenteIl peso del perfect matching M vale esattamente

3n-(d(3n-(d(ΠΠ11,M)+d(,M)+d(ΠΠ22,M)+d(,M)+d(ΠΠ33,M)),M))

Cioè, il problema del massimo perfect matching equivale è un Cioè, il problema del massimo perfect matching equivale è un

problema di minimo valore del mediano.problema di minimo valore del mediano.

Dato che il problema del perfect matching è polinomiale, attraverso Dato che il problema del perfect matching è polinomiale, attraverso

questa riduzione è possibile risolvere il breakpoint median problem in questa riduzione è possibile risolvere il breakpoint median problem in

tempo polinomiale.□tempo polinomiale.□


Breakpoint distance: halvingBreakpoint distance: halving

Il problema non è ancora stato studiato. Per ottenere una facile Il problema non è ancora stato studiato. Per ottenere una facile

soluzione si possono combinare gli elementi del precedente teorema soluzione si possono combinare gli elementi del precedente teorema

con il calcolo della con il calcolo della double distancedouble distance..

Sia Sia ΔΔ il genoma il genoma all-duplicatedall-duplicated su un insieme di geni ʛ, e sia G il grafo su un insieme di geni ʛ, e sia G il grafo

costruito secondo i precedenti criteri: per ogni coppia x,y, si pesa l’arco 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 xy con (0,1,2) secondo quante volte l’adiacenza xy è presente in ΔΔ, e si , e si

pesa l’arco pesa l’arco xtxtx x con la metà della volte che x è un telomero in con la metà della volte che x è un telomero in ΔΔ. Tutti gli . Tutti gli

altri archi hanno valore 0.altri archi hanno valore 0.

Il massimo peso del perfect matching su G definisce le adiacenze del Il massimo peso del perfect matching su G definisce le adiacenze del

genoma M che minimizza d(genoma M che minimizza d(ΔΔ,M).,M).


Breakpoint distance: guided halvingBreakpoint distance: guided halving

La soluzione, analogamente, combina gli elementi finora visti.La soluzione, analogamente, combina gli elementi finora visti.

Sia Sia ΔΔ il genoma il genoma all-duplicatedall-duplicated su un insieme di geni ʛ, e sia G il grafo su un insieme di geni ʛ, e sia G il grafo

costruito secondo i precedenti criteri.costruito secondo i precedenti criteri.

Gli archi sono pesati con il numero di volte che l’adiacenza xy è Gli archi sono pesati con il numero di volte che l’adiacenza xy è

presente sia in presente sia in ΔΔ che che ΠΠ, e con la metà delle volte che x è un telomero , e con la metà delle volte che x è un telomero

di entrambi i genomi. Tutti gli altri archi hanno valore 0.di entrambi i genomi. Tutti gli altri archi hanno valore 0.

Il massimo peso del perfect matching su G definisce le adiacenze del Il massimo peso del perfect matching su G definisce le adiacenze del

genoma M che minimizza d(genoma M che minimizza d(ΔΔ,M)+d(M,,M)+d(M,ΠΠ).).


Breakpoint distance lineareBreakpoint distance lineare

Per i problemi qui analizzati considereremo solamente genomi lineari: Per i problemi qui analizzati considereremo solamente genomi lineari:

ciò permette una migliore modellazione dei genomi nucleari degli ciò permette una migliore modellazione dei genomi nucleari degli

eucarioti.eucarioti.

I risultati per la I risultati per la distancedistance e la e la double distancedouble distance sono analoghi al caso sono analoghi al caso

precedente, dove erano ammesse circolarità; in contrasto con i risultati precedente, dove erano ammesse circolarità; in contrasto con i risultati

appena mostrati però gli altri problemi risultano essere NP-complessi.appena mostrati però gli altri problemi risultano essere NP-complessi.


Breakpoint distance lineare: medianBreakpoint distance lineare: median

Teorema 2Teorema 2

Il problema del breakpoint median per i genomi lineari Il problema del breakpoint median per i genomi lineari

multicromosomici è NP-complesso.multicromosomici è NP-complesso.

Per dimostrare questo teorema ci si basa sulla riduzione con il Per dimostrare questo teorema ci si basa sulla riduzione con il

problema delle permutazioni circolari medianeproblema delle permutazioni circolari mediane (CPM). (CPM).

E’ noto che, dati tre genomi circolari E’ noto che, dati tre genomi circolari ΠΠ11, , ΠΠ22 e e ΠΠ33 con un solo con un solo

cromosoma, trovare il genoma circolare M con un solo cromosoma che cromosoma, trovare il genoma circolare M con un solo cromosoma che

minimizza d(minimizza d(ΠΠ11,M)+ ,M)+ d(d(ΠΠ22,M)+ ,M)+ d(d(ΠΠ33,M) ,M) è un problema NP-complesso è un problema NP-complesso

[Pe’er, Shamir, 1998][Pe’er, Shamir, 1998]


Breakpoint distance lineare: medianBreakpoint distance lineare: median

Sia quindi Sia quindi ΠΠ11, , ΠΠ22 e e ΠΠ33 un’istanza del problema CPM su un insieme di un’istanza del problema CPM su un insieme di

geni {1,…,n}. Sia geni {1,…,n}. Sia n+1 n+1 un nuovo gene e sia un nuovo gene e sia ΠΠ’’ii il genoma costruito da il genoma costruito da ΠΠii

dalla cancellazione dell’adiacenza x1dalla cancellazione dell’adiacenza x1tt (dove x è l’estremità di un gene (dove x è l’estremità di un gene

in {2,…,n}), e aggiunge l’adiacenza x(n+1).in {2,…,n}), e aggiunge l’adiacenza x(n+1).

I genomi I genomi ΠΠ’’11, , ΠΠ’’22 e e ΠΠ’’3 3 sono lineari. Sia poi sono lineari. Sia poi k k un intero positivo.un intero positivo.

Allora esiste un genoma circolare multicromosomico M su {1,…,n} con Allora esiste un genoma circolare multicromosomico M su {1,…,n} con

d(Πd(Π11, M) + d(Π, M) + d(Π22, M) + d(Π, M) + d(Π33, M) ≤ , M) ≤ kk se e solo se esiste un genoma se e solo se esiste un genoma

lineare e multicromosomico M’ su {1,…,lineare e multicromosomico M’ su {1,…,n+1n+1} con } con

d(Π’d(Π’11, M) + d(Π’, M) + d(Π’22, M) + d(Π’, M) + d(Π’33, M) ≤ , M) ≤ k.k.


Breakpoint distance lineare: halving, guided Breakpoint distance lineare: halving, guided halvinghalving

Questi problemi non sono ancora stati trattati.Questi problemi non sono ancora stati trattati.

E’ possibile fare la congettura che esista una soluzione polinomiale, E’ possibile fare la congettura che esista una soluzione polinomiale,

dato che tali problemi per tutte le altre misure di distanza hanno una dato che tali problemi per tutte le altre misure di distanza hanno una

soluzione polinomiale.soluzione polinomiale.

Tuttavia tentare di costruire una soluzione esula gli scopi di questa Tuttavia tentare di costruire una soluzione esula gli scopi di questa

presentazione, ed il problema rimane tutt’ora aperto.presentazione, ed il problema rimane tutt’ora aperto.


DCJ distance: distanceDCJ distance: distance

Per questo problema si ha una facile soluzione lineare.Per questo problema si ha una facile soluzione lineare.

Il grafo breakpoint di due genomi Il grafo breakpoint di due genomi ΠΠ e e ΓΓ, indicato con BP(, indicato con BP(ΠΠ,,ΓΓ), è un ), è un

grafo bipartito il cui insieme dei vertici è l’insieme delle estremità dei grafo bipartito il cui insieme dei vertici è l’insieme delle estremità dei

geni.geni.

I vertici in questo grafo hanno grado 0,1 o 2, così che il grafo è un I vertici in questo grafo hanno grado 0,1 o 2, così che il grafo è un

insieme di percorsi. Inoltre, è anche una valida rappresentazione insieme di percorsi. Inoltre, è anche una valida rappresentazione

alternativa del grafo delle adiacenze.alternativa del grafo delle adiacenze.


DCJ distance: distanceDCJ distance: distance

Teorema 3Teorema 3

Per due genomi Per due genomi ΓΓ,,ΠΠ, sia c(, sia c(ΓΓ,,ΠΠ) il numero di cicli di un grafo breakpoint ) il numero di cicli di un grafo breakpoint

BP(BP(ΓΓ,,ΠΠ) e sia p() e sia p(ΓΓ,,ΠΠ) il numero di percorsi. ) il numero di percorsi.

Allora valeAllora vale

d(d(ΓΓ,,ΠΠ) = n – c() = n – c(ΓΓ,,ΠΠ) – p() – p(ΓΓ,,ΠΠ)/2)/2

Si noti la somiglianza di questo risultato con la generale Si noti la somiglianza di questo risultato con la generale breakpoint breakpoint

distance: distance: esse differiscono nel modo in cui contano i cicli non semplici 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 ed i percorsi, ma per genomi molto distanti tra loro tendono a dare gli

stessi risultati.stessi risultati.


DCJ distance: double distanceDCJ distance: double distance

Teorema 4Teorema 4

Il problema DCJ double distance è NP-completo per genomi Il problema DCJ double distance è NP-completo per genomi

multicromosomici.multicromosomici.

Per dimostrarlo, ci si riduce al problema Per dimostrarlo, ci si riduce al problema breakpoint graph breakpoint graph

decomposition (BGD)decomposition (BGD). Un grafo G è bicolore se tutti i suoi archi sono . Un grafo G è bicolore se tutti i suoi archi sono

rossi o blu.rossi o blu.

E’ bilanciato se ogni vertice ha grado 2 o 4, ogni vertice è inerente dallo 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 stesso numero di percorsi rossi e blu e non ci sono cicli formati da archi archi

solo rossi o solo blu.solo rossi o solo blu.



Sia G un grafo bilanciato bicolore su n vertici, che definisce un’istanza 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 del problema BGD. Si definisce l’insieme del gene G come l’insieme

dei vertici in G. dei vertici in G.

Si costruisce un genoma Si costruisce un genoma all-duplicatedall-duplicated ΔΔ ed un genoma ed un genoma ΠΠ su G nel su G nel

seguente modo:seguente modo:

per ogni vertice x di G, alle estremità xper ogni vertice x di G, alle estremità x ttxxhh corrisponde un’adiacenza in corrisponde un’adiacenza in

ΠΠ. Per ogni vertice x di G siano poi x1. Per ogni vertice x di G siano poi x1ttx1x1hh,x2,x2ttx2x2hh le estremità del gene le estremità del gene

duplicato x: per ogni arco blu xy in G si costruisce un’adiacenza in 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. che unisce le teste dei geni x1 o x2 e y1 o y2.



Se il vertice ha grado 4, una delle due adiacenze definita da due archi Se il vertice ha grado 4, una delle due adiacenze definita da due archi

blu implica x1blu implica x1h h e l’altra x2e l’altra x2hh..

Se invece ha grado 2, definisce l’adiacenza con x1Se invece ha grado 2, definisce l’adiacenza con x1h h ed aggiunge ed aggiunge

un’altra adiacenza x1un’altra adiacenza x1t t x2x2hh in in ΔΔ..

Gli archi rossi seguono lo stesso principio, ma uniscono le code dei Gli archi rossi seguono lo stesso principio, ma uniscono le code dei

geni.geni.

Con questa costruzione Con questa costruzione ΠΠ è composto da n cromosomi circolari, uno è composto da n cromosomi circolari, uno

per ogni gene, e né per ogni gene, e né ΠΠ né né ΔΔ hanno telomeri. hanno telomeri.

Il numero massimo di archi-disgiunti è uguale a 2n-d(Il numero massimo di archi-disgiunti è uguale a 2n-d(ΔΔ,,ΠΠ).).


DCJ distance: medianDCJ distance: median

Teorema 5Teorema 5

Il problema DCJ median per geni multicromosomici è NP-complesso.Il problema DCJ median per geni multicromosomici è NP-complesso.

Si utilizza una riduzione della decomposizione di un grafo breakpoint Si utilizza una riduzione della decomposizione di un grafo breakpoint

simile alla precedente. Sia G un grafo bilanciato bicolore su n vertici. Si 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 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 ogni vertice di G con grado 2, e due geni x,y per ogni vertice di G con

grado 4grado 4

Si applica la seguente trasformazione Si applica la seguente trasformazione

al grafo:al grafo:


DCJ distance: medianDCJ distance: median

Sia v un vertice di grado 2 in G: si sostituisce v con due vertici 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 etichettati dalle due estremità del gene associato x. L’arco blu diventa

incidente su v per xincidente su v per xhh, quello rosso in x, quello rosso in xtt. Si aggiungono quindi due archi . Si aggiungono quindi due archi

ΠΠ11 e e ΠΠ22 per collegare queste estremità. per collegare queste estremità.

Se v è un vertice di grado 4 si sostituisce con 4 vertici etichettati con le Se v è un vertice di grado 4 si sostituisce con 4 vertici etichettati con le

4 diverse estremità e si aggiungono gli archi 4 diverse estremità e si aggiungono gli archi ΠΠ11, , ΠΠ22 e e ΠΠ33 per collegarle. per collegarle.

ΠΠ11, , ΠΠ22 e e ΠΠ33 definiscono genomi su ʛ privi di telomeri. Sia definiscono genomi su ʛ privi di telomeri. Sia ωω22 il numero il numero

di vertici di di vertici di ΓΓ di grado 2, e sia di grado 2, e sia ωω44 il numero di quello di grado 4. il numero di quello di grado 4.

Allora esiste un genoma M tale che Allora esiste un genoma M tale che

d(M, Πd(M, Π11) + d(M, Π) + d(M, Π22) + d(M, Π) + d(M, Π33) ≤ ω) ≤ ω22 + 3 ω + 3 ω44 – k – k

se e solo se esiste almeno un arco-disgiunto k alternando i cicli in G se e solo se esiste almeno un arco-disgiunto k alternando i cicli in G


DCJ distance: halving, guided halvingDCJ distance: halving, guided halving

Questo problema ha una soluzione polinomiale.Questo problema ha una soluzione polinomiale.

Gli algoritmi che lo risolvono si basano su versioni semplificate Gli algoritmi che lo risolvono si basano su versioni semplificate

dell’algoritmo di El-Mabrouk e Sankoff dell’algoritmo di El-Mabrouk e Sankoff [2003][2003] sviluppato per la distanza sviluppato per la distanza

RT.RT.

Teorema 6Teorema 6

Il problema del Il problema del guided halvingguided halving è NP-complesso per genomi è NP-complesso per genomi

multicromosomici.multicromosomici.

L’analisi di questi ultimi risultati è omessa dall’articolo, ma si basa su L’analisi di questi ultimi risultati è omessa dall’articolo, ma si basa su

riduzioni analoghe a quelle precedentemente osservate.riduzioni analoghe a quelle precedentemente osservate.


DCJ, Reversal/Translocation distance: linear DCJ, Reversal/Translocation distance: linear casecase

I problemi I problemi median median e e halvinghalving possono essere ridefiniti in termini di possono essere ridefiniti in termini di

cromosomi esclusivamente lineari, ma il problema rimane tutt’ora cromosomi esclusivamente lineari, ma il problema rimane tutt’ora

aperto.aperto.

Sono state proposte valide euristiche, specie in molti articoli recenti Sono state proposte valide euristiche, specie in molti articoli recenti

[Zheng, Zhu, Sankoff, 2008][Zheng, Zhu, Sankoff, 2008] ma le loro complessità non sono ancora note. ma le loro complessità non sono ancora note.


ConclusioniConclusioni

La seguente tabella riassume la complessità dei problemi analizzati in La seguente tabella riassume la complessità dei problemi analizzati in

questo articolo.questo articolo.

I I “?”“?” rappresentano congetture, mentre rappresentano congetture, mentre ”open””open” sta ad indicare che il problema è sta ad indicare che il problema è

ancora in fase di discussione.ancora in fase di discussione.

ProblemaProblema distancedistance HalvingHalving double distancedouble distance MedianMedian guided halvingguided halving

Breakpoint uniBreakpoint uni

Breakpoint general multiBreakpoint general multi

Breakpoint linear multiBreakpoint linear multi

PP

PP

PP

OpenOpen

PP

P?P?

PP

PP

PP

NPNP

PP

NPNP

OpenOpen

PP

NPNP

DCJ uniDCJ uni

DCJ general multiDCJ general multi

DCJ linear multiDCJ linear multi

PP

PP

PP

PP

PP

OpenOpen

OpenOpen

NPNP

OpenOpen

NPNP

NPNP

NP?NP?

OpenOpen

NPNP

NP?NP?

RT uniRT uni

RT multiRT multi

PP

PP

OpenOpen

PP

OpenOpen

NP?NP?

NPNP

NP?NP?

OpenOpen

NP?NP?


Conclusioni personaliConclusioni personali

o I problemi biologici sui genomi possono essere ricondotti a problemi matematici su grafi, e studiati mediante l’uso di un calcolatoreI problemi biologici sui genomi possono essere ricondotti a problemi matematici su grafi, e studiati mediante l’uso di un calcolatore

o Alcuni problemi sono efficientemente risolvibili, Alcuni problemi sono efficientemente risolvibili, “facili”“facili”..

o Altri sono intrattabili anche con l’utilizzo di computer, Altri sono intrattabili anche con l’utilizzo di computer, “difficili“difficili” con le attuali strategie, quindi dimostrabilmente intrattabili.” con le attuali strategie, quindi dimostrabilmente intrattabili.

Multichromosomal genome median and halving problems E. Tannier C. Zheng D. Sankoff Daniele...

Documents

Transcript of Multichromosomal genome median and halving problems E. Tannier C. Zheng D. Sankoff Daniele...