Biologia Computazionale
Giulio Pavesi
[email protected]
Biologia Computazionale?
Computational Biology, sometimes
referred to as bioinformatics,
is the science of using biological
data to develop algorithms and relations
among various biological systems.
Prior to the advent of computational biology,
biologists were unable to have access
to large amounts of data.
Researchers were able to develop analytical methods
for interpreting biological information, but were
unable to share them quickly among colleagues
(Wikipedia)
Biologia Computazionale?
Bioinformatics: Research, development, or application
of computational tools and
approaches for expanding the use of biological,
medical, behavioral or health data,
including those to acquire, store, organize,
analyze, or visualize such data.
Computational Biology: The development and application of
data-analytical and theoretical methods,
mathematical modeling and
computational simulation techniques
to the study of biological, behavioral, and social systems.
Programmare?



Algoritmo: sequenza di operazioni che a partire da un
insieme di dati iniziali (input) produce un insieme di dati
finali (output)
Un algoritmo “descrive” il procedimento per risolvere un
problema, e può essere scritto in linguaggio “naturale” o
con apposite rappresentazioni (“pseudocodici”,
diagrammi di flusso) ma NON dipende da linguaggi di
programmazione
Programmazione: implementazione di uno o più
algoritmi in un dato linguaggio di programmazione 
descrivo le operazioni con comandi che possono essere
eseguiti da un computer
Il primo algoritmo della storia
"If some one say: "You divide ten into two parts: multiply the one by itself;
it will be equal to the other taken eighty-one times."
Computation: You say, ten less thing, multiplied by itself,
is a hundred plus a square less twenty things, and this is equal to eighty-one things.
Separate the twenty things from a hundred
and a square, and add them to eighty-one. It will then be a hundred plus a square,
which is equal to a hundred and one roots.
Halve the roots; the moiety is fifty and a half. Multiply this
by itself, it is two thousand five hundred and fifty and a quarter.
Subtract from this one hundred; the remainder i
s two thousand four hundred and fifty and a quarter.
Extract the root from this; it is forty-nine and a half. Subtract this from the moiety
of the roots, which is fifty and a half. There remains one, and this is one of the two parts.”
[Risolveva: (10-x)2=81x]
Programmi ed algoritmi



Quando si vuole risolvere un problema
utilizzando un computer è necessario prima
“disegnare” un algoritmo per la soluzione
L’algoritmo deve essere indipendente dalla
successiva implementazione (codifica) in un
linguaggio di programmazione
L’algoritmo descrive un procedimento che,
partendo da dati di input (l’istanza del
problema), esegue un insieme di istruzioni o
operazioni, in un ordine stabilito, che al
termine produce come risultato (output) la
soluzione del problema
Programmi ed algoritmi

I passi (istruzioni) dell’algoritmo devono essere





Finiti (l’algoritmo deve terminare)
Non ambigui
Terminare e produrre un output corretto per ogni istanza
del problema
Ad esempio, una ricetta *non* è un algoritmo se scrive
“aggiungere un pizzico di sale”; lo è se scrive
“aggiungere 0,5 g di sale”
Ad esempio, dato il problema “Dati a, b, c risolvere
l’equazione di secondo grado con coefficienti a,b,c”
deve prevedere tutti i casi diversi che si possono
presentare per i valori di a,b,c (equazione impossibile, di
primo grado, etc.)
Programmi ed algoritmi



Per molti problemi (quelli più difficili!) possono
esistere più metodi di soluzione e quindi più
algoritmi
L’algoritmo migliore è quello più “efficiente”,
ovvero quello che implementato richiede
meno risorse di calcolo (tempo, spazio su
memoria o su disco) per produrre una
soluzione esatta
La “teoria degli algoritmi” si occupa di stimare
- indipendentemente dall’implementazione - il
numero di operazioni “atomiche” o elementari
e lo spazio richiesti da un algoritmo, in modo
da decidere a priori quale possa essere la
soluzione migliore
Programmi ed algoritmi


Un algoritmo può essere descritto in vari modi, purché
rispetti le condizioni precedenti
Ad esempio, si possono usare:



Linguaggio naturale
Diagramma di flusso
“Pseudocodice”
Il linguaggio naturale si presta a semplici algoritmi, ma
già algoritmi per problemi “semplici” come l’equazione
di secondo grado diventano di difficile “lettura” se
descritti così
“Se a è uguale a zero, allora è un equazione di primo grado,
la cui soluzione, se b e c sono diversi da zero è data da
meno uno per b diviso per c, altrimenti ....”

Diagramma di flusso




Un “diagramma di flusso” descrive il “flusso di calcolo”
di un algoritmo
E’ suddiviso in blocchi: in ciascun blocco l’algoritmo
compie un’operazione
Archi orientati (frecce) collegano un blocco all’altro,
indicando la sequenza delle operazioni da compiere
Alcuni blocchi sono “condizionali” (o di “selezione”, di
solito a forma di rombo), ovvero il blocco (istruzione)
successivo dipenderà dalla condizione descritta dal
blocco stesso: a seconda del fatto che la condizione sia
soddisfatta o meno, saranno possibili due scelte per il
passo successivo (e quindi ci saranno due archi uscenti)
Delta = b2-4ac
VERO
Delta < 0?
FALSO
VERO
Delta = 0?
FALSO
Scrivi
“l’equazione
non ha soluzioni
reali”
x=-b/2a
x1=(-b+Delta)/2a
x2=(-b-Delta)/2a
Scrivi
“L’equazione ha
soluzioni x1 e x2”
Scrivi
“L’equazione ha
due soluzioni
coincidenti = x”
“Pseudocodice”



“Simula” uno “pseudo” linguaggio di
programmazione, e descrive l’algoritmo
utilizzando le “pseudo-istruzioni” del
linguaggio di programmazione
Lo pseudocodice deve comunque essere
indipendente dal linguaggio in cui si
scriverà il programma
Deve quindi contenere un insieme
“minimale” di istruzioni che ci
aspettiamo essere comuni a tutti i
linguaggi (vedi dispense)
Lo “pseudolinguaggio”

Possiamo assumere che il linguaggio di
programmazione che usiamo conterrà
operazioni:






Leggi/Scrivi (input/output)
Operazioni (e funzioni) matematiche
Assegnamento: assegnare un valore a una
variabile
Selezione:
SE(condizione)...ALLORA...ALTRIMENTI
Iterazione: ESEGUIFINCHE’(condizione) esegue finché la condizione è vera
Iterazione: PEROGNI elemento IN
collezione
“Iterazioni”


E’ possibile fare ripetere all’algoritmo
lo stesso insieme di operazioni un
qualsiasi numero n di volte, senza
bisogno di scriverle esplicitamente n
volte
n può



essere un numero prefissato
una variabile il cui valore può variare
durante l’esecuzione dell’algoritmo
dipendere dal fatto che una condizione
venga soddisfatta o meno (ovvero, le
istruzioni vengono ripetute finché la
condizione è soddisfatta)
Esempio: calcola 2n
Leggi n
contatore = 0
potenza = 1
ESEGUIFINCHE’ (contatore < n)
potenza = potenza * 2
contatore = contatore + 1
FINE ESEGUIFINCHE’
Scrivi “Due alla” n “è uguale a” potenza
“Pseudocodice”



Un programma per computer lavorerà su in insieme di
“variabili” contenenti i dati del problema, soluzioni
intermedie, soluzioni finali
Le variabili possono essere di tipo diverso, a seconda dei
dati che trattiamo, ad esempio
 Numeri interi
 Numeri reali
 Matrici
 Parole costruite su un alfabeto
 Vettori
 ....
Anche in questo caso dobbiamo prevedere un insieme
“minimale” di tipi di variabili su cui lavorare con lo
pseudocodice
Programmare?



Algoritmo: sequenza di operazioni che a partire da un
insieme di dati iniziali (input) produce un insieme di dati
finali (output)
Un algoritmo “descrive” il procedimento per risolvere un
problema, e può essere scritto in linguaggio “naturale” o
con apposite rappresentazioni (“pseudocodici”,
diagrammi di flusso) ma NON dipende da linguaggi di
programmazione
Programmazione: implementazione di uno o più
algoritmi in un dato linguaggio di programmazione 
descrivo le operazioni con comandi che possono essere
eseguiti da un computer
La struttura interna di un
computer
Linguaggi di programmazione
Programma in memoria RAM
(C, Pascal, Perl, Python…)
Computer
(PC, MAC, smartphone)
Linguaggi di programmazione
Programma
(C, Pascal, Perl, Python…)
Traduttore in linguaggio macchina
(specifico del linguaggio usato)
Computer
Linguaggi di programmazione
Programma
Traduttore in linguaggio macchina
Sistema Operativo
(Unix, Windows Mac OSX)
Computer
Linguaggi di programmazione


I computer “capiscono” soltanto il proprio
linguaggio macchina
Insieme di istruzioni di “basso livello” che
consentono di





leggere/scrivere nella memoria
eseguire operazioni sul contenuto dei registri (tipo
somma e operazioni logiche)
“saltare” da una parte all’altra del programma
controllare se una data condizione è verificata
Quindi, il linguaggio utilizzato varia a seconda
dell’ “architettura” e del sistema operativo
(PC vs Mac, PC Windows vs PC Linux etc...)
Linguaggio “macchina”

Esempio di istruzioni in linguaggio
macchina




Leggi il contenuto della cella di memoria
1058382
Leggi il contenuto della cella di memoria
1058843
Somma i due valori letti
Scrivi il risultato della somma nella cella di
memoria 1751511
(più possibilità di confronti, condizioni e
cicli)
Linguaggio “macchina”

Esempio di istruzioni in linguaggio macchina,
lettura di un file da disco





Fai partire il motore che fa ruotare il disco
Cerca sul disco la posizione dell’inizio del file
Copia il contenuto di una parte del file in memoria
RAM
Cerca sul disco il pezzo successivo di file
….
(di solito, operazioni di questo tipo sono gestite
dal sistema operativo, che fa da “interfaccia”
per tutto quello che riguarda l’utilizzo
dell’hardware della macchina)
Linguaggi di Programmazione





Scrivere un programma in linguaggio macchina
è un incubo (detto da uno che l’ha fatto!)
Esistono linguaggi di programmazione di “alto
livello”
Per poter essere compresi dal programma
devono prima essere tradotti da programmi
appositi, ovvero, trasformati nel “linguaggio
macchina” della macchina che stiamo usando
La traduzione dipende dall’architettura del
computer (ovvero il processore) e dal sistema
operativo in cui il programma viene tradotto
Il computer “capisce” un linguaggio di
programmazione se è installato un apposito
“traduttore” specifico del linguaggio
Linguaggi di Programmazione


Il programma può essere tradotto in linguaggio
macchina prima dell’esecuzione, o durante
l’esecuzione
Linguaggi compilati



Linguaggi interpretati





Il traduttore (compilatore) traduce tutto il programma in
una volta sola, producendo un programma in linguaggio
macchina (eseguibile)
Esempio: C, C++
Il traduttore (interprete) traduce un’istruzione alla volta,
mano a mano che il programma viene eseguito
Esempio: Perl, Python
I linguaggi “compilati” sono in genere molto più veloci
degli “interpretati” (c’è in meno il tempo di traduzione)
I linguaggi “interpretati” sono più comodi da distribuire
Java: prima compilato in un linguaggio macchina
“virtuale” (byte code) che viene poi interpretato quando
il programma viene eseguito  “portabile” su diversi
computer, indipendentemente da CPU e SO
Linguaggi di Programmazione

Linguaggi compilati, vantaggi




Linguaggi interpretati, vantaggi



Più veloce l’esecuzione
Più flessibili e più maneggiabili dal programmatore
esperto
Una volta compilato, se si ha lo stesso computer/SO
è sufficiente avere l’eseguibile
Più semplici da utilizzare per il programmatore
inesperto
Il programma può essere eseguito su qualsiasi
computer/SO, a patto che sia installato il
traduttore/interprete per il linguaggio
Perl: vedi appunti del corso, è un linguaggio
interpretato e non tipizzato
Linguaggi di Programmazione





Un qualsiasi linguaggio di programmazione ha una
sua precisa sintassi
Interpreti e compilatori verificano innanzitutto che
la sintassi sia corretta
Un qualsiasi linguaggio di programmazione ha un
insieme di “comandi” o comunque parole chiave
che sono interpretate come istruzioni da eseguire
Interpreti e compilatori verificano anche che i
“comandi” del programma siano effettivamente
riconosciuti come istruzioni del linguaggio
I linguaggi di programmazione moderni sono
“espandibili”: combinando le istruzioni già
disponibili posso creare “funzioni”, che a tutti gli
effetti diventano nuove istruzioni del linguaggio
Linguaggi di Programmazione

Regole di sintassi (esempi)
Ogni comando deve essere seguito
da punto e virgola ; (esempio
print”Ciao”;)
 Per ogni parentesi aperta (tonda,
quadra o graffa) deve esserci la
corrispondente parentesi chiusa
 Tutte le virgolette (semplici o doppie)
aperte devono essere chiuse
