Presentazione Laurea Esame di Stato

Università degli Studi di Salerno

Tesi di laurea in informatica

Studio e analisi di strutture dati efficienti per la compressione di sequenze di DNA

Relatore: Prof. Rosalba Zizza Laureando: Serena Iannuzzi Anno Accademico: 2018/2019

Comprimere DNA

Una sequenza di DNA:

• È una successione di lettere che rappresentano la struttura primaria di una molecola di DNA.

Perché comprimerlo?

• Per distinguere tra le due regioni di una sequenza di DNA: codificante e non codificante.
• Utile per valutare la distanza tra le sequenze di DNA.
• Ecc...

Serena Iannuzzi

Obiettivo

Stiamo estendendo il nuovo approccio per costruire Suffix Arrays incrementali usando la Fattorizzazione di Lyndon alla costruzione dei Suffix Array estesi (SUNITA e DEEPAK GARG, 2018, “Extended suffix array construction using Lyndon factors”).

Serena Iannuzzi

Suffix Array esteso

Esistono due modi per realizzarlo:

• Il primo consiste nel costruire il Suffix Array e, una volta completata la costruzione del Suffix Array, utilizzarlo per costruire l’array LCP.
• Il secondo consiste nel costruire in modo incrementale il Suffix Array e insieme al Suffix Array calcolare anche l’array LCP di volta in volta.

Serena Iannuzzi

Suffix Array

• Potente strumento per comprimere dati.
• Struttura dati ottenuta ordinando i suffissi di una stringa in ordine lessicografico.

Serena Iannuzzi

Suffix Array - esempio

Testo S = informatica da indicizzare: suffissi ordinati in ordine crescente:

Il Suffix Array è {10, 6, 9, 2, 8, 0, 5, 1, 3, 4, 7}