allineando - Università degli Studi di Milano

Corsi di Laurea in Biotecnologie
(primo anno interfacoltà)
Corso integrato di Matematica,
Informatica e Statistica
Informatica di base
Linea 1
Daniela Besozzi
Dipartimento di Informatica e Comunicazione
Università degli Studi di Milano
Nona lezione:
Introduzione alla Bioinformatica
Informatica di base – Linea 1 e 2
2
Prima parte
Cos’è la Bioinformatica?
Informatica di base – Linea 1 e 2
3
Una definizione di Bioinformatica
• La Bioinformatica è la scienza che si occupa
della soluzione di problemi biologici,
sfruttando gli strumenti e le teorie
dell’Informatica
• Nata con lo scopo di fornire metodi automatici
per l’analisi di sequenze di DNA e di proteine:
– sviluppo di database di dati biologici
– enorme impulso dal Progetto Genoma Umano
(sequenziamento di genomi su larga scala)
Informatica di base – Linea 1 e 2
4
Una definizione di Bioinformatica
• Oggi si usa spesso anche il termine “Biologia
Computazionale”:
– sviluppo di modelli matematici e statistici per
l’integrazione e l’interpretazione dei dati
sperimentali
– definizione di algoritmi per l’analisi di sequenze,
l’espressione dei geni, la previsione di strutture
molecolari, lo studio di processi evolutivi, …
– sviluppo di strumenti per la simulazione di
processi cellulari e sistemi biologici complessi
Informatica di base – Linea 1 e 2
5
Relazione fra Informatica e Biologia
Bioinformatica
Informatica
Biologia
Problema di biologia:
Metodologie informatiche
soluzione?
Informatica di base – Linea 1 e 2
•In cosa consiste?
•Perché è importante?
•E’ “facile o difficile”?
•Possiamo risolverlo?
•Che ricadute ha?
6
(Alcuni) problemi della Biologia (1)
• Analisi di sequenze genomiche:
– sequenziamento e mappatura di genomi
– ricerca di geni con la stessa funzione in organismi diversi
• Analisi di sequenze e strutture proteiche:
– prevedere la funzione di una proteina poco nota
– ricerca di proteine omologhe in organismi diversi
• Evoluzione di organismi:
– ricostruire l’albero filogenetico di un insieme di organismi
– capire le relazioni evolutive fra proteine (e geni)
Informatica di base – Linea 1 e 2
7
(Alcuni) problemi della Biologia (2)
• Funzionamento di processi cellulari:
– comprensione dei meccanismi di interazione fra le varie
specie molecolari presenti nella cellula
– localizzazione e concentrazione delle specie molecolari
– studio delle dinamiche del processo
• Comportamento di sistemi multicellulari:
– comprensione dei meccanismi di interazione fra cellula e
cellula (in un tessuto, in una colonia di microrganismi)
– studio di metodi per intervenire positivamente o
negativamente sul sistema multicellulare:
• es. colonia di batteri patogeni
Informatica di base – Linea 1 e 2
8
(Alcuni) problemi della Biologia (3)
• Sviluppo di farmaci e terapie mediche:
– progettazione di farmaci specifici per una certa patologia,
e analisi di tossicità/assorbimento del farmaco
– previsione e prevenzione di malattie, ottimizzazione delle
terapie mediche
• medicina personalizzata
• Risanamento ambientale (bioremediation):
– uso di biotecnologie per la “costruzione” di batteri in
grado di degradare contaminanti ambientali
Informatica di base – Linea 1 e 2
9
Gli strumenti dell’Informatica
• Molti concetti che avete già visto in questo
corso:
– Algoritmi
– Modelli
– Software e hardware dedicati
– Database
– Calcolo parallelo
– Calcolo distribuito
–…
Informatica di base – Linea 1 e 2
10
Seconda parte
Allineamenti di sequenze
Informatica di base – Linea 1 e 2
11
Qual è il problema biologico?
• Es.1 - In un laboratorio viene sequenziato un gene di un
organismo. Si vuole sapere:
– se questo gene è presente anche in altri organismi, per i quali
è già stata identificata la sua funzione
– se un altro laboratorio, che ha sequenziato lo stesso gene, ha
ottenuto lo stesso identico risultato
• Es.2 - Viene scoperta una nuova proteina, di cui non si
conosce la funzione. Si vuole sapere:
– se esiste qualche altra proteina simile a quella appena
scoperta, di cui sono già note la funzione e/o la struttura
tridimensionale
Informatica di base – Linea 1 e 2
12
DNA e proteine: sono sequenze!
• Ogni molecola può essere descritta come una sequenza
di simboli:
– ci dimentichiamo della sua struttura tridimensionale e delle
sue proprietà chimiche, fisiche o biologiche
– ci interessa soltanto sapere quali sono gli “elementi” (simboli)
che la costituiscono
• DNA: è una sequenza con 4 simboli (A, C, G, T)
– consideriamo un solo filamento (l’altro è complementare)
• RNA: è una sequenza con 4 simboli (A, C, G, U)
• Proteina: è una sequenza con 20 simboli (gli aminoacidi)
Informatica di base – Linea 1 e 2
13
Somiglianza fra due sequenze
• Come si fa a sapere se due sequenze sono
simili, e quanto sono simili?
– si confrontano i simboli di una sequenza con i
simboli dell’altra sequenza
– si dà un buon punteggio a tutte le coppie di simboli
uguali (es. A con A, T con T, C con C, G con G)
– si dà un punteggio più basso alle coppie di simboli
diversi (es. A con T, A con C, A con G, …)
• biologicamente, coppie di questo tipo corrispondono ad
eventi di mutazione (base sostituita da un’altra base)
Informatica di base – Linea 1 e 2
14
Allineamento di due sequenze
• In questo modo, possiamo “misurare” quanto sono
simili le due sequenze:
– più alta è la somma dei punteggi di tutte le coppie di simboli
che confrontiamo, più simili saranno le due sequenze
• In pratica, stiamo allineando ogni simbolo della prima
sequenza con un simbolo dell’altra:
– cioè, li scriviamo uno sopra l’altro. Esempio:
ACTCG
AGTCC
– ci sono 3 coppie di simboli uguali (A-A, T-T, C-C) e 2 coppie
di simboli diversi (C-G, G-C)
Informatica di base – Linea 1 e 2
15
I gap
• “Aspetta, aspetta… ma se le sequenze non sono
lunghe uguali, non posso allineare tutti i simboli
di una con simboli dell’altra!”
• Come si fa allora?
– si usa un simbolo speciale, che si chiama “gap” e si
denota con “”
– es. allineamento delle sequenze AACTCTG e AATCT:
AACTCTG
AATCT
il punteggio di una coppia
“simbolo-gap” è molto basso!
Informatica di base – Linea 1 e 2
16
Il significato biologico dei gap
• “Stai barando! Così modifichi la sequenza! Che
senso ha?”
• Un gap può corrispondere ad un evento
biologico di:
– delezione (base eliminata dalla molecola)
– inserimento (base aggiunta nella molecola)
• Usare i gap può essere molto utile per trovare
allineamenti migliori fra sequenze
Informatica di base – Linea 1 e 2
17
Quanti allineamenti ci sono?
• Date due sequenze A e B, il primo simbolo di A
può essere allineato con ognuno dei simboli di B
– idem per ogni altro simbolo di A
• Inoltre, posso inserire gap in qualsiasi punto della
sequenza
– (ma non si può allineare un gap con un altro gap)
• Quindi: il numero di possibili allineamenti fra due
sequenze è altissimo!
– come si fa a scegliere l’allineamento migliore?
Informatica di base – Linea 1 e 2
18
L’allineamento migliore
• Soluzione poco furba:
– costruisco tutti gli allineamenti, valuto il punteggio di
ognuno, e poi scelgo l’allineamento con il valore più alto
– ma ci vorrebbe un tempo di calcolo esponenziale rispetto
alla lunghezza delle due sequenze
• Una soluzione più furba:
– se provassimo a dividere il problema in sottoproblemi,
risolvere ogni sottoproblema, e quindi trovare la soluzione
finale rimettendo insieme le soluzioni parziali?
Informatica di base – Linea 1 e 2
19
L’algoritmo di allineamento
• Sfrutta la tecnica di “programmazione dinamica”:
– molto simile al metodo divide et impera
– la soluzione di un sottoproblema può servire per trovare la
soluzione di un altro sottoproblema (cioè, i sottoproblemi
non sono indipendenti fra loro)
• Come funziona in pratica?
– costruisce l’allineamento migliore in modo progressivo,
partendo dai simboli iniziali delle due sequenze
– a mano a mano che allunga l’allineamento, sceglie sempre la
soluzione migliore fra quelle possibili
– per costruzione, l’allineamento completo sarà quindi il
migliore allineamento!
Informatica di base – Linea 1 e 2
20
L’algoritmo di allineamento
• Un esempio con le sequenze ATTCT e GACT:
– inizio ad allineare i primi simboli delle due sequenze:
il migliore fra
A
A

questi tre
G

G
allineamenti
– restano da allineare TTCT e ACT. Osservazione: quanti
modi ci sono per allungare un allineamento?
• solo 3: simbolo-simbolo, simbolo-gap, gap-simbolo
• quindi si sceglie il migliore fra:
A T
G A
• eccetera eccetera…
A T
G 
A 
G A
e poi restano da
allineare TCT e CT
21
L’algoritmo di allineamento
• Funziona! (Fidatevi)
ATTCT
GA-CT
• E’ un buon algoritmo?
– la sua complessità computazionale è quadratica
• se n è la lunghezza delle sequenze, l’algoritmo esegue
circa n2 istruzioni
– quindi: possiamo trovare il migliore allineamento
fra due sequenze in un tempo ragionevole, senza
dover provare a costruire tutti gli altri possibili
allineamenti
22
I database biologici
• Esistono moltissimi database di dati biologici:
– sequenze nucleotidiche (GenBank, EMBL, GENES)
– sequenze proteiche (SWISSPROT)
– strutture proteiche (PDB)
– profili di espressione ricavati da microarray (GEO)
– percorsi metabolici (KEGG, Enzyme)
– dati mitocondriali (MITOMAP)
–…
23
Ricerca in database biologici
• Torniamo al gene sequenziato in laboratorio:
si usa l’algoritmo di allineamento per cercare
nel database tutte le sequenze simili?
– in un database ci sono milioni di sequenze
– se ad es. impiego 0,01 sec per un allineamento fra
due sequenze, mi servono 10000 sec=3 ore circa
per confrontare la mia sequenza con tutte quelle
presenti nel database
– se devo confrontare 6000 geni (es. lievito), ci
metto 2 anni per completare l’analisi
24
Ricerca in database biologici
• Come si fa allora?
• Si usano altri metodi, basati su “tecniche
euristiche”:
– sono procedure empiriche ed intuitive, in generale
non supportate da precisi fondamenti teorici
– non garantiscono di trovare la soluzione migliore,
ma di solito funzionano bene
– sono molto veloci
– es. BLAST, FASTA (basati su indicizzazione di
sequenze)
Informatica di base – Linea 1 e 2
25
Allineamenti multipli
• E se volessimo confrontare più sequenze
contemporaneamente?
– ad es. per vedere se una proteina è simile a un insieme di
altre proteine note
– i siti funzionalmente più rilevanti di una proteina sono di
solito ben conservati e invariati rispetto a proteine omologhe
• E’ un problema di Biologia molto importante:
– in ambito evolutivo, per capire la relazione di discendenza
fra organismi (alberi filogenetici)
– in ambito molecolare, per la previsione della struttura di una
proteina
Informatica di base – Linea 1 e 2
26
Alberi filogenetici
• Sono diagrammi che esprimono le relazioni di
discendenza fra gruppi di organismi:
– esiste un progenitore comune
– eventi di speciazione danno origine a diverse linee
di discendenza
Informatica di base – Linea 1 e 2
27
Allineamenti multipli: un esempio
Informatica di base – Linea 1 e 2
28
Allineamenti multipli: un altro esempio
Informatica di base – Linea 1 e 2
29
Algoritmi di allineamento multiplo
• Possiamo estendere l’algoritmo di allineamento fra
due sequenze, per definire un algoritmo di
allineamento fra molte sequenze?
• Si! Ma c’è un problema:
– la complessità computazionale dell’algoritmo diventa
esponenziale rispetto al numero di sequenze e alla loro
lunghezza
• “Cerchiamo un altro algoritmo allora!”
– sfortunatamente, tutti gli algoritmi che possiamo definire
per questo problema avranno complessità esponenziale
– “Perché??! E come fai a saperlo? Hai già provato a
costruire mille algoritmi diversi per risolvere il problema?”
Informatica di base – Linea 1 e 2
30
Un problema difficile
• Si può dimostrare che l’allineamento multiplo
è un problema “molto difficile”:
– è oggettivamente (non soggettivamente) difficile,
la sua complessità è intrinseca al problema stesso
– questo problema è “NP-completo”:
• in pratica, non ci sono speranze di trovare un algoritmo
efficiente che possa risolverlo (a meno che P=NP)
– come si risolve allora?
• con le tecniche euristiche, “accontentandosi” della
soluzione trovata, che non sarà necessariamente la
migliore
Informatica di base – Linea 1 e 2
31
Problemi facili e problemi difficili
“Perciò mi stai dicendo che:
1. l’allineamento fra due sequenze è un “problema
facile” perché ho trovato un algoritmo efficiente,
2. l’allineamento multiplo è un “problema difficile” e
(quasi sicuramente) non troverò mai un algoritmo
efficiente.
Uhm, tutto questo non mi piace… non è che esistono
anche altri problemi di Biologia che sono altrettanto
difficili?”
Informatica di base – Linea 1 e 2
32
Terza parte
Previsione di strutture molecolari
Informatica di base – Linea 1 e 2
33
Studiare la struttura delle molecole
• Esistono metodi sperimentali per determinare
la struttura tridimensionale di una proteina:
– cristallografia a raggi X
– risonanza magnetica nucleare (NMR)
• Sono metodi complessi, costosi, e richiedono
molto tempo
• Non si possono utilizzare per tutti i tipi di
proteine:
– ad es. proteine transmembrana
Informatica di base – Linea 1 e 2
34
Perché studiare la struttura?
• La funzione di una proteina è determinata dalla
“struttura nativa” che la proteina assume nella
cellula in condizioni fisiologiche
–
–
–
–
struttura primaria = sequenza di aminoacidi
struttura secondaria = formazione di -eliche e foglietti-
struttura terziaria = struttura tridimensionale (nativa)
struttura quaternaria = associazione di più unità
polipeptidiche
• Ogni proteina ha specifici domini di legame con altre
molecole
– es. siti attivi su un enzima (zone di legame con i reagenti e
attività catalitica) Informatica di base – Linea 1 e 2
35
Strutture proteiche non “corrette”
• Numerose patologie sono dovute a ripiegamenti errati
di una proteina, oppure ad anomale
aggregazioni/dissociazioni di proteine:
– il morbo di Alzheimer, il morbo di Huntington, il morbo di
Parkinson, l'encefalopatia spongiforme bovina, la malattia di
Creutzfeldt-Jakob, la fibrosi cistica, l’anemia falciforme,
molti tipi di tumore, ecc.
• Riuscire a determinare la struttura nativa di una
proteina consente quindi sia di identificare la sua
funzione, sia di “intervenire” sulla proteina in modo
da inattivarla/attivarla per curare la specifica patologia
Informatica di base – Linea 1 e 2
36
Il protein folding
• Consiste nel prevedere la struttura nativa di una
proteina, usando come dato in input la sequenza
primaria dei suoi aminoacidi
• Data la sequenza iniziale, esiste un
numero esponenziale di possibili
strutture tridimensionali
– come cercare un ago in un pagliaio…
Informatica di base – Linea 1 e 2
37
Protein folding e funzione di energia
• La struttura nativa migliore è quella che minimizza il
valore di “energia libera” associato alla struttura
Il valore di energia si
determina considerando
le forze di Van der Waals,
le forse elettrostatiche,
i legami idrogeno, le
lunghezze/angoli di legame,
gli angoli di torsione, le
interazioni col solvente, i
contributi entropici, …
Informatica di base – Linea 1 e 2
38
Il protein folding in Bioinformatica
• Questo problema è facile o difficile?
– è molto difficile, è un altro problema NP-completo
– tutti gli algoritmi che possiamo definire per
risolvere questo problema avranno complessità
esponenziale
– ma possiamo sfruttare anche in questo caso delle
tecniche euristiche (ma senza dare garanzie sulla
bontà della soluzione trovata):
• ad es. la tecnica per gli allineamenti multipli (si parla di
folding comparativo o per omologia)
• ne vediamo un’altra fra un po’…
Informatica di base – Linea 1 e 2
39
Interazioni fra macromolecole
• In alcuni casi, non è solo importante sapere
come la proteina si avvolge, ma anche come
interagisce con altre molecole:
– es. di interazione fra macromolecole:
• proteina-proteina, proteina-DNA, proteina-molecola
• enzima e substrato, antigene e anticorpo, recettore e
ligando
– processo che sta alla base del riconoscimento
molecolare, fondamentale per la formazione dei
complessi molecolari e il generale funzionamento
di tutti i processi cellulari
Informatica di base – Linea 1 e 2
40
Il docking molecolare
• Il problema di docking consiste nel determinare se e
come due molecole interagiscono fra di loro, e qual è
la geometria del complesso che esse formano:
– per poter risolvere questo problema, bisogna conoscere le
geometrie delle molecole  meccanismo “chiave-serratura”
• Ad es. fra queste tre coppie di molecole, qual è la
coppia con l’interazione “migliore”?
Informatica di base – Linea 1 e 2
41
Docking e funzione di energia
• Anche in questo caso, l’interazione migliore viene
definita tramite un’opportuna funzione di energia
che stima l’affinità di legame fra le due molecole
Il valore di energia si
determina considerando
le varie forze elettrochimiche,
l’interazione col solvente, la
complementarietà geometrica e
chimica fra le superfici a contatto,
l’entropia, la flessibilità delle
molecole interagenti, ecc.
il complesso migliore è quello che
minimizza il valore di energia
Informatica di base – Linea 1 e 2
42
Il docking in Bioinformatica
• Indovinate? Un altro problema difficile!
• Non esistono algoritmi efficienti in grado di trovare la
soluzione ottimale, ma è possibile applicare tecniche
euristiche
Il risultato ottenuto
dall’analisi computazionale
dovrà essere sottoposto a
successive (e numerose)
analisi sperimentali e
cliniche
Informatica di base – Linea 1 e 2
43
Drug design
• La progettazione e lo sviluppo di farmaci (drug
design) sono il principale campo di applicazione del
docking:
– determinare le modalità con cui farmaci già noti si legano
alla molecola target che si sta studiando
– effettuare una ricerca in un database di potenziali
molecole che risultino attive su nuovi target (“virtual
screening” di grandi librerie di strutture chimiche)
– prevedere in modo computazionale (“in silico”) la
potenziale attività farmacologica di nuove molecole
Informatica di base – Linea 1 e 2
44
Dalla sequenza all’interazione
interazione
sequenza
affinità
di legame
struttura
funzione
45
Quarta parte
I processi cellulari e
la “Biologia dei Sistemi”
Informatica di base – Linea 1 e 2
46
I processi cellulari
• Tutti i processi cellulari sono determinati da interazioni
fra molecole:
• espressione genica, processi metabolici, percorsi di
trasduzione del segnale, modificazioni post-traduzionali di
proteine, potenziale di membrana, ecc.
• Esistono numerosi e complessi metodi di controllo e di
regolazione cellulare per tutte queste interazioni
• Non è sempre facile o possibile effettuare esperimenti e
misurazioni in laboratorio per determinare:
– la concentrazione delle molecole, la loro localizzazione dentro la
cellula, la successione temporale delle interazioni in un dato
percorso cellulare, ecc.
Informatica di base – Linea 1 e 2
47
I processi cellulari:
componenti e interazioni
• Es. percorso di trasduzione del segnale:
–
–
–
–
–
–
segnale esterno alla cellula (molecola ligando)
recettore di membrana (proteina transmembrana)
cascata di interazioni fra proteine citoplasmatiche
sintesi di secondi messaggeri
attivazione di proteina effettore
attivazione/disattivazione di geni
OSS. Alcune di queste molecole
potrebbero essere coinvolte in
più processi cellulari!
Informatica di base – Linea 1 e 2
48
Informatica di base – Linea 1 e 2
49
Ricorriamo all’Informatica?
• Un approccio Bioinformatico permette di:
– sviluppare modelli matematici per descrivere tutte
le componenti del processo cellulare e le loro
reciproche interazioni:
• quando non c’è una precisa conoscenza biologica, si
possono definire tanti modelli diversi basati su ipotesi
– usare software appositi per simulare la “dinamica”
del processo cellulare:
• cioè, vedere come variano le concentrazioni delle
molecole nel tempo, a seconda delle condizioni della
cellula e dei meccanismi di controllo e regolazione che
sono attivi in quelle condizioni
Informatica di base – Linea 1 e 2
50
Ricorriamo all’Informatica!
• Studiare un processo cellulare sul computer ha
numerosi vantaggi:
– riduzione dei costi e del numero di esperimenti di
laboratorio
– il tempo di calcolo è generalmente inferiore al
tempo necessario per un esperimento
– si possono testare diverse ipotesi e condizioni,
senza pericolo di danneggiare o uccidere le cellule
– si possono integrare processi distinti e studiarne le
reciproche interazioni  studio del sistema globale
Informatica di base – Linea 1 e 2
51
Un esempio: p53 e Mdm2
• La proteina p53 è nota come “guardiano del genoma”, è in grado
di attivare la riparazione dei danni al DNA (oppure indurre la
cellula in apoptosi)
– è mutata in oltre il 50% delle cellule tumorali
• La sua degradazione è regolata dalla proteina Mdm2, che è a sua
volta regolata da p53 (controllo tramite “feedback negativo”)
Informatica di base – Linea 1 e 2
52
La Biologia dei Sistemi
• Scienza interdisciplinare che studia i processi biologici
in termini di “sistemi” (Systems Biology) tramite un
approccio iterativo e integrativo:
– identificazione e modellazione della struttura del sistema,
cioè delle sue componenti e delle loro interazioni
– analisi computazionale delle dinamiche del sistema per
prevedere comportamenti non noti
– disegno di nuovi esperimenti di laboratorio e confronto con i
risultati computazionali ottenuti
– uso dei nuovi dati sperimentali per migliorare il modello o
effettuare nuove analisi computazionali
– ecc.
Informatica di base – Linea 1 e 2
53
Le discipline “-omiche”
• Sono discipline biomolecolari che si occupano
dello studio su larga scala degli elementi di
una cellula (es. geni, proteine, ecc.) e delle
loro funzionalità, integrando l’uso di metodi
sperimentali e computazionali:
– Genomica, Genomica Funzionale, Genomica
Strutturale, Farmacogenomica
– Proteomica, Trascrittomica, Interattomica
– Metabolomica, Glicomica, Lipidomica
– e molte altre…
Informatica di base – Linea 1 e 2
54
L’obiettivo finale: una nuova Medicina
• La Medicina di oggi è basata principalmente sulla
cura di patologie manifeste, in generale diagnosticate
tramite poche misurazioni:
– non si distingue fra individui diversi, non ci sono terapie
personalizzate, è difficile fare una vera prevenzione
basandosi solo sulla predisposizione alle malattie
• La Medicina di domani sarà “preventiva, predittiva,
personalizzata e partecipatoria” (P4):
– basata sull’analisi degli aspetti genetici del singolo
individuo, al fine di determinare la probabilità che si
possano sviluppare malattie , e poter così intervenire in
anticipo con terapie totalmente personalizzate
Informatica di base – Linea 1 e 2
55
Quinta parte
Dalla Biologia all’Informatica
Bioinformatica
Informatica
Biologia
Calcolo Naturale
Informatica di base – Linea 1 e 2
56
Ispirarsi alla Natura: algoritmi genetici
• Il mondo dell’Informatica ha spesso fatto ricorso alla
Natura per definire nuove tecniche algoritmiche che
risultino più potenti di quelle “classiche”
• Gli algoritmi genetici sono tecniche euristiche basate
su due fenomeni che avvengono in Natura:
1. la selezione naturale degli individui in una specie
•
la teoria dell’evoluzione di Darwin sostiene che “gli
individui migliori hanno maggiore probabilità
di sopravvivere nell’ambiente in cui vivono
e quindi maggiore probabilità di riprodursi”
2. la ricombinazione del DNA durante le riproduzione
degli individui, e gli eventi di mutazione
Informatica di base – Linea 1 e 2
57
Gli algoritmi genetici (AG)
• Per risolvere un problema con un AG, viene fatta
evolvere una popolazione di “individui”:
– ogni individuo corrisponde ad una potenziale soluzione del
problema
– gli individui migliori vengono selezionati per potersi
“riprodurre” fra di loro, in base al loro grado di adattamento
– gli individui si riproducono rimescolando i loro cromosomi,
dando così origine a nuovi individui (cioè, nuove potenziali
soluzioni)
 in questo modo, molti problemi possono essere risolti da
un processo iterativo che imita l’evoluzione naturale nella
ricerca della soluzione migliore
Informatica di base – Linea 1 e 2
58
Gli algoritmi genetici: vantaggi
• Gli AG permettono di risolvere rapidamente
numerosi problemi di ottimizzazione:
– i problemi per cui si cerca la soluzione “migliore” in
un insieme molto alto di potenziali soluzioni
• Come funzionano:
– invece che “provare” tutte le soluzioni possibili, si
lavora solo su un numero molto ridotto di soluzioni
– si fanno “evolvere” le soluzioni per trovare soluzioni
che siano migliori delle precedenti
Informatica di base – Linea 1 e 2
59
Un esempio
• Proviamo a determinare il minimo assoluto di
questa funzione con un algoritmo genetico:
– l’esempio ci fa intuire quanto potrebbe essere
complessa la funzione d’energia di una molecola
questo è il minimo assoluto
Prova a usare l’applicazione Java che trovi qui:
60
http://www.obitko.com/tutorials/genetic-algorithms/example-function-minimum.php
Informatica di base – Linea 1 e 2
61
Algoritmi genetici e protein folding
• Un’applicazione degli AG al protein folding:
– ogni individuo corrisponde ad una potenziale struttura
nativa della proteina
• es. codificata con le coordinate di ogni atomo nello spazio 3D, o
con gli angoli di torsione degli aminoacidi
– la selezione opera in modo da scegliere individui “buoni”,
cioè quelli con la funzione d’energia più bassa
– la riproduzione (crossover) fra due individui buoni crea
nuove soluzioni, cioè nuove strutture native
• la mutazione può affinare una buona soluzione
– la soluzione migliore sarà scelta, alla fine dell’iterazione,
sulla base del valore minimo di energia
• ma non è detto che la soluzione trovata sia quella ottimale!
Informatica di base – Linea 1 e 2
62
Algoritmi genetici e protein folding
Il vantaggio degli AG: invece che provare tutte le soluzioni del problema
(=ricerca esaustiva nello spazio delle conformazioni con complessità esponenziale),
lavoro solo su un insieme ridotto di soluzioni
63
Sesta parte
Conclusioni e
informazioni aggiuntive
Informatica di base – Linea 1 e 2
64
La bioinformatica si occupa di:
• Definire algoritmi e modelli per:
– l’analisi dei dati biologici, la
comprensione del funzionamento
di processi cellulari e di sistemi
biologici complessi, la previsione
di strutture molecolari, la
progettazione di farmaci, ecc.
• Organizzare, memorizzare e
gestire grandi quantità di dati
biologici
• Creare software e database di
facile utilizzo anche per utenti
non esperti di Informatica
• … e molto altro
Informatica di base – Linea 1 e 2
65
“Voglio fare il bioinformatico!”
• La Bioinformatica è un’area di ricerca
multidisciplinare:
– si lavora in gruppi di ricerca eterogenei
– capirsi è fondamentale, ma non è sempre facile
• Il bioinformatico ideale ha:
– conoscenze teoriche:
• Biologia, (Bio)Chimica, Fisica, Matematica, Informatica
– competenze pratiche:
• uso di strumentazione e protocolli di laboratorio
• abilità di programmazione e manualità informatica
Informatica di base – Linea 1 e 2
66
“Ah però… non è mica così facile!”
• “Quanto devo studiare?”
– tanto, la laurea di solito non basta (serve un
dottorato di ricerca)
• “Dove si fa ricerca bioinformatica in Italia?”
– prevalentemente a livello accademico
– in alcune grandi aziende, ma su problemi più
specifici (es. drug design)
• “E all’estero?”
– quasi ovunque, ma di più nei Paesi in cui “girano più
soldi” per la ricerca (USA, Giappone, Nord Europa)
Informatica di base – Linea 1 e 2
67
“Ci sono corsi di Bioinformatica?”
• Consultate la guida dello studente e il sito del
vostro corso di laurea
• Corsi singoli per Biotecnologie Farmaceutiche
• Curriculum bioinformatico per Biotecnologie
Industriali e Ambientali:
– Bioinformatica e Biostatistica, Biologia
Computazionale, Informatica avanzata, …
• Curriculum bioinformatico nella Laurea Magistrale
di “Biotecnologie biomolecolari e bioinformatica”
Informatica di base – Linea 1 e 2
68
“Dove trovo altre informazioni?”
• Testi di riferimento:
– D.E. Krane, M.L. Raymer, Fondamenti di
Bioinformatica, Pearson (2007)
– G. Valle, M. Helmer Citterich, M. Attimonelli,
G. Pesole, Introduzione alla Bioinformatica,
Zanichelli (2003)
Informatica di base – Linea 1 e 2
69
“Dove trovo altre informazioni?”
• Link:
– National Center for Biotechnology Information (NCBI):
http://www.ncbi.nlm.nih.gov/
su questo sito, in particolare:
http://www.ncbi.nlm.nih.gov/About/primer/
http://www.ncbi.nlm.nih.gov/About/outreach/index.html
– Società di Bioinformatica Italiana (Bits):
http://www.bioinformatics.it/
– European Bioinformatics Institute (EBI):
http://www.ebi.ac.uk/
– Institute for Systems Biology:
http://www.systemsbiology.org/
Informatica di base – Linea 1 e 2
70
“Dove trovo altre informazioni?”
• Link:
– Bioinformatica su Wikipedia:
http://it.wikipedia.org/wiki/Bioinformatica
(con molti altri link alle varie applicazioni)
– cerca su Wikipedia le altre parole chiave:
protein folding, molecular docking, drug design, Systems
Biology, personalized medicine, …
ATTENZIONE! E’ sempre meglio studiare su un libro o su
articoli pubblicati su riviste di settore, o affidarsi a siti sicuri di
organismi internazionali (specializzati nell’area)
Informatica di base – Linea 1 e 2
71
Esercizi
• Assumendo di assegnare il punteggio
“+1” a coppie di nucleotidi uguali,
“-1” a coppie di nucleotidi diversi,
“-2” a coppie formate da un nucleotide e un gap,
valutare il punteggio dei seguenti allineamenti e
determinare quale allineamento è il migliore:
ATCCTA
TTCA
ATCCTA
TTCA
ATCCTA
TTCA
Informatica di base – Linea 1 e 2
ATCCTA
TTCA
72