gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern...
TRANSCRIPT
![Page 1: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/1.jpg)
Gestione e modellazione di dati bioinformatici
MODULO: Riconoscimento e Recupero dell’informazione per
Bioinformatica
Manuele Bicego
Corso di Laurea in Bioinformatica
Dipartimento di Informatica - Università di Verona
![Page 2: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/2.jpg)
Il docente
Manuele Bicego
Dipartimento di informatica
Ufficio: Ca' Vignal 2 – Primo Piano – Stanza 1.55
Telefono: 045 8027072
e-mail: [email protected]
Ricevimento:Durante il semestre di lezione: lunedì ore 11.30 - 13.00
In alternativa: su appuntamento concordato via e-mail
![Page 3: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/3.jpg)
Il corso
Modulo da 6 CFU4 CFU teoria, 2 CFU laboratorio
NOTA: Alcune lezioni in Lab (le prime) saranno di Teoria
Orario:
Mercoledì 10.30 – 13.30 Aula D
Giovedì 8.30 – 11.30 Lab Delta
![Page 4: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/4.jpg)
Pre-requisiti
Pre-requisiti per le attività in aula:
Conoscenze di base di Probabilità, Statistica, Analisi
Pre-requisiti per le attività in laboratorio:
Minima capacità di programmare
Verranno forniti i fondamenti di Matlab
![Page 5: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/5.jpg)
Punto di vistaTitolo del modulo: Riconoscimento e Recupero
dell’informazione per bioinformaticaè un titolo molto generico!
In questo modulo: studio delle tecniche di “Pattern Recognition” per estrarre informazioni (da dati biologici)spesso alla base di programmi largamente utilizzati (ad
esempio BLAST, Phylip, HMMER)
![Page 6: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/6.jpg)
Obiettivi formativiFornire le basi delle metodologie di Pattern Recognition
Capire cos’è la pattern recognition
Capire la differenza tra le diverse tipologie di problemi risolvibili con tecniche di pattern recognition
Capire come creare un sistema automatico di pattern recognition
Capire come validare i risultati ottenuti
Vedere esempi di applicazione di tecniche di Pattern Recognition a problemi di bioinformatica
L’attenzione è rivolta principalmente alla descrizione delle metodologie piuttosto che ai dettagli dei programmi applicativi (già visti in altri corsi).
![Page 7: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/7.jpg)
Programma (in generale)
Il corso si compone di due parti
Teoria: in questa parte verranno presentate le diverse metodologie
di Pattern Recognition, le motivazioni che portano al loro studio, e i problemi connessi al loro utilizzo.
Verranno inoltre analizzati alcuni problemi bioinformatici che sono classicamente risolti con metodologie di pattern recognition
Laboratorio:verranno implementati in matlab semplici algoritmi di
pattern recognition
![Page 8: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/8.jpg)
Materiale didattico
Materiale didattico: lucidi del corso, appunti presi a lezione (per lezioni alla lavagna), libri suggeriti, articoli, internet in generale. I lucidi del corso saranno messi in linea prima delle lezioni
Laboratorio di riferimento: VIPS (Vision, Image Processing & Sound), CV2, piano -2
Info: http://vips.scienze.univr.it
![Page 9: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/9.jpg)
TestiR. Duda, P. Hart, D. Stork Pattern Classification. Wiley,
2001 (2nd edition).
P. Baldi, S. Brunak, Bioinformatics, The Machine Learning Approach. MIT Press, 2001
G. Gan, C. Ma, J, Wu: Data Clustering: Theory, Algorithms and Applications, ASA-SIAM Series on Statistics and Applied Probability, 2007
A.K. Jain and R.C. Dubes, Algorithms for Clustering Data, Prentice-Hall, 1988.Disponibile on line
http://homepages.inf.ed.ac.uk/rbf/BOOKS/JAIN/Clustering_Jain_Dubes.pdf
S. Theodoridis, K. Koutroumbas: Pattern Recognition, Second edition, Academic press, 2003
![Page 10: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/10.jpg)
Altri testi consigliatiN. Cristianini, M.W. Hahn: Introduction to Computational
Genomics, Cambridge University Press, 2007
W.J. Ewens, G.R. Grant: Statistical Methods in Bioinformatics, Springer 2001
C.M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006.
W.J. Ewens, G.R. Grant, Statistical Methods in Bioinformatics. Springer, 2001
E. Keedwell, A. Narayanan, Intelligent Bioinformatics. Wiley, 2005
M. Berthold, D.J. Hand, Intelligent Data Analysis. Springer, 2003 (2nd edition).
![Page 11: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/11.jpg)
Modalità d’esame
NOTA: Vale per tutto il corso di Gestione e Modellazione di dati per Bioinformatica
PARTE 1 (13.5 punti): scritto sugli argomenti del modulo di Riconoscimento e Recupero dell'informazione per Bioinformatica
PARTE 2 (13.5 punti): scritto sugli argomenti del modulo di Basi di Dati per Bioinformatica
PARTE 3 (6 punti, OPZIONALE): seminario di approfondimento, argomento da scegliere autonomamente
![Page 12: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/12.jpg)
Modalità d’esame
Seminario:
- OPZIONE 1: Seminario da fare a fine gennaio: due persone, 30-35 minuti (più domande)
- OPZIONE 2: Seminario da fare “quando si vuole”: una persona sola, 30-35 minuti (più domande)
PROCEDURA (per chi lo fa a gennaio)Registrazione entro il 15 novembre
Scelta argomento entro il 15 dicembre (check obbligatorio con il docente)
Preparazione slides (possibilità di check con il docente)
Presentazione
![Page 13: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/13.jpg)
Modalità d’esame
PROCEDURA (per chi lo fa “quando si vuole”)
(In generale viene offerta una possibilità al mese)Scelta argomento (check obbligatorio con il docente)
Preparazione slides e accordo su data esposizione (possibilità di check con il docente)
Presentazione
![Page 14: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/14.jpg)
Modalità d’esameScelta argomento: un articolo uscito nel 2016 su una di queste riviste:
Briefings in Bioinformatics (http://bib.oxfordjournals.org/), Bioinformatics (
http://bioinformatics.oxfordjournals.org/), IEEE/ACM Transactions on Computational Biology and Bioinformatics (http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=8857) BMC Bioinformatics (http://www.biomedcentral.com/bmcbioinformatics) Artificial Intelligence in Medicine (http://www.sciencedirect.com/science/journal/09333657) , Information Systems (https://www.journals.elsevier.com/information-systems/) VLDB Journal (http://www.vldb.org/vldb_journal/) ACM Transaction on Database Systems (https://tods.acm.org)
Altre riviste di alto prestigio (Nature, Science, ...)
(pdf accessibili nei laboratori dell'università)
L'articolo deve essere in linea con gli argomenti trattati nel corso e può contenere approfondimenti su tematiche di stage/tesi
![Page 15: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/15.jpg)
Modalità d’esame
Preparazione slides (dopo aver letto e capito l'articolo):30/40 slides (dipende da quanto si parla per ogni slide)
Non troppo piene, non usare font troppo piccolo
Attenzione al tempo e al modo di esposizione:Suddivisione equa tra i due partecipanti (nel caso di seminario a
gennaio)
Stare nei tempi (30/35 minuti)
Il seminario viene seguito dai due docenti (quindi deve essere sufficientemente generale)
Seminario a gennaio: presentazione penultima o ultima settimana di gennaio
Check con il docente delle diapositive: una volta sola!
![Page 16: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/16.jpg)
NOTA: Tutte le informazioni, il materiale didattico, gli aggiornamenti e gli avvisi inerenti al corso sono pubblicati alla pagina web del corso
![Page 17: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/17.jpg)
Introduzione
![Page 18: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/18.jpg)
Sommario
Introduzione alla Pattern Recognition
Pattern Recognition e Bioinformatica: perché?
![Page 19: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/19.jpg)
Pattern RecognitionPunto di partenza: l'uomo e la Pattern Recognition
Che cos'è questa?
In che città mi trovo?
![Page 20: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/20.jpg)
C'è una vespa blu?
![Page 21: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/21.jpg)
Quanti tipi di fiori ci sono?
![Page 22: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/22.jpg)
Pattern Recognition Il processo che ci porta a rispondere a queste
domande si chiama Pattern Recognition
Riconoscere che si tratta di una mela
Identificare l'oggetto più importante nella foto (l'Arena) ed associarlo alla città di Verona
Trovare nell'immagine tutti gli oggetti di tipo “vespa”, ed identificare se ce n'è una di colore blu
Riconoscere i fiori e distinguerli in due diverse tipologie (anche non sapendo che fiori sono)
![Page 23: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/23.jpg)
Pattern Recognition
Più in generale:
Prendere in ingresso un insieme di dati (un'immagine, un suono, un odore)
Effettuare un'analisi di tali dati per rispondere ad una domanda tipicamente legata al concetto di categoria o classe (che tipo di oggetto è? Quante categorie di oggetti ci sono? E' presente un dato di una certa categoria?)
Pattern: il dato che viene analizzato, l'entità di interesse
![Page 24: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/24.jpg)
Pattern RecognitionUna definizione storica: “il processo che prende in
input dati grezzi (raw) ed effettua un’azione sulla base della categoria dei dati” [Duda et al., 2001]
E' un problema che l'uomo risolve facilmente (tramite processi complicati non ancora completamente chiari)
![Page 25: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/25.jpg)
Pattern RecognitionLa prospettiva informatica: realizzare sistemi AUTOMATICI di Pattern Recognition
Sistemi che siano in grado di risolvere problemi di Pattern Recognition senza l'intervento dell'uomo
Il problema viene studiato da molti anni, anche se è tipicamente molto difficile!
Esempio: riconoscere caratteri scritti a mano
Facile per l'uomo, difficile per il calcolatore
![Page 26: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/26.jpg)
Perché è difficile per un calcolatore?
C'è molta variabilità:
- oggetti della stessa classe possono essere diversi
- oggetti di classi diverse possono essere molto simili
![Page 27: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/27.jpg)
Perché è difficile per un calcolatore?
Gli umani hanno “sensori” migliori
vs
![Page 28: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/28.jpg)
Perché è difficile per un calcolatore?
Quello che vede l'uomo:
Quello che vede il calcolatore:
![Page 29: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/29.jpg)
Altri esempi classici
distinguere diverse persone sulla base del volto
pattern: la parte dell'immagine che contiene la faccia
![Page 30: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/30.jpg)
Altri esempi classiciRiconoscimento del parlato
Riconoscimento di impronte digitali
Riconoscimento di gesti
![Page 31: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/31.jpg)
Altri esempi classiciRiconoscimento di Scene a partire da immagini
![Page 32: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/32.jpg)
Classificazione di video: capire in ogni immagine se ci sono oggetti che si muovono (classificare i pixel)
Originale Classificazione: bianco = movimento
Altri esempi classici
![Page 33: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/33.jpg)
Altri esempi classici
Videosorveglianza: classificazione di oggetti in movimento
![Page 34: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/34.jpg)
Nel laboratorio VIPS:classificazione e clustering di:
Oggetti
Immagini
Audio e video
Segnali sismici e naturali
...
classificazione di situazioni (videosorveglianza)
Bioinformatica: genetica computazionale, analisi di spettri NMR, analisi di dati da esperimenti microarray, protein remote homology detection
Analisi di immagini biomedicali: (es. MRI)
![Page 35: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/35.jpg)
Il problema principale
Capire e modellare i diversi pattern di un problema
(tipicamente in termini di classi / gruppi / categorie)
Il paradigma principaleIl problema è risolto usando il cosiddetto paradigma
“apprendimento da esempi”
La conoscenza si deriva da un insieme di esempi campionati dal problema (il training set – insieme di addestramento)
![Page 36: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/36.jpg)
L’obiettivo principale
GENERALIZZAZIONE: capacità di generalizzare anche a oggetti sconosciuti (non presenti nel
training set)
![Page 37: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/37.jpg)
Il vero problema
Derivare un modello per il problema a partire da esempi
Tipicamente il problema è risolto con una procedura di ottimizzazione
Model max Ε T , P ,Θ T = training set P = informazioni a priori Θ= parametri
![Page 38: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/38.jpg)
Il vero problema
Problemi da risolveredefinire la funzione E
compromesso tra la capacità di spiegare il training set e la complessità
ottimizzare E (tipicamente una funzione difficile da ottimizzare)discesa lungo il gradiente
Expectation – Maximization
Simulated annealing
Tabu Search (Reactive Tabu search)
Algoritmi genetici
![Page 39: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/39.jpg)
Altri problemiAspetti teorici
convergenze del learning
comportamenti asintotici
ottimalità delle soluzioni
...
Aspetti praticiaccuratezza
requisiti computazionali (tempo e spazio)
flessibilità
usabilità
...
![Page 40: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/40.jpg)
Tipologie di problemi in PR
Ci sono diversi problemi che possono essere risolti con metodologie di pattern recognition
I tre principali sono:
Classificazione
Detection
Clustering
Che cos'è?
C'è una vespa blu?
Come si raggruppano i fiori di questo campo?
![Page 41: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/41.jpg)
Più nel dettaglio...
Problema: modellare pesci
spigola orata
[Duda Hart Stork, Pattern Classification, Second Edition, Wiley 2001]
![Page 42: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/42.jpg)
M1, M2
spigola o orata?
Classificazione
Trovare due modelli M1 e M2, uno per l’orata e uno per la spigola
Trovare un modello M per tutte le spigole
M
Questo pesce è una spigola?
Detection
Che cos'è?
C'è una vespa blu?
![Page 43: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/43.jpg)
Clustering
1. identificare pesci simili (identificare tutti i gruppi “naturali” e creare i modelli)
2. identificare le relazione tra i pesci (clustering gerarchico)
Come si raggruppano i fiori di questo campo?
![Page 44: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/44.jpg)
In ogni caso.....
occorre costruire un modello a partire dai dati!
![Page 45: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/45.jpg)
Aspetti principaliLa realizzazione di un sistema di Pattern Recognition implica la soluzione dei seguenti problemi:
Rappresentazione: come rappresentare in modo digitale gli oggetti del problema
Costruzione del modello: come costruire un modello a partire da un insieme di dati (training set)
Testing: come utilizzare il modello per “spiegare qualcosa” dei dati tipicamente per fare classificazione, clustering o detection
![Page 46: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/46.jpg)
Problema
Dati grezzi
Dati rappresentati
Rappresentazione
campionamento
Estrazione/raffinamento delle feature (preprocessing)
patterns
patterns
![Page 47: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/47.jpg)
Costruzione del modello
Training Set (patterns)
Modelli
Informazioni a priori
addestramento
![Page 48: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/48.jpg)
Testing
Testing Set (patterns)
Informazioni
Modelli addestrati
![Page 49: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/49.jpg)
Più nel dettaglio....
![Page 50: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/50.jpg)
RappresentazioneObiettivo: trovare una rappresentazione digitale per gli
oggetti del problema in esame
Tipicamente si effettuano una serie di misure sull'oggetto,
utilizzando dei sensori
L'insieme di queste misure è detto PATTERN, ogni singola
misura è detta FEATURE
Esempio
L'immagine è il pattern, ogni pixel è una feature (viene misurato il colore)
La sequenza di DNA è il pattern, ogni nucleotide è una feature (viene misurato il tipo – A,T,C,G)
![Page 51: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/51.jpg)
RappresentazioneLe misure sono spesso “grezze”
Immagine: migliaia di pixels!
Sequenze di DNA: migliaia di basi!
Pre-processing dei dati: “migliorare” la rappresentazione:ridurre la dimensione del pattern (per visualizzare, per ridurre il carico
computazionale, ...)
mettere in evidenza particolari strutture o migliorare le capacità
discriminative dello spazio
Estrazione di feature: trasformazione dello spazio originale
Selezione di features: selezionare le feature migliori
![Page 52: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/52.jpg)
Rappresentazione: esempio
Il problema
campionamento
dati grezzi (un’immagine)
x1 = [5, 10]
estrazione di due features
(altezza,lunghezza)
dati pre-processati
![Page 53: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/53.jpg)
Costruzione del modelloProblema da risolvere: costruire un modello in grado di
spiegare i dati del training set
training/learning/addestramento
“Il modello deve spiegare il problema”: capacità di generalizzare anche a pattern mai visti (capacità di generalizzazione)
La costruzione del modello (paradigma di apprendimento da esempi) si basa su:
Le misure (il training set)
La conoscenza a priori (le etichette del training set, o altro)
![Page 54: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/54.jpg)
Costruzione del modello
Il training set deve essere adeguatamente:
largo (molti pattern)
completo (tutte le categorie devono essere ragionevolmente rappresentate)
variabile (deve tenere in considerazione la variabilità dei pattern nelle categorie)
![Page 55: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/55.jpg)
Costruzione del modello Scelte da effettuare
tipo di modello
parametri del modello
dimensione del modello
metodo di addestramento (funzione da ottimizzare, metodo di ottimizzazione)
metodo di validazione (come capire se il modello scelto effettivamente rappresenta il fenomeno in questione)
procedura diversa a seconda che si parli di classificazione, clustering o detection
Diversa tipologia di informazione a priori disponibile (cosa conosco degli esempi del training set)
![Page 56: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/56.jpg)
Esempio: classificazione
Insieme di addestramento
x1,y1
x2,y2
...
xN,yN
Addestramento: modellare (separare) le due classi
altezza
lunghezza
Feature space
spigola
orata
Rappresentazione
xi patterns yi etichette
Info a priori: di tutti gli esempi del training set conosco la classe (patter recognition supervisionata)
![Page 57: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/57.jpg)
Esempio: classificazione/testing
dati pre-processati
oggetto sconosciuto
Altezza
lunghezza
Modelli
categoria: spigola
x1 = [3, 12]
rappresentazione
testing
![Page 58: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/58.jpg)
Esempio: detection
Insieme di addestramento
x1
x2
...
xN
Addestramento: modellare la classe
altezza
lunghezza
Feature space
Info a priori: tutti gli esempi del training set sono nella stessa classe (patter recognition supervisionata)
![Page 59: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/59.jpg)
Esempio: detection/testing
x1 = [3,12]
rappresentazione
dati pre-processati
oggetto sconosciuto
altezza
lunghezza
Modello
testing
questo pesce non appartiene al gruppo
![Page 60: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/60.jpg)
Esempio: clustering
Data Set
x1
x2
...
xN
Goal1: scoprire i gruppi naturali altezza
Info a priori: nessuna (pattern recognition non supervisionata) al massimo che ci sono due gruppi
Feature space
lunghezza
Goal2: descrivere le relazioni tra i patterns
![Page 61: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/61.jpg)
Un commento sul clustering Il clustering è un problema più difficile della classificazione
Il processo è non supervisionato: non è possibile misurare la correttezza del risultato! (differentemente dalla classificazione)
Il clustering rappresenta l’organizzazione di un insieme di patterns (entità) in gruppi (clusters) sulla base della similarità
Qual’è la similarità più appropriata?Cambiare la similarità cambia il risultato
Cosa deve rappresentare un “buon gruppo”? Il concetto di gruppo è definito in modo vago e assolutamente soggettivo
![Page 62: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/62.jpg)
Esempio: Oggetti da clusterizzare
![Page 63: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/63.jpg)
Ci sono 2 gruppi: mele e pere
![Page 64: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/64.jpg)
Altra possibilità: frutta rossa e frutta verde
![Page 65: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/65.jpg)
Quindi
Il concetto di cluster è vago:Dipendentemente dalle misure di similarità utilizzate cambia
il risultato
La scelta della misura di similarità è cruciale.Dovrebbe essere fatta in modo da inglobare la maggior
quantità possibile di informazione a priori.
Il risultato può cambiare anche a seconda della metodologia utilizzata per fare clustering (il concetto sarà più chiaro in seguito)
![Page 66: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/66.jpg)
Sommario
La costruzione del modello può avvenire in modo supervisionato (classificazione e detection) o non supervisionato (clustering)Supervisionato (Supervised learning): per ogni oggetto del
training set si conosce l’esatta categoria
Non supervisionato (Unsupervised learning): non si conosce nulla
Reinforcement learning (per classificazione)a metá strada tra le due: non viene fornita alcuna
informazione sulla categoria esatta, viene dato un giudizio sulla correttezza della classificazione
![Page 67: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/67.jpg)
Interpretazione dei risultati
L’obiettivo finale è quella di estrarre / recuperare conoscenzaottenere intuizioni dal data set
Il fuoco deve essere sulla ”interpretabilità” dei prodotti interpretabilità dei metodi
mette a proprio agio l’utente
interpretabilità delle soluzionipermette di capire gli errori
![Page 68: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/68.jpg)
Pattern Recognition e bioinformatica: perché?
![Page 69: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/69.jpg)
PR e bioinformatica: perché?
Ci sono molti buoni motivi per utilizzare tecniche di Pattern Recognition nella Bioinformatica...
LA MOTIVAZIONE PRINCIPALE: la caratterizzazione di una popolazione in termini di gruppi/classi/categorie può essere utilizzata per inferire alcune proprietà di oggetti sconosciuti guardando ad oggetti conosciuti nello stesso gruppo
In altre parole: vengono inferite informazioni su entità sconosciute a partire da informazioni note su entità conosciute che siano “simili”
![Page 70: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/70.jpg)
Esempio 1
Problema:
Da che continente proviene X?
Questo è conosciuto: si chiama John e viene dall’Europa
X e John sono simili, sono nello stesso gruppo/classe
X
Posso ipotizzare: anche X viene dall’Europa
Popolazione (dati – patterns)
X
Categorizzazione sulla base del colore
![Page 71: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/71.jpg)
Esempio 2Esempio:
ho una proteina B la cui funzione è sconosciuta
trovo una proteina A che ha una struttura/sequenza molto simile (misura di similarità, clustering)
Posso ipotizzare che la proteina B abbia una funzione simile.
![Page 72: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/72.jpg)
PR e bioinformatica: perché?
Altre motivazioni:
1. In bioinformatica ci sono molti problemi di classificazione, clustering e detection
2. Possibilità di derivare modelli per i dati tramite esempi (paradigma di apprendimento da esempi)
3. Ci sono problemi di classificazione (onerosi in termini di tempo) che possono essere automatizzati apprendimento da esempi che possono essere giudicati da
esperti / validati sperimentalmente
più in dettaglio...
![Page 73: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/73.jpg)
SommarioOrganism
Genome
Gene 1...
mRNA
Protein sequence
Protein structure
...
...
Gene N
mRNA
Protein sequence
Protein structure
Genomica
Trascrittomica
Proteomica
![Page 74: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/74.jpg)
PR e bioinformatica: perché?
1. In bioinformatica ci sono molti problemi di classificazione, clustering e detection
2. Possibilità di derivare modelli per i dati tramite esempi (paradigma di apprendimento da esempi)
3. Ci sono problemi di classificazione (onerosi in termini di tempo) che possono essere automatizzati
![Page 75: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/75.jpg)
PR e BioinformaticaOrganism
Genome
Gene 1...
mRNA
Protein sequence
Protein structure
...
...
Gene N
mRNA
Protein sequence
Protein structure
Gene search
![Page 76: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/76.jpg)
Gene search
Non tutto il DNA del genoma è “geni”
PR: detection di geni
![Page 77: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/77.jpg)
PR e BioinformaticaOrganism
Genome
Gene 1...
mRNA
Protein sequence
Protein structure
...
...
Gene N
mRNA
Protein sequence
Protein structure
Analisi dell'espressione e della regolazione genica (microarrays)
![Page 78: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/78.jpg)
MicroarrayMicroarray: tecnologia in grado di analizzare simultaneamente migliaia di geni
Expression microarrays: misurano il livello di espressione dei geni
![Page 79: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/79.jpg)
Microarray
![Page 80: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/80.jpg)
![Page 81: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/81.jpg)
Di solito vengono effettuati diversi esperimenti:differenti condizioni di crescita
soggetti diversi
malattie diverse
Risultato
Matrice di espressione e(g,s)
genes
esperimenti
lo spot e(g,s) rappresenta quanto il gene e è espresso nell’esperimento s
![Page 82: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/82.jpg)
Microarray
Two conditions
Four conditions
PR:
1. classificazione di campioni
2. clustering
![Page 83: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/83.jpg)
clustering di geni
Trovare geni con pattern di espressione simili (quindi con funzioni ipoteticamente correlate)
clustering di esperimenti
trovare esperimenti con geni espressi in modo simile
Clustering
![Page 84: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/84.jpg)
PR e BioinformaticaOrganism
Genome
Gene 1...
mRNA
Protein sequence
Protein structure
...
...
Gene N
mRNA
Protein sequence
Protein structure
Motif discovery
![Page 85: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/85.jpg)
Motif Discovery
pattern simili nelle sequenze
PR: detection di questi pattern (motif)
parti simili in strutture di diverse proteine
![Page 86: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/86.jpg)
Protein Remote Homology Detection
PR e BioinformaticaOrganism
Genome
Gene 1...
mRNA
Protein sequence
Protein structure
...
...
Gene N
mRNA
Protein sequence
Protein structure
![Page 87: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/87.jpg)
Protein Remote Homology Detection
Stessa Funzione
“A”
Molte proteine con
strutture simili
Le sequenze corrispondenti
condividono una similarità remota
PR: caratterizzare ogni classe di sequenze omologhe (in senso remoto)
![Page 88: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/88.jpg)
PR e Bioinformatica
Organism
Genome
Gene 1...
mRNA
Protein sequence
Protein structure
...
...
Gene N
mRNA
Protein sequence
Protein structure
Organism
Genome
Gene 1...
mRNA
Protein sequence
Protein structure
...
...
Gene N
mRNA
Protein sequence
Protein structure
Filogenesi
Filogenesi
![Page 89: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/89.jpg)
Filogenesi
Filogenesi: inferire le relazioni genealogiche tra gli organismi
PR: clustering di sequenze geniche o proteiche
![Page 90: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/90.jpg)
PR e Bioinformatica
Organism
Genome
Gene 1...
mRNA
Protein sequence
Protein structure
...
...
Gene N
mRNA
Protein sequence
Protein structure
Organism
Genome
Gene 1...
mRNA
Protein sequence
Protein structure
...
...
Gene N
mRNA
Protein sequence
Protein structure
Genomica comparativa
![Page 91: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/91.jpg)
Genomica comparativa (filogenomica)
Problemi: Presenza
assenza di geni
traslazioni spaziali di geni
duplicazione di geni
Filogenomica: ha lo stesso obiettivo della filogenesi ma viene effettuata a livello di genoma
![Page 92: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/92.jpg)
PR e bioinformatica: perché?
1.In bioinformatica ci sono molti problemi di classificazione, clustering e detection
2.Possibilità di derivare modelli per i dati tramite esempi (paradigma di apprendimento da esempi)
3.Ci sono problemi di classificazione (onerosi in termini di tempo) che possono essere automatizzati
![Page 93: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/93.jpg)
Modelli dai datiModelli dai dati con il paradigma di “apprendimento
da esempi”Permette l'estrazione di informazioni semplificate o
riassuntive
Loop “simulazione & feedback”
Dati Modelli
Apprendimento da esempi
predizioneDati
simulati
Confronto
feedback
![Page 94: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/94.jpg)
PR e bioinformatica: perché?
1.In bioinformatica ci sono molti problemi di classificazione, clustering e detection
2.Possibilità di derivare modelli per i dati tramite esempi (paradigma di apprendimento da esempi)
3.Ci sono problemi di classificazione (onerosi in termini di tempo) che possono essere automatizzati
![Page 95: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/95.jpg)
Possibilità di automatizzare procedure di classificazione onerose dal punto di vista del tempo richiestoSi può “imparare” come uno specialista esegue tali
operazioni
Addestramento da un training set “annotato” da esperti
Automazione di procedure
Esempio: qualità degli spot dei microarray
![Page 96: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/96.jpg)
Problema: Trovare gli spot dei microarray con
bassa qualità
Spot: immagine che contiene l'espressione di un gene
Approccio tipico:Annotazione manuale da parte di
esperti
size roundness intensity pixel distribution
![Page 97: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/97.jpg)
L’approccio PRImparare un modello, usando i giudizi dell’esperto,
in un esperimento
spots (raw data)
x1
x2
...
xN
features
y1
y2
...
yN
etichette degli esperti
Addestramento del modello
![Page 98: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/98.jpg)
L’approccio PRTesting: per un esperimento qualsiasi
per ogni spot: buono o non buono
spots (raw data)modello addestrato
x1
x2
...
xN
features
![Page 99: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/99.jpg)
PR e Bioinformatica (more)
Applicazioni legate alle immagini:Rilevamento (detection) di parti interessanti
in immaginispots in microarray
gel
immagini mediche
misurecalcolo di feature (e.g. rotondità degli spot nei
microarray)
presenza / assenza di elementi
![Page 100: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/100.jpg)
PR e Bioinformatica (more)
Ricerche nei database (GenBank, PDB)
sequenze:trovare similarità tra sequenze (e.g. BLAST,
FASTA)
PR: similarità trovate utilizzando modelli addestrati
documenti: estrazione di informazioni rilevanti
PR: retrieval by content (invece della classica ricerca per keywords)
PR: classificazione di documenti
![Page 101: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/101.jpg)
Sfide Enorme complessità e
diversità dei sistemi biologici
Enorme quantità di dati
Esempio: > 13K Completed Genome Projects - www.genomesonline.org
Potenziale crescita esplosiva (e.g. il 95% della biodiversità microbica è sconosciuta)
![Page 102: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/102.jpg)
Sfide
E' difficile comunicare
Aspettative differenti
Background differenti
Linguaggi differenti!!
Necessità di interagire con medici e biologi
![Page 103: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/103.jpg)
Sfide
Necessità di utilizzare il più possibile le informazioni biologiche note a priori
Ricerca della “interpretabilità biologica” di:metodologie sviluppate
soluzioni ottenute
![Page 104: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/104.jpg)
Il programma del corso
![Page 105: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/105.jpg)
Programma dettagliato
CAPITOLO 1. Introduzione
Introduzione generale alla Pattern Recognition: cos’è, cosa serve, com'è fatto un tipico sistema di PR
CAPITOLO 2. Rappresentazione
Rappresentazione dei dati, feature/pattern, preprocessing
CAPITOLO 3. Classificazione
Schema di classificazione, Regola di decisione di Bayes, K-Nearest Neighbor, Support Vector Machines, validazione
![Page 106: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/106.jpg)
Programma dettagliato
CAPITOLO 4. Clustering
Misure di similarità tra dati, tecniche di clustering, validazione
CAPITOLO 5. Altre tecniche
Hidden Markov Models, Reti Neurali
CAPITOLO 6. Applicazioni
classificazione e clustering di dati microarray, analisi di immagini biomedicali (cenni), Classificazione di omologia remota tra proteine
![Page 107: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/107.jpg)
Riviste e convegni principali (sul tema generale)
Convegni NIPS, ICML, ECML, CVPR, AI, ICPR, ICCV, ECCV, ICIP, etc.
Journals PAMI, IEEE Trans. on Pattern Analysis & Machine Intelligence Artificial Intelligence Machine Learning Journal of Machine Learning Research CVIU, Computer Vision and Image Understanding GMIP, Graphical Models & Image Processing IVC, Image and Vision Computing PR, Pattern Recognition PRL, Pattern Recognition Letters IEEE Trans. on Image Processing IEEE Trans. on Systems, Man, & Cybernetics Int. J. on Pattern Recognition & Artificial Intelligence IEEE Trans. on Neural Networks Neural Computation Proceedings of the IEEE
![Page 108: Gestione e modellazione di dati bioinformatici implementati in matlab semplici algoritmi di pattern recognition. ... presentazione penultima o ultima ... Algoritmi genetici. Altri](https://reader031.vdocumenti.com/reader031/viewer/2022030413/5a9e9aa27f8b9a84178b8dd3/html5/thumbnails/108.jpg)
Convegni molti, parole chiave bioinformatics, computational biology,
medical informatics, pattern matching, systems biology, AI in Medicine, etc.
Journals Bioinformatics BMC Bioinformatics Journal of Bioinformatics & Computational Biology IEEE/ACM Trans. on Computatinal Biology & Bioinformatics Int’l Journal of Data Mining & Bioinformatics Eurasip Journal of Bioinformatics & Systems Biology Int’l Journal of Bioinformatics Research and Applications Journal of Biomedical Informatics Journal of Computational Biology Journal of Proteomics & Bioinformatics Journal of Integrative Bioinformatics The Open Bioinformatics journal
Riviste e convegni principali (specifici su Bioinfo)