UNIVERSITA’ DI MILANO-BICOCCA LAUREA MAGISTRALE IN BIOINFORMATICA
18
UNIVERSITA’ DI MILANO-BICOCCA UNIVERSITA’ DI MILANO-BICOCCA LAUREA MAGISTRALE IN LAUREA MAGISTRALE IN BIOINFORMATICA BIOINFORMATICA Corso di BIOINFORMATICA: TECNICHE DI BASE Prof. Giancarlo Mauri Lezione 11 Distanza genomica
description
UNIVERSITA’ DI MILANO-BICOCCA LAUREA MAGISTRALE IN BIOINFORMATICA. Corso di BIOINFORMATICA: TECNICHE DI BASE Prof. Giancarlo Mauri Lezione 11 Distanza genomica. Introduzione. - PowerPoint PPT Presentation
Transcript of UNIVERSITA’ DI MILANO-BICOCCA LAUREA MAGISTRALE IN BIOINFORMATICA
UNIVERSITA’ DI MILANO-BICOCCAUNIVERSITA’ DI MILANO-BICOCCALAUREA MAGISTRALE IN LAUREA MAGISTRALE IN
BIOINFORMATICABIOINFORMATICA
Corso di
BIOINFORMATICA: TECNICHE DI BASE
Prof. Giancarlo Mauri
Lezione 11
Distanza genomica
2
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
Introduzione
3
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
Riarrangiamento genomico
4
Operazioni su un solo cromosoma
Cancellazione abc ac
Inserimento ac abc
Duplicazione (tandem o no) abc abbc, abcd abcbd, abcd acbcd
Inversione abcdefgh abfedcgh
Trasposizione abcd acbd
Transversione una delle sottosequenze trasposte viene invertita
Riarrangiamento genomico
5
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
Riarrangiamento genomico
6
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
Riarrangiamento genomico con inversioni
7
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
Riarrangiamento genomico con inversioni
8
Dal cavolo alla rapa
1 -5 4 -3 2
1 -5 4 -3 -2
1 -5 -4 -3 -2
1 2 3 4 5
9
Dal verme all’uomo12 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 720 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 71 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 71 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 71 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 71 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 71 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 71 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 71 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 71 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 71 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 71 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 71 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 71 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 71 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 2 71 26 27 28 29 30 31 22 9 20 19 35 34 33 32 36 18 17 16 15 14 13 12 11 5 4 23 10 6 3 24 21 8 25 2 71 26 27 28 29 30 31 32 33 34 35 19 20 9 22 36 18 17 16 15 14 13 12 11 5 4 23 10 6 3 24 21 8 25 2 71 26 27 28 29 30 31 32 33 34 35 36 22 9 20 19 18 17 16 15 14 13 12 11 5 4 23 10 6 3 24 21 8 25 2 71 26 27 28 29 30 31 32 33 34 35 36 22 9 24 3 6 10 23 4 5 11 12 13 14 15 16 17 18 19 20 21 8 25 2 71 26 27 28 29 30 31 32 33 34 35 36 22 9 8 21 20 19 18 17 16 15 14 13 12 11 5 4 23 10 6 3 24 25 2 71 26 27 28 29 30 31 32 33 34 35 36 8 9 22 21 20 19 18 17 16 15 14 13 12 11 5 4 23 10 6 3 24 25 2 71 26 27 28 29 30 31 32 33 34 35 36 8 9 22 21 20 19 18 17 16 15 14 13 12 11 5 4 3 6 10 23 24 25 2 71 26 27 28 29 30 31 32 33 34 35 36 8 9 22 21 20 19 18 17 16 15 14 13 12 11 5 4 3 2 25 24 23 10 6 71 2 3 4 5 11 12 13 14 15 16 17 18 19 20 21 22 9 8 36 35 34 33 32 31 30 29 28 27 26 25 24 23 10 6 71 2 3 4 5 11 12 13 14 15 16 17 18 19 20 21 22 9 8 7 6 10 23 24 25 26 27 28 29 30 31 32 33 34 35 361 2 3 4 5 6 7 8 9 22 21 20 19 18 17 16 15 14 13 12 11 10 23 24 25 26 27 28 29 30 31 32 33 34 35 361 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
10
Distanza di inversione tra le sequenze S1 e S2: numero minimo di operazioni di inversione necessarie per trasformare S1 in S2
Esempio:
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 4 3 2 5 6
1 2 3 4 5 6
1 4 3 2 5 6
1 2 3 4 5 6
1 4 3 2 5 6
1 4 6 5 2 3
1 2 3 4 5 6
1 4 3 2 5 6
1 4 6 5 2 3
S1 1 2 3 4 5 6
1 4 3 2 5 6
1 4 6 5 2 3
S2 6 4 1 5 2 3
Distanza di inversione
d(S1,S2 ) = 3
11
Riarrangiamento genomico con inversioni
INPUTINPUT:
una permutazione dell’insieme {1,2,…,n}
OUTPUTOUTPUT:
distanza tra e la permutazione identica INB: la permutazione identica èI=1,2,…,n
NB: la permutazione identica èI=1,2,…,n
Il problema è NP-hard
Esiste però la possibilità di approssimarlo
12
Si definisca un breakpoint tra le posizioni i e i+1 di se e solo se
|(i) - (i+1)| ≠ 1dove (i) e (i+1) sono gli elementi di alle posizioni i e i+1
La permutazione identica I non ha breakpoints, quindi il riarrangiamento secondo I corrisponde all’eliminazione dei breakpoints da
In generale ogni inversione toglie al più due breakpoint
Ne segue che d()≥b()/2, dove d() è la distanza di da I e b() è il numero di breakpoints in
Riarrangiamento genomico con inversioni
13
L’euristica
DefinizioneDefinizione:
una striscia in è un sottointervallo massimale di 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 crescenteEs: 7 9 6 5 4 3 8 1 2
NB: una striscia di lunghezza 1 è considerata decrescenteNB: una striscia di lunghezza 1 è considerata decrescente
14
while ci sono breakpoints in do
begin
if c’è una striscia decrescente
then trovane una che riduca il numero di bp e invertila
(Lemma 1)
else trova e inverti una striscia crescente
(diventa decrescente; non aumenta i bp: Lemma 2)
L’euristica
Lemma 1 - Se contiene una striscia decrescente, alloraesiste una inversione che riduce il numero di bp di almeno uno
Lemma 1 - Se contiene una striscia decrescente, alloraesiste una inversione che riduce il numero di bp di almeno uno
Lemma 2 - ...Lemma 2 - ...
15
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........
L’algoritmo
16
Esempio
45321987 123549867 123459867
123459876 123456789
17
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
Riarrangiamento con permutazioni con segno
18
Il problema a differenza della versione priva di segno non è NP-hard
Esistono algoritmi risolutivi esatti in tempo quadratico
Riarrangiamento con permutazioni con segno
