logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-06182008-085952


Tipo di tesi
Tesi di laurea specialistica
Autore
LOMBARDO, ROSARIO
URN
etd-06182008-085952
Titolo
Algoritmi efficienti per la scoperta di pattern ripetuti a intervalli
Dipartimento
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
INFORMATICA
Relatori
Relatore Prof. Grossi, Roberto
Relatore Prof. Marangoni, Roberto
Parole chiave
  • common interval
  • data mining
  • genome analysis
  • maximal notation
  • motif
  • permutation pattern
  • PQ tree
  • suffix tree
Data inizio appello
18/07/2008
Consultabilità
Parziale
Data di rilascio
18/07/2048
Riassunto
Dal momento che non esiste ancora sufficiente conoscenza per costruire un adeguato modello dell'informazione, e tale da filtrare sequenze di caratteri rilevanti da altre apparentemente senza significato, si ricorre spesso ad approcci che non prevedono l'uso di un modello di dati. La formulazione di notazioni massimali, senza introdurre perdita d'informazione, cattura importanti caratteristiche sulla struttura interna dei motif e ne riduce drasticamente il numero da analizzare, conferendo un senso all'enorme numero di risultati.

In questa tesi propongo un approccio alla codifica delle sequenze nucleotidiche altamente ridondanti, tale da produrre permutazioni numeriche. Questa metodologia, che usa i Suffix Tree, mira a generare codifiche esenti da alterazioni o artefatti dell'informazione genetica producendo, per design, permutazioni "compatibili" con i minimal consensus PQ Tree, i quali sono usati per la creazione della notazione massimale. Si forniscono le motivazioni che hanno ispirato questo approccio, basato sull'analisi della struttura permutativa interna delle stringhe. Si delineano alcuni possibili sviluppi e si forniscono molti esempi accompagnati da un caso d'uso reale.
File