Presentazione Laurea Esame di Stato

DNA• ecc...Serena Iannuzzi

2Università degli Studi di Salerno

Tesi di Laurea in Informatica

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

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

3Università degli Studi di Salerno

Tesi di Laurea in Informatica

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

Suffix Array esteso

Esistono due modi per realizzarlo: Il secondo consiste nel costruire in modo incrementale il Suffix Array e, una volta completata la costruzione del Suffix Array, utilizzarlo anche l’array LCP di volta in volta.

Serena Iannuzzi

Università degli Studi di Salerno

Tesi di Laurea in Informatica

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

Suffix Array

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

Serena Iannuzzi

Università degli Studi di Salerno

Tesi di Laurea in Informatica

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

Suffix Array - esempio

Testo S = informatica

da indicizzare: suffissi ordinati in ordine crescente:

Serena Iannuzzi

Università degli Studi di Salerno

Tesi di Laurea in Informatica

in Informatica

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

LCP (Longest Common Prefix) è la lunghezza del prefisso più lungo che è comune tra i due suffissi consecutivi in un array di suffissi ordinati

suffix[] = {10, 6, 9, 2, 8, 0, 5, 1, 3, 4, 7}

txt[0…n-1] = "informatica"

lcp[] = {1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}

lcp[0] = Longest Common Prefix di "a" e "atica" = 1

lcp[6] = Longest Common Prefix di "matica" e "nformatica" = 0

lcp[1] = Longest Common Prefix di "atica" e "ca" = 0

lcp[7] = Longest Common Prefix di "nformatica" e "ormatica" = 0

lcp[2] = Longest Common Prefix di "ca" e "formatica" = 0

lcp[8] = Longest Common Prefix di "ormatica" e "rmatica" = 0

lcp[3] = Longest Common Prefix of "formatica" and "ica" = 0

lcp[9] = Longest Common Prefix di

“rmatica” e “tica” = 0

lcp[4] = Longest Common Prefix di "ica" e "informatica" = 1

lcp[10] = Longest Common Prefix di “tica” e None = 0

lcp[5] = Longest Common Prefix di "informatica" e "matica" = 0

Serena Iannuzzi 7

Università degli Studi di Salerno

Tesi di Laurea in Informatica

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

Suffix Array esteso

Esistono due modi per realizzarlo: Il secondo consiste nel costruire in modo incrementale il Suffix Array e, una volta completata la costruzione del Suffix Array, utilizzarlo anche l’array LCP di volta in volta.

Nuova strategia per la costruzione incrementale del Suffix Array esteso utilizzando la Fattorizzazione di Lyndon.

Serena Iannuzzi 8

Università degli Studi di Salerno

Tesi di Laurea in Informatica

Studio e

Analisi di strutture dati efficienti per la compressione di sequenze di DNA

Fattorizzazione di Lyndon

Data una parola x, la parole non vuote e strettamente più piccole della Fattorizzazione di Lyndon, è una sequenza di tutte le loro sotto-sequenze di parole di Lyndon, in modo tale che le parole nella sequenza non aumentino lessicograficamente.

Esempi di Lyndon words:

• a
• ab
• aabab

Esempio: w = informatica

breaks = 2, 6, 10, 11. Non-Lyndon words factors = (in)(form)(atic)(a).

• ba
• abaac
• abcaac

Serena Iannuzzi

Università degli Studi di Salerno

Tesi di Laurea in Informatica

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

Costruzione del Suffix Array esteso

Dato T[1…n], calcolo la Fattorizzazione di Lyndon di T, L … L1 k

Per ogni fattore L calcolo SA e LCP (locale), a partire dall'ultimo

Merge (SA(L ), SA(L … L )) p p+1 k

Merge (LCP(L ), LCP (L … L )) p p+1 k

Correttezza: proprietà di

Compatibilità dei suffissi locali

Serena Iannuzzi

10