Bioinformatica:
un mix tra Biologia,
Matematica e Informatica.
Luca Bortolussi
Dipartimento di Matematica e Informatica,
Universita’ di Udine.
[email protected]
www.dimi.uniud.it/bortolus
Ringraziamenti
●
Alberto Policriti,
per le slides e i consigli!
●
LucioTorelli,
per l’opportunità!
Di cosa parleremo
●
●
●
●
Perche’ (e quando) i biologi hanno cominciato a parlare con
gli informatici?
Quali biologi e mentre facevano cosa si sono interessati alla
computazione?
Quali sono i problemi che ci vedono coinvolti?
Quali sono gli strumenti che usiamo e che contributo
possiamo (realisticamente) dare?
●
Complessita’.
●
Che cosa ci viene in cambio? (Ci possiamo divertire?)
●
…
●
Che cos’e’ la Bioinformatica?
Le aree
Algoritmica su stringhe
●
–
–
Matematica del discreto
String matching esatto e approssimato
Systems biology
●
–
–
Matematica del continuo
Automi e biologia
Computare usando il DNA
●
–
Le nuove frontiere
Qualche spunto sugli sviluppi, qualche lettura consigliata.
Crick and Watson: 1953
●
●
●
●
1953: F. Crick e J. Watson scoprono la
struttura a doppia elica del DNA
anni ’70: si sviluppano le tecniche per il
sequenziamento di spezzoni di DNA (F. Sanger)
anni ’80: viene lanciato il progetto genoma e
partono le prime sperimentazioni pilota (insieme
alle prime compagnie per lo sfruttamento
commerciale di queste ricerche)
anni ’90: vengono sequenziati i primi organismi
(qualche M di paia di basi)
●
●
1990: viene pubblicato
1998: C. Venter annuncia la costituzione della
compagnia privata Celera e sfida il consorzio pubblico
per il sequenziaemnto del genoma umano: Celera
otterra’ il risultato in 3 anni (e 300 M di $)
http://www.pbs.org/wgbh/nova/genome/program.html
(Cracking the code of life)
Dietro la sfida:
Two main shotgun-sequencing strategies.
Clone-by-clone shotgun sequencing
Whole-genome shotgun sequencing
Programmi e algoritmi nella sfida
Finally, perhaps the most essential element of any whole-genome
shotgun-sequencing strategy is the availability of a robust assembly
program that can accommodate the inevitably large collection of
sequence reads. [...] include algorithms that account for the anticipated
spatial relationship of read pairs emanating from individual subclones,
which help to avoid misassemblies due to repetitive sequences.
Strategies for the systematic sequencing of complex genomes
Eric D. Green
Un problema iniziale (semplice?)
T testo su un alfabeto 
P pattern su 
Come determino (tutte) le occorrenze di P in T?
Quanto tempo impiego?
T
P
|P| |T| confronti
Altri problemi algoritmici correlati
●
●
Longest repeated substring (determina la
piu’ lunga stringa ripetuta in una stringa
data)
strutture dati (non conviene
rappresentare in memoria sequenze come
stringhe ma come sistemi di indici per
tutti i possibili suffissi della sequenza)
Tries & Trees
●
●
●
Trie
a
Trie: Digital Search Tree over
strings in alphabet C
b
Each edge is a symbol, and
siblings represent distinct
symbols
Final character of string cannot
occur elsewhere in string
–
c
c
c
a
$
a
$
b
bcabc$
b
c
c
$
$
Add marker symbol (“$”) to
alphabet
• Inefficient
•Eliminate Unary Nodes
b
Tree
$
abc$
bc
abc$
•Suffix Tree
• Arcs are non-empty substrings
• Each non-terminal, non-root has two children
• Sibling arcs begin with different characters
c
$
abc$
$
$
$
Com’e’ finita la sfida?
http://www.accessexcellence.org/AB/
Human Genome Working Draft Sequence
published February 15 & 16, 2001
Science and Nature
Problemi algoritmici in biologia
computazionale
Astronomy began when the Babylonians mapped the
heavens. Our descendants will certainly not say that
biology began with today’s genome projects, but they
may well recognize that a great acceleration in the
accumulation of biological knowledge began in our era.
To make sense of this knowledge is a challenge, and will
require increased understanding of the biology of cells
and organisms. But part of the challenge is simply to
organise, classify and parse the immense richness of
sequence data.
Biological sequence analysis
R. Durbin, S. Eddy, A. Krogh and G. Mitchinson
L’allineamento di sequenze
Among the most useful computer-based tools in
modern biology are those that involve sequence
alignments of proteins, since these alignements often
provide insights into gene and protein function.
There are several types of alignments: global
alignments of pairs of proteins, multiple alignments
of members of protein families, and alignments made
driving data base searches to detect homologies.
S. Henikoff and J.G.Henikoff PNAS 1992
Cos’e’ un allineamento?
Input:
GTTGATTAGCTTATCCCAAAGCAAGGCACTGAAAATGCTAGAT
GTGATGTAGCTTAACCCAAGCAAGGCACTAAAAATGCCTAGAT
Output:
GTTGAT_TAGCTTATCCCAAAGCAAGGCACTGAAAATG_CTAGAT
GT_GATGTAGCTTAACCCAA_GCAAGGCACTAAAAATGCCTAGAT
GTTGATTAGCTTATCCCAAAGCAAGGCACTGAAAATGCTAGAT
GTGATGTAGCTTAACCCAAGCAAGGCACTAAAAATGCCTAGAT
G
T
G
A
T
G
T
A
G
T
T
G
A
T
T
A
G
C
T
T
A
0
1
2
3
4
5
6
7
8
9
10
11
12
1
0
1
2
3
2
1
1
1
2
3
2
2
2
1
4
3
2
5
4
3
6
5
4
7
6
5
GTTGAT_TAGCTTATCCCAAAGCAAGGCACTGAAAATG_CTAGAT
GT_GATGTAGCTTAACCCAA_GCAAGGCACTAAAAATGCCTAGAT
Algoritmi
●
●
●
●
●
●
●
Needelman-Wunsh 1970
Smith –Waterman 1981
Landau-Vishkin 1986
Wu-Manber 1992
Myers 1994
Chang-Lawler 1994
...
Complessita’: le risorse che abbiamo sono
finite
My favorite way to describe computer science
is to say that it is the study of algorithms.
Advances in our ability to compute are bringing us
substantially closer to ultimate limitations.
D.Knuth
Mathematics and Computer Science: Coping with
Finiteness
Che risorse (computazionali) abbiamo?
Universo
protone
10-13 cm
40 miliardi di anni luce
125
10
(maggiore o uguale al) numero di protoni nell’universo
Se assumiamo una unita’ di tempo pari al tempo necessario alla
luce a viaggiare per 10-13 cm e assumiamo che l’universo sia nato
10 miliardi di anni fa, il numero di unita’ di tempo trascorse e’
minore o uguale a
42
10
Che “speranze” abbiamo
•
•
•
•
•
snail 0.0006 miles/h
man 4 miles/h
US auto 55 miles/h
Jet 600 miles/h
Supersonic jet 1200 miles/h
•
•
•
•
•
man (pencil) 0.2/sec
man (abacus) 1/sec
calculator 4/sec
computer 200.000/sec
fast computer 2M/sec
Bill Gates (nel 2003)
Alla COMDEX, una fiera di computer
svoltasi di recente (tipo SMAU, n.d.t),
Bill Gates ha fatto un parallelo tra
l'industria del computer e quella
dell'automobile, sentenziando che
"Se la General Motors fosse progredita
con la tecnologia tanto quanto
l'industria dei computer, ora tutti noi
guideremmo automobili da 25.000
dollari che percorrono circa 400 Km.
con un litro di benzina"
In risposta a queste osservazioni di Bill Gates,
l'Ufficio Stampa della General Motors ha emesso il
seguente comunicato:
"Se la GM avesse sviluppato la propria tecnologia con
gli stessi criteri con cui Microsoft ha sviluppato
Windows, tutti noi guideremmo automobili con le
seguenti caratteristiche:
1.
senza alcun motivo particolare, l'automobile
avrebbe incidenti due volte al giorno;
2.
ogni volta che ridipingono le linee sulle strade,
occorrerebbe comprare una nuova automobile;
3.
di tanto in tanto l'automobile morirebbe in mezzo
all'autostrada senza alcuna ragione particolare;
dovremmo spingerla a lato della strada, chiudere
tutte i finestrini, spegnere, riavviare e riaprire i
finestrini per poter continuare.
●
●
●
●
●
●
occasionalmente, l'effettuare una semplice manovra, come la
svolta a sinistra, provocherebbe lo spegnimento
dell'automobile, che poi si rifiuterebbe di riaccendersi: in
questo caso, sarebbe necessario reinstallare il motore;
le spie dell'olio, dell'acqua troppo calda e della batteria
verrebbero sostituite da una sola spia, indicante che
"L'automobile ha effettuato una operazione illegale";
l'airbag, prima di entrare in funzione, chiederebbe: "sei
sicuro?“
occasionalmente, di nuovo senza alcuna ragione, l'automobile ti
chiuderebbe fuori e ti impedirebbe di rientrare fino a quando,
con un'unica manovra, non sollevi la maniglia della portiera, giri
la chiave nella serratura e sollevi l'antenna della radio;
ogni volta che esce un nuovo modello di automobile, gli
automobilisti dovrebbero imparare a guidare da capo, poiche’
nessuna delle levette, dei pedali e degli interruttori del
precedente modello si comporterebbe come quelli del nuovo
modello;
sarebbe necessario premere il pulsante "Start" per spegnere il
motore.
Grid problem: calcolare il numero di cammini da start a finish
finish
start
Il problema e’ difficile
●
●
●
non ci sono metodi noti per calcolare il numero di cammini
(in a reasonable amount of time)
possiamo comunque generare dei cammini random e usare
un teorema di statistica che ci dice che la stima migliore e’
data dalla media dei reciproci delle probabilita’ osservate
otteniamo una stima enorme: (1.6 ± 0.3) 1024
Un problema semplice (da enunciare) e “pulito”, ma ...
non possiamo contare nemmeno su una procedura
esaustiva per enumerare i cammini!
il problema di stabilire una (qualunque) proprieta’ dei
cammini sulla griglia e’ algoritmicamente trattabile?
Forse abbiamo bisogno di una teoria della
complessita’ algoritmica che ci permetta di
classificare questo come un problema difficile
Protein Folding Prediction
Una proteina può essere vista come una
sequenza di aminoacidi (stringa di lettere)
● Vi sono 20 tipi di aminoacidi
● PROBLEMA:
– Data la sequenza di aminoacidi
(struttura primaria) di una proteina,
●
– Identificare la forma spaziale della
proteina (Conformazione nativa o
Struttura Terziaria)
Esempio
●
●
Primaria: [k,s,c,c,p,n,t,t,g,t, … ,y,p,k]
Terziaria:
Regolarità locali: sono la Struttura Secondaria.
Come si risolve?
●
●
●
●
●
Si ritiene (assune) che alla conformazione
nativa sia associata una energia minima.
Si specifica lo spazio delle possibili soluzioni,
In questo spazio si cerca quella che minimizza
l'energia.
PROBLEMA 1: come si calcola l'energia?
PROBLEMA 2: lo spazio delle soluzioni ha
dimensioni esponenziali in funzione della
lunghezza della proteina.
Calcolo dell'energia
Ogni conformazione spaziale è associata ad un
valore di energia.
●Il valore è minimo per la conformazione nativa.
●Dipende dalla distanza tra gli aminoacidi e dai
loro tipi.
●
Assunzione: solo coppie di
aminoacidi in contatto
contribuiscono all'energia
globale, secondo una tabella
20 x 20.
Spazio Ricerca
- Si usano (anche) spazi discreti.
Uno usato e' il cubo a facce
centrate
(FCC) di lato 2.
-
- Ogni punto ha 12 vicini (ognuno a
distanza radice di 2).
Dati 3 punti consecutivi, i valori ammissbili sono 60°,
90°, 120°, e 180°
●Gli angoli di 60° e 180° non occorrono in natura.
●E' un modello realistico.
●La struttura secondaria può essere codificata.
●
Esempio:
1ENH
●Length: 54
●Primary
●
[r,p,r,t,a,f,s,s,e,q,
l,a,r,l,k,r,e,f,n,e,
n,r,y,l,t,e,r,r,r,q,
q,l,s,s,e,l,g,l,n,e,
a,q,i,k,i,w,f,q,n,k,
r,a,k,i]
Secondary
●
[helix(8,20),strand(22,23),
helix(26,36),helix(40,52)]
L'astrazione HP
●
●
●
K. A. Dill, nel 90, propone di
dividere gli aminoacidi in 2
famiglie: H, P
L'energia si calcola con il
numero di H in contatto.
Già questa versione semplificata
è NP-completa.
-2
Systems Biology:
Informatica e costruzione ed uso di
modelli
Le difficolta’ di comprensione in Biologia non
dipendono, come in fisica, dalla scala ma dalla
complessita’.
J. Monod “Il caso e la necessita’”
Esempio:
un orologio artificiale
• Three proteins:
– LacI, tetR & l cI
– Arranged in a cyclic manner
(logically, not necessarily
physically) so that the
protein product of one gene
is rpressor for the next gene.
LacI! : tetR; tetR! TetR
TetR! : l cI; l cI ! l cI
l cI! : lacI; lacI! LacI
Modello Biologico
Modello Matematico
x1
-
dx2/dt = a2 X6g26X1g21 - b2 X2h22
x2
x3
dx4/dt = a4 X2g42X3g43 - b4 X4h44
-
x4
x5
dx6/dt = a6 X4g64X5g65 - b6 X6h66
-
x6
X1, X3, X5 = const
La Bioinformatica deve fornire:
• strumenti per costruire modelli matematici potenti
• metodi per trattare diverse tipologie di input
• linguaggi di interrogazione (automatica)
• consentire una analisi di tipo discreto/continuo
Una notte del 1993 L. Adleman stava
leggendo “The molecular Biology of the Gene”.
Si sedette sul letto e disse a sua moglie:”Dio
mio, queste cose possono calcolare “
Se usiamo il dna come software
(hardware) di un calcolatore,
che possibilita’ “avremmo” a disposizione?
helicase estrae l’informazione, polymerase la ricombina,
ligase la rifinisce ... ecc. ecc.
... possiamo costruire un computer ‘biologico”!
(non error free)
polymerase: 1ml di p 5 10^18 molecole
ligase: 1 joule di energia 20 10^18 operazioni
1 g di dna 4 10^21 bit (1.000 G CD’s)
The thiniest treasure chest
Conclusioni
• Biologia ed Informatica interagiscono lungo strade molto
variegate. La Matematica e’ il linguaggio comune.
• Il termine Complessita’ (ed i modi e gli strumenti per
affrontarla) non sono intesi da tutti nello stesso modo.
• Il lavoro di ricerca in questo campo e’ motivato dalle
applicazioni ma tocca problematiche profonde: ricerca di
base.
Bioinformatica tra Udine e Trieste
•Alberto Policriti (UD)
●
●
●
●
Protein Structure
Prediction
•Agostino Dovier (UD)
•Angelo Montanari (UD)
•Giuseppe Lancia (UD)
Algorithms for
genome analysis
•Carla Piazza (UD)
Computational
System Biology
•Francesco Fabris (TS)
Databases and Data
Management
•Andrea Sgarro (TS)
•Luca Bortolussi (UD)
•Nicola Vitacolonna (UD)
•Simone Scalabrin (UD)
•Marco Zantoni (UD)
•Cristian del Fabbro (UD)
•Michele Braidotti (CIB - TS)