Fuzzy Logic in Protein Structure Prediction
Introduzione alla fuzzy logic
FANS: un’euristica fuzzy per la ricerca locale
Applicare FANS alla predizione di strutture proteiche
Introduzione
• La scienza tende ad essere precisa.
• La realtà è invece pervasa da incertezza e imprecisione.
• Necessità di una logica diversa dalla classica logica dicotomica per
rappresentare le proprietà polivalenti degli oggetti.
• Necessità di risolvere certi problemi reali, considerati difficili, in un
tempo umanamente accettabile.
Fuzzy Logic & Soft Computing
Soft Computing
•
•
•
•
Neurocomputing
Evolutionary computation
Fuzzy logic
Probability reasoning
• “Strumenti in grado di trattare con
l‘imprecisione e l’incertezza dei problemi
reali, in grado di individuare soluzioni
robuste ed a basso costo.”
(fonte: Soft Computing and Fuzzy Logic, Zadeh 1994)
Soft Computing
• Un’euristica è una tecnica per risolvere
problemi difficili, la cui bontà della soluzione
è valutata secondo parametri basati sulle
necessità dell’utilizzatore.
• Queste necessità non sono solo legate alla
logica simbolica ma anche ad ambiti non
formali come il linguaggio naturale.
Logica Fuzzy
• “La fuzzy logic o logica sfumata è una logica polivalente e pertanto
un'estensione della logica booleana in cui si può attribuire a
ciascuna proposizione un grado di verità compreso tra 0 e 1. […]
Quando parliamo di grado di appartenenza, per dirla con
un'esemplificazione, intendiamo che una proprietà può essere oltre
che vera (= a valore 1) o falsa (= a valore 0) come nella logica
classica, anche di valori intermedi.”
(fonte: Wikipedia)
Logica Fuzzy: esempio
• Logica dicotomica
1
Bambino
0
10
A
d
o
l
e
s
c
e
n
t
e
Giovane
20
30
Mezza età
40
Su d’età
50
60
Sopra media
Anziano
70
80
90
anni
Logica Fuzzy: esempio
• Logica fuzzy
13 anni:
μ(bambino) = 0.20
μ(adolescente) = 0.55
μ(giovane) = 0.0
μ(mezza età) = 0.0
μ(su d’età) = 0.0
μ(anziano) = 0.0
μ(sopra media) = 0.0
μ
1
Bambino
0
10
Adolescente
20
Mezza età
Giovane
30
40
50
Su d’età
60
Anziano
70
80
Sopra media
90
anni
Logica Fuzzy: esempio
• Una variabile linguistica (nell’esempio precedente, l’età) rappresenta
una variabile il cui dominio è stato quantizzato in maniera fuzzy
(granulation process). E’ descritta da insiemi fuzzy (nell’esempio
precedente bambino, giovane, adolescente, etc.) definiti
univocamente ed in parte sovrapposti.
• “Un insieme F è fuzzy se l’appartenenza di un elemento x (che
rappresenta una certa variabile) ad esso può essere espressa da un
numero reale compreso tra 0 e 1.
La funzione μ(x) che esprime tale grado di appartenenza è appunto
detta funzione di appartenenza.”
(fonte: Logica Fuzzy, Veronesi e Visioli, ed. FrancoAngeli)
Logica fuzzy
Quali problemi traggono beneficio da una implementazione fuzzy?
• Problemi la cui descrizione matematica non è presente o è di difficile
definizione.
• Problemi la cui descrizione matematica è ben definita ma:
- necessità di una logica polivalente;
- il costo computazionale dell’implementazione del modello è molto
elevato;
- si lavora con un consistente rumore di fondo o con strumenti
scarsamente precisi.
Logica fuzzy
• Vantaggi:
- maggiore aderenza del modello al comportamento reale;
- riduzione costi (tempo e risorse di computazione).
• Svantaggi:
- necessità di persone che conoscano molto bene il sistema in
concreto e che siano in grado di scriverne le regole sottostanti;
- difficoltà nella rappresentazione degli insiemi fuzzy che descrivono
le variabili del sistema.
Sistemi fuzzy
problema iniziale
modellizzazione
definizione superficie
di controllo
definizione delle regole
defuzzificazione
no
è un buon
modello?
sì
Applicazioni pratiche
Sistemi fuzzy
problema iniziale
modellizzazione
definizione superficie
di controllo
definizione delle regole
defuzzificazione
no
è un buon
modello?
sì
Applicazioni pratiche
• Definizione iniziale delle caratteristiche
funzionali del sistema e delle operazioni
che possono essere compiute su di
esso.
Sistemi fuzzy
problema iniziale
modellizzazione
• Ogni variabile in input o in output al
sistema deve essere decomposta in in
una serie di insiemi fuzzy.
definizione superficie
di controllo
definizione delle regole
Input vars
defuzzificazione
no
è un buon
modello?
sì
Applicazioni pratiche
Output vars
Sistemi fuzzy
problema iniziale
modellizzazione
definizione superficie
di controllo
definizione delle regole
defuzzificazione
no
è un buon
modello?
sì
Applicazioni pratiche
• Il comportamento della superficie di
controllo deve essere definito da regole
in grado di correlare l’input con l’output
del sistema.
• IF <fuzzy preposition>
THEN <fuzzy preposition>
Sistemi fuzzy
problema iniziale
IF temperature is Cool AND pression IS Low THEN throttle action is PM
modellizzazione
definizione superficie
di controllo
definizione delle regole
defuzzificazione
IF temperature is Cool AND pression is OK THEN throttle action is ZR
no
è un buon
modello?
sì
Applicazioni pratiche
Come viene generato l’output?
Le premesse (IF) vengono combinate scegliendo
il grado di appertenenza più basso dei due valori
(intersezione, AND). Il valore di output è ottenuto
come unione (OR) degli α-cut delle funzioni di
appartenenza dopo il THEN.
Sistemi fuzzy
problema iniziale
modellizzazione
definizione superficie
di controllo
definizione delle regole
defuzzificazione
no
è un buon
modello?
sì
Applicazioni pratiche
• Il passo finale consiste nella scelta del
metodo di “defuzzificazione”, attraverso
il quale estrarre un valore
deterministico dall’inferenza fuzzy.
• Esistono vari metodi:
- media dei massimi;
- media pesata dei centri;
- metodo del baricentro;
- centro delle somme.
Sistemi fuzzy
problema iniziale
modellizzazione
definizione superficie
di controllo
definizione delle regole
defuzzificazione
no
è un buon
modello?
sì
Applicazioni pratiche
+150
FANS: Fuzzy Adaptive Neighborhood Search
• A Fuzzy Valuation-Based Local Search Framework for
Combinatorial Problems
• Applying a Fuzzy Sets-based Heuristic to the Protein Structure
Prediction Problem
(Armando Blanco, David A. Pelta, Jos´ e-L. Verdegay, 2002).
Ricerca locale
• Metodo euristico stocastico iterativo
• Semplice ma potente nel trattare problemi di tipo combinatoriale
• Trova minimi locali
Begin
s = initial_solution();
While (improve(s) = TRUE) Do
s = improve(s);
Od
return(s);
End.
FANS: introduzione
• Perché Fuzzy: le soluzioni vengono valutate in termini di
appartenenza a un insieme fuzzy, oltre che con una classica
funzione obiettivo.
• Perché Adattativo: il comportamento di FANS viene adattato nel
corso delle iterazioni.
• Meccanismo di escape da minimi locali che non richiede il riavvio
dell’intera procedura di ricerca.
FANS: fuzzy valuation
• A seconda di una diversa calibrazione delle funzioni di
appartenenza che definiscono la valutazione fuzzy delle soluzioni,
FANS può essere adattato per comportarsi in modi diversi:
- random search;
- random walk;
- hill climbing;
- simulated annealing;
- tabu search.
FANS: componenti
• Modification Operator (O): genera nuove soluzioni si a partire da s.
E’ costituito da una componente fissa, una random ed una
parametrica;
• Fuzzy Valuation (µ): ad ogni iterazione, in base al valore restituito
dalla funzione obiettivo, valuta l’appartenenza di ogni soluzione
all’insieme fuzzy costituito dalle soluzioni si dell’intorno di s (una
sorta di “Accettabilità” della soluzione);
• Operator Scheduler (OS): varia il comportamento di O;
• Neighborhood Scheduler (NS): dopo aver generato un intorno di
soluzioni servendosi di O, ne seleziona una tra quelle che
costituiscono l’intorno della soluzione in input servendosi di µ.
FANS: Modification Operator
O2
s2α
O1α
α
s
s1α,β
O1β
O2
β
s2β
FANS: procedura
Begin
InitVariables();
While (not-end) Do
NS->Run(O, µ(), Scur, Snew, ok);
If (ok) then
Scur = Snew;
adaptFuzzyVal(µ(), Scur)
Else
OS->Run();
Fi
If (TrappedSituation()) then
doEscape();
Fi
Od
return(Scur);
End.
• Creazione di una soluzione
iniziale;
• inizializzazione delle condizioni
di fine ciclio.
FANS: procedura
Begin
InitVariables();
While (not-end) Do
NS->Run(O, µ(), Scur, Snew, ok);
If (ok) then
Scur = Snew;
adaptFuzzyVal(µ(), Scur)
Else
OS->Run();
Fi
If (TrappedSituation()) then
doEscape();
Fi
Od
return(Scur);
End.
• Il ciclo esegue un numero di
iterazioni variabile in base a:
- numero di iterazioni predefinito;
- la funzione obiettivo raggiunge
un certo valore.
FANS: procedura
Begin
InitVariables();
While (not-end) Do
NS->Run(O, µ(), Scur, Snew, ok);
If (ok) then
Scur = Snew;
adaptFuzzyVal(µ(), Scur)
Else
OS->Run();
Fi
If (TrappedSituation()) then
doEscape();
Fi
Od
return(Scur);
End.
• Il Neighborhood Scheduler (NS)
è costituito da due procedure:
- generatrice;
- selezionatrice.
•
Definizione operazionale di intorno
(“vicinato di s”):
•
Definizione semantica di intorno
(“vicinato di s”):
FANS: procedura
Begin
InitVariables();
While (not-end) Do
NS->Run(O, µ(), Scur, Snew, ok);
If (ok) then
Scur = Snew;
adaptFuzzyVal(µ(), Scur)
Else
OS->Run();
Fi
If (TrappedSituation()) then
doEscape();
Fi
Od
return(Scur);
End.
• Se è stata trovata una soluzione
migliore di quella corrente:
- prende quella nuova come
corrente;
- i parametri di µ() vengono
adattati al nuovo contesto.
FANS: procedura
Begin
InitVariables();
While (not-end) Do
NS->Run(O, µ(), Scur, Snew, ok);
If (ok) then
Scur = Snew;
adaptFuzzyVal(µ(), Scur)
Else
OS->Run();
Fi
If (TrappedSituation()) then
doEscape();
Fi
Od
return(Scur);
End.
• Se NON è stata trovata una
soluzione “più adatta” di quella
corrente, viene lanciato l’Operator
Scheduler (OS), che ritorna una
versione modificata di O.
• Permette di uscire da un minimo
locale.
FANS: procedura
Begin
InitVariables();
While (not-end) Do
NS->Run(O, µ(), Scur, Snew, ok);
If (ok) then
Scur = Snew;
adaptFuzzyVal(µ(), Scur)
Else
OS->Run();
Fi
If (TrappedSituation()) then
doEscape();
Fi
Od
return(Scur);
End.
• Qualora la ricerca con cambio di
operatore fallisca ripetutamente
(tante volte quante il numero di
operatori disponibili), è molto
probabile che ci si trovi intrappolati
in un minimo locale da cui è
impossibile uscire.
• In questa situazione viene lanciata
la procedura doEscape(), la cui
implementazione classica è il
riavvio dell’intera procedura.
FANS: knapsack problem
•
Il Problema dello zaino (Knapsack
problem), è un problema di
ottimizzazione combinatoria.
•
Si ha uno zaino che può
supportare un determinato peso.
Si ha a propria disposizione una
serie di N oggetti. Ognuno degli
oggetti ha un peso e fornisce
un'utilità (ovvero un guadagno).
Il problema si propone di trovare
quali oggetti mettere all'interno
dello zaino ottenendo la maggiore
utilità, ma non eccedendo nel peso
sostenibile dallo zaino stesso.
FANS: knapsack problem
Media e deviazione standard dello scarto tra il risultato ottenuto dalle
euristiche e il risultato esatto ottenuto con un algoritmo pseudo-polinomiale.
(SA, simulated annealing; GAop, genetic algorithm one point crossover;
GAux, genetic algorithm uniform crossover).
• Buona parte del successo dell’euristica FANS può essere attribuito
all’uso di un sistema fuzzy di valutazione delle soluzioni.
FANS: Protein Structure Prediction
• Oltre che sui classici problemi di ottimizzazione combinatoriale,
FANS è stato testato su problemi di tipo biologico.
• Protein structure prediction (PSP) di prototipi proteici altamente
semplificati (lattici) secondo il modello di interazioni idrofobicheidrofiliche di Dill (HP model).
Lattici
• La complessità delle proteine reali non permette di simulare più di
pochi microsecondi del loro comportamento.
• Necessità di modelli proteici computerizzati altamente semplificati,
che possano foldare in un tempo sufficientemente piccolo da poter
essere simulato.
• Gli aminoacidi sono ridotti a sfere dal comportamento semplificato,
con gradi di libertà molto ristretti.
• Gli aminoacidi sono divisi in tipi, ogni tipo con un diverso
comportamento (possibili interazioni).
• Come nella realtà, la struttura nativa può essere individuata
minimizzando l’energia delle interazioni tra gli aminoacidi.
HP model
• La proteina è ridotta ad un pattern di idrofobicità; ogni aminoacido
viene visto come un oggetto caratterizzato da un’unica proprietà
(l’idrofobicità) che può assumere valore H o P.
• Con contatto idrofobico si intende una coppia di H adiacenti nella
struttura impaccata che non siano adiacenti nella sequenza.
• Ogni contatto idrofobico diminuisce di 1 l’energia della proteina (0
per la struttura lineare).
• PSP viene risolto massimizzando il numero di contatti idrofobici,
ovvero minimizzando l’energia della proteina.
HP model: esempio
P
P
H
H
H
H
P
n contatti idrofobici = 0
Eproteina = 0
min(Eprotein)
max(n contatti H)
H
H
H
H
P
n contatti idrofobici = 1
Eproteina = -1
Lattici: rappresentazione
• Coordinate interne:
-
assolute (s = {Up, Down, Left, Right}):
sLatticeQuadrato = RURDRDLLDLU;
-
relative (s = {Forward, TurnRight, TurnLeft}):
sLatticeQuadrato = FLRRLRRFLRR.
FANS: Protein Structure Prediction
Fans(NS, O, OS, μ(), Pars, (cond1, action1))
• L’operatore di modifica si serve di un parametro k che rappresenta il
numero di posizioni da cambiare ad ogni iterazione.
• Due categorie di operazioni possibili:
-
segment mode:
modifica k posizioni consecutive:
- shuffling: {FLRRLRRFLRR}
{FLRRFLLRLRR}
- reflection: {FLRRLRRFLRR}
{FLRRFRRLLRR}
-
flip mode:
modifica k posizioni selezionate casualmente.
FANS: Protein Structure Prediction
Fans(NS, O, OS, μ(), Pars, (cond1, action1))
• La valutazione fuzzy
f
s
q
µ
1
β
γ
0
µ(q,s,β) =
β
funzione obiettivo
soluzione corrente
una soluzione dall’intorno
operazionale di s
f(s)*(1-γ)
[0..1], in questo caso 0.2
f(s)
0.0
if f(q) < β
(f(q) – β)/(f(s) – β)
if β < f(q) =< f(s)
1.0
if f(q) > f(s)
FANS: Protein Structure Prediction
Fans(NS, O, OS, μ(), Pars, (cond1, action1))
• L’operator scheduler adatta l’operatore di modifica attraverso
cambiamenti del parametro k;
• k inizializzato a n/4;
• Ad ogni chiamata: kt+1 = kt – 1.
FANS: Protein Structure Prediction
Fans(NS, O, OS, μ(), Pars, (cond1, action1))
• E’ implementata una versione semplice del neighborhood scheduler.
-
Generatore:
chiama O secondo le modalità e i parametri passati da OS;
-
Selezionatore:
ritorna la prima soluzione trovata con µ(q) > λ.
• In questa implementazione il numero massimo di soluzioni valutate
in una chiamata di NS è fissato a 50.
FANS: Protein Structure Prediction
Fans(NS, O, OS, μ(), Pars, (cond1, action1))
• Parametri di O, (k, …).
• Parametri di μ(), (λ, …).
• Informazioni condivise tra le componenti.
FANS: Protein Structure Prediction
Fans(NS, O, OS, μ(), Pars, (cond1, action1))
• (k = 0, doEscape()).
• (“nessun miglioramento in N chiamate di NS”, doEscape()).
FANS: relative encoding vs absolute encoding
Risultati per lattici quadrati
Risultati per lattici triangolari
Risultati per lattici cubici
• Per ogni lattice valutato, FANS è
stato lanciato 180 volte (30 corse *
3 λ * 2 encoding).
• Le tabelle mostrano, per ogni
coppia (lattice, λ) quale dei due
metodi di codifica delle coordinate
sia risultato significativamente
migliore (t-test) rispetto all’altro.
• Condizione di terminazione:
105 chiamate della funzione di
valutazione fuzzy.
FANS vs GA
•
•
•
•
•
•
Parametri di FANS adattati e implementati in GA;
lattici quadrati;
relative encoding;
λ = 0.9;
30 corse per ogni istanza ed algoritmo;
condizione di terminazione: 105 chiamate della funzione di
valutazione fuzzy.
FANS vs GA
FANS: conclusioni riguardo PSP
• I risultati di FANS si allineano o superano quelli ottenibili con
algoritmi genetici.
• Codifica relativa delle coordinate migliore nei lattici quadrati, codifica
assoluta migliore nei lattici triangolari, comportamento intermedio
per i lattici cubici.
Questo risultato conferma i risultati precedentemente ottenuti
utilizzando algoritmi genetici.
FANS: conclusioni
• Si può ottenere un diverso comportamento di FANS calibrando la
componente fuzzy.
(A Fuzzy Valuation-Based Local Search Framework for Combinatorial Problems, Armando Blanco, David A. Pelta,
Jos´ e-L. Verdegay, 2002).
• Sono stati ottenuti risultati soddisfacenti applicandolo a problemi
generici quali l’ottimizzazione di funzioni.
(A Fuzzy Adaptive Neighborhood Search for Function Optimization, Armando Blanco, David A. Pelta, Jos´ e-L.
Verdegay, 2002).
• FANS dà buoni risultati anche come euristica applicata a problemi
pratici di ottimizzazione (PSP).
(Applying a Fuzzy Sets-based Heuristic to the Protein Structure Prediction Problem, Armando Blanco, David A.
Pelta, Jos´ e-L. Verdegay, 2002).
Ulteriori risorse
• Krasnogor N, HartW, Smith J, Pelta D. Protein structure prediction
with evolutionary algorithms. In: BanzhafW, Daida J, Jakaiela M,
Smith R, editors. GECCO-99. Morgan Kauffman; 1999.
• Dill KA. Theory for the folding and stability of globular proteins.
Biochemistry, 1985.
• David Pelta, Natalio Krasnogor, Carlos Bousono-Calzon, José L.
Verdegay, J. Hirst, Edmund Burke. A fuzzy sets based
generalization of contact maps for the overlap of protein structures,
2004.