Argomenti trattati

Struttura di un gene e alternative splicing (AS)

Definizione del problema AS e algoritmo per risolverlo

ASPic software

Introduzione biologica

DNADoppia catena polinucleotidica definita sull’alfabeto: A, C, G, T

GeneRegione di DNA che codificaproteine

Numero geni e genomi in eucarioti

1

10

100

1000

10000

100000

human mouse chicken xenopus zebrafish fugu ciona fly worm yeast

Gene number Genome size (Mb)

Number of genes in prokaryotes (up to 8000)Genoma in procarioti (> 9 Mb)

Espressione di un gene

3’

5’

5’

3’

DNA

TRASCRIZIONE

5’

3’

exon 1 exon 2 exon 3pre-mRNA

SPLICING

exon 1 exon 2 exon 3 prodotto dello splicingmRNA

EST Expressed Sequence Tag(cDNA)

exon 2exon 1 exon 3

Trascritti e sequenze EST

Un trascritto è l’elenco delle basi (A, T, C, G) che compongono un mRNA maturo

Un EST è un frammento di cDNA (copia complementare di un mRNA, prodotta in vitro )

ATTGCGTTAACTGGACTGAmRNA

TAACGCAATTGACCTGACTcDNA

AATTGACCEST

Pattern di un introne

GT AG

Introni canonici: 99.24 %

Introni non canonici:

GC

AG

0.05 %0.69 %

0.02 %

AT AC

ALTRO

Burset et al., Nucleic Acids Res. 2000, 28:4363-4375

Espressione di un gene

Ma le cose funzionano davvero così?

Numero Geni corpo umano : 40000 circa

Numero Proteine : centinaia di migliaia

La corrispondenza 1 a 1 non è rispettata. Perché?

SPLICING ALTERNATIVO

Tipi di Alternative Splicing

A B C D

mRNA1

A I1 C DBGENOMICA

Splice/don’t splice

mRNA2

A I1 B C D

A I1 B

Competing 5’

A I1 BA’

A’ C DB

Competing 3’

A I1 B

C DB’A

B’

Exon skipping

A I1 B

C DA

Mutually exclusive exons

A I1 B

A B DB

C

B C

Perché AS è importante?

AS avviene nel 40-60% dei geni umani (Modrek and Lee, 2002)

AS genera numerosi trascritti a partire da un singolo gene

AS is specifico del tessuto in cui si trova la cellula (Graveley, 2001)

AS è correlato alle malattie

Problema di AS

predire le forme di splicing alternativo di un gene

analizzare il meccanismo di splicing tramite la rappresentazione delle possibili isoforme

AS è ancora un problema aperto

Si ha la necessità di software tools per

Cosa c’è a disposizione?

Programmi veloci che producono l’allineamento di una singola sequenza EST contro la genomica:

Spidey (Wheelan et al., 2001)Squall (Ogasawara & Morishita, 2002)

Ma la predizione della struttura in esoni e intronidi un gene è complicata da

errori di sequenziamento nell’EST (inserzioni, delezioni e mismatch) => criteri di ottimizzazione

sequenze duplicate sulla genomica => analisi combinata di un cluster di sequenze EST

Definizioni formali Def 1

Sequenza genomica, G = I1 f1 I2 f2 I3 f3 … In fn In+1, con Ii (i=1, 2, …, n+1) introni e fi (i=1, 2, …, n) esoni

Def 2 Fattorizzazione in esoni di G, GE = f1 f2 f3 … fn

Def 3 Fattorizzazione di un EST S compatibile con GE

S=s1 s2 … sk t.c. per 1 i1 < i2 < … < ik n si abbia:

st = fit per t=2, 3, …, k-1 s1 è un suffisso di fi1 e sk è un prefisso di fik

st = suff (fit) o st = pref (fit)variante di splicing

Def 1 Sequenza genomica, G = I1 f1 I2 f2 I3 f3 … In fn In+1,

con Ii (i=1, 2, …, n+1) introni e fi (i=1, 2, …, n) esoni

Def 2 Fattorizzazione in esoni di G, GE = f1 f2 f3 … fn

Def 3 Fattorizzazione di un EST S compatibile con GE

S=s1 s2 … sk t.c. per 1 i1 < i2 < … < ik n si abbia:

edit (st, fit) errore per t=2, 3, …, k-1 edit(s1, suff(fi1)) errore e edit(sk, pref(fik)) errore

Il problemaInput

- Una sequenza genomica G- Un cluster di sequenze EST S = {S1, S2, …, Sn}

Output

Una fattorizzazione GE di G (GE = f1, f2, …, fn) e unset di fattorizzazioni degli EST compatibili con GE

Obiettivo: minimizzare n

Esempio

Sequenza genomica G

EST set S = {S1, S2, S3}

S2 A1A2 B D1

S3 A2 D1D2 C1C2

A2 A1A2 B D1 C1 D1D2 C1C2

C1S1 A2 D1

A2 D1 C1A2 D1 C1A1A2 B D1A1A2 B D1A2 D1D2 C1C2A2 D1D2 C1C2

7 exons

B D1D2 C1C2

4 esoni

A1A2

Risultati

Il problema è MAX-SNP-hard (riduzione lineare da NODE-COVER)

Euristica: Processo iterativo per fattorizzare ogni EST

backtracking per ricomputare fattorizazzioni precedenti se si giunge ad una fattorizzazione non compatibile con GE

L’algoritmo

si1 si j-1 sijSi

e1 e2G

Passo j-esimo: Fattorizzazione parziale dell’EST Si (fattore sij)

em

if (Compatible(em, exon_list)) thenadd em to exon_list;

otherwise try to place sij elsewhere;

em

If not possible then backtrack;

si-1 1 si-1 j-1 si-1 j si-1 nSi-1

After placing all the factors sij for the set S,place the external factors;

L’algoritmo (dettagli)

G

si1 si j-1Sisi j

Calcolo del fattore sij

Sij can be divided into n components ck (k=1,2,…,n)At least one of these components for k from 1 to (n-1)is error-free and can be placed on G

sijc1 c2 c3 c4 c5

The algorithm searches a perfect match of c1 on G

c1

Suppose that c1 has no perfect match on G

Then the algorithm searches a perfect match of c2 on G

c2c1c1

Suppose that c2 has a perfect match on G

c2

Then the entire factor sij can be placed on GFind the canonical ag pattern on the left

ag

Find the rightmost gt pattern such that the edit distance between sijy and the genomic substring from ag to gt is bounded

gt

si jy

esone

ASPic software (Alternative Splicing PredICtion)

Input- La lunghezza minima prevista per un esone- La lunghezza della componente di matching perfetto- L’errore di riduzione degli introni- L’errore di sequenziamento di un EST- La sequenza genomica- Il cluster di EST

Output- Un file di testo per tutti gli allineamenti EST-genomica- Un file HTML degli allineamenti in prossimità dei siti displicing predetti

ASPic web site

ASPic è un web-based tool disponibile all’indirizzo http://aspic.algo.disco.unimib.it/aspic-devel che permette di predire i siti di splicing per un gene in input

ASPIC web site

ASPIC web site

ASPIC web site

http://www.caspur.it/ASPIC/

Information about the input A graphical view of the predicted gene structure

A table of the predicted introns A graphical view of the transcript-genome alignments

A graphical view of the predicted full-length isoforms

A table of the predicted full-length isoforms

OUTPUT:

ASPIC web site

ASPIC web site

ASPIC web site

ASPIC web site

ASPIC web site

ASPIC web site

ASPIC web site

Prediction of p53 protein isoforms

Isoform Entry L (aa) ASPIC ASAP2 ASD ACEVIEWp53 alpha NM_000546 393 + + + +p53 beta DQ186648 341 + - - -p53 gamma DQ186649 346 + - - -133 p53 alpha DQ186650 261 + + - -133 p53 beta DQ186651 209 + - + -133 p53 gamma DQ186652 214 + - + -40 p53 alpha nd 354 + - + -40 p53 beta nd 302 - - - -40 p53 gamma nd 307 - - - -

GRAZIE!