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

Tesi per la facoltà di Scienze matematiche fisiche e naturali, dell'università degli Studi di Salerno - unisa elaborata dall’autore nell’ambito del corso di Esame di Stato tenuto dalla professoressa Zizza dal titolo Studio e analisi di strutture dati efficienti per la compressione di sequenze di DNA. Scarica il file in formato PDF!

Esame Esame di Stato

Facoltà Scienze matematiche fisiche e naturali

Università Università degli Studi di Salerno

Publisher serena995

A.A. 2020-2021

50 pagine

Tesi

Vota

Scarica

Estratto del documento

Formattazione del testo

Abbiamo tre casi possibili:

Caso 1: nell'albero corrente il cammino etichettato S[j, i] termina in una foglia numerata j. In questo caso il nuovo carattere S[i+1] viene aggiunto all'etichetta dell'ultimo arco di tale cammino (quello che termina nella foglia).

Caso 2: nell'albero corrente il cammino etichettato S[j, i] termina in un nodo interno (implicito o esplicito) ma nessun cammino che parte da u inizia con il carattere S[i+1]. In questo caso viene creata una nuova foglia etichettata j connessa al nodo u con un arco etichettato con il carattere S[i+1]. Nel caso in cui u sia un nodo implicito, prima di fare ciò, il nodo u viene sostituito con un nodo esplicito che suddivide in due parti l'arco a cui esso appartiene.

Caso 3: nell'albero corrente il cammino etichettato S[j, i] termina in un nodo interno (implicito o esplicito) e almeno un cammino che parte da u inizia con il carattere S[i+1]. In questo caso il suffisso S[j, i+1] è già...

presente nell'albero e non occorre fare niente. Dopo aver esteso tutti i suffissi di S[1, i] siamo sicuri che nell'albero ottenuto sono rappresentati tutti i suffissi di S[1, i+1]. Infatti ogni suffisso non nullo di S[1, i+1] è estensione di un suffisso di S[1, i] ed il suffisso nullo è sempre rappresentato in ogni albero dei suffissi implicito.

Esempio: T= informatica$ È possibile osservare tutti i passi dello svolgimento sul sito http://brenden.github.io/ukkonen-animation/.

I Suffix Trees sono stati impiegati intensamente nei problemi di Pattern Matching (corrispondenza del modello) su stringhe, matrici e alberi.

Un tipico problema di Pattern Matching consiste nel localizzare tutte le occorrenze di una determinata stringa, matrice o albero, chiamato modello (pattern), come una sottostruttura di un'altra stringa, matrice o albero, chiamata testo. I problemi di corrispondenza dei modelli hanno una vasta gamma di applicazioni, come biologia molecolare,

Elaborazione dei dati, modifica del testo, riscrittura dei termini, progettazione dell'interprete, recupero delle informazioni, tipi di dati astratti e molti altri.

In generale il problema del Pattern Matching è definito come segue: Σ.∈INPUT: stringa di testo T = t t ... t e stringa pattern P = p p ... p , t , p1 2 n 1 2 m i iOUTPUT: tutte le posizioni i in T , in cui si verifica un'occorrenza di P, ovvero ≤T[i+k] = P [k], 1 ≤ k < m.

La soluzione con l'uso del Suffix Tree è la seguente: dato un modello di carattere (pattern) m P[0...m-1] e un testo di carattere n T[0...n-l'insieme di posizioni in T in cui P di verifica.1], riporta Se una struttura dati del Suffix Tree è costruita da T, allora i pattern possono essere localizzati nel testo in tempo O(m+occ), dove occ è il numero di occorrenze del modello P in T. dell'efficienza dello spazio Il miglioramento della struttura dati del Suffix Array e quindi anche del Suffix Tree.

Introduzione alle strutture dati compressi per la corrispondenza dei modelli

La ricerca di pattern all'interno di un testo è un'operazione comune nell'informatica. Per migliorare le prestazioni di questa operazione, sono state sviluppate nuove classi di strutture dati astratte, come il suffix array compresso e il suffix tree compresso.

Suffix Array Compresso

Il Suffix Array Compresso è una struttura dati compressa che migliora il Suffix Array nella corrispondenza dei modelli. Queste strutture dati consentono una ricerca rapida di una stringa arbitraria con un indice relativamente piccolo.

Dato un testo T di n caratteri da un alfabeto Σ, il Suffix Array compresso supporta la ricerca di pattern arbitrari in T. Per un modello di input P di m caratteri, il tempo di ricerca è tipicamente O(m) o O(m + log(n)). Lo spazio utilizzato è in generale l'entropia empirica O(nH(T)) + O(n), dove H(T) è l'entropia del testo T di ordine k.

Il tempo e lo spazio necessari per costruire un suffisso compresso sono normalmente O(n). Gli accessi alla memoria effettuati da suffix array compressi e altre strutture di dati compressi per la corrispondenza dei modelli non sono in genere localizzati, e quindi queste strutture di dati offrono un'efficienza notevole.

utilizzo di strutture di dati complesse per rappresentare e manipolare i dati. Tuttavia, esistono diverse implementazioni open source che permettono di gestire in modo efficiente array di suffissi compressi. Bowtie e Bowtie2 sono due implementazioni open source di array di suffissi compressi utilizzate per l'allineamento di letture nella bioinformatica. La Succinct Data Structure Library (SDSL) è una libreria che contiene diverse strutture di dati compressi, tra cui array di suffissi compressi. FEMTO è un'altra implementazione di array di suffissi compressi specificamente progettata per l'uso nella memoria esterna. Uno dei principali svantaggi dei Suffix tree è la loro elevata occupazione di memoria, che di solito è vicina a 20n byte per una sequenza di n simboli. Questo ha portato alla ricerca di rappresentazioni compressi dei Suffix tree, che operano in forma compressa. Il Suffix Tree compresso si ottiene arricchendo il Suffix Array compresso con alcuni dati extra. Sia i Suffix Tree che i Suffix Array richiedono l'utilizzo di strutture di dati complesse.

spazio O(n), ma mentre un'implementazione del Suffix Tree richiede 13-15 byte per carattere, per i Suffix Array sono sufficienti solo 5 + O(1) byte.

151.3. LCP (Longest Common Prefix)

L'array Longest Common Prefix [12] (array LCP) è una struttura di dati ausiliaria del Suffix Array. Memorizza le lunghezze dei prefissi comuni più lunghi tra coppie di suffissi consecutivi nella matrice di suffissi ordinati. In altre parole, è la lunghezza del prefisso che è comune tra i due suffissi consecutivi in un array di suffissi ordinati. ,…

Definizione: Sia A l'array di suffissi della stringa S = (s , s s ) e sia lcp (v, w) la lunghezza del prefisso comune più lungo tra due stringhe v e w. Indichiamo ulteriormente S [i…j] la sottostringa di S che va da i a j. Quindi l'array LCP H[1, n] è un array intero di dimensioni n tale che H[1] non è definito e H [i] = lcp(S [A[i-1],n], S [A[i], n]) per ogni 1 < i <= n.

Pertanto H_i memorizza la lunghezza del prefisso comune più lungo del lessicografo i-esimo suffisso più piccolo e il suo predecessore nella matrice di suffissi. L'array LCP è quindi un array di dimensione n le cui voci sono definite come: LCP[i] = -1 if i=0 lcp(suf[i-1], suf[i]) if 0Sappiamo che almeno k caratteri corrisponderanno.

17txt[0…n-1] = “informatica”

Esempio:

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

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

I suffissi rappresentati dall’array di suffissi ordinato sono:

{"a", "atica", "ca", "formatica", "ica", "informatica",“matica”, “nformatica”, “ormatica”, “rmatica”, “tica”}

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

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

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

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

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

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

lcp[6] = Longest Common Prefix di “matica”

“nformatica” = 0lcp[7] = Longest Common Prefix di “nformatica”

e“ormatica” = 0lcp[8] = Longest Common Prefix di “ormatica”

e “rmatica”= 0 18lcp[9] = Longest Common Prefix di “rmatica”

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

e None = 0

1.4. Suffix Array esteso

Quindi, come abbiamo già accennato all’inizio del documento, il Suffix Array esteso è semplicemente il Suffix Array di una stringa con il relativo LCP.

Esistono due modi per realizzare il Suffix Array esteso: uno, quello utilizzato finora da me, consiste nel costruire il Suffix Array e, una volta completata la costruzione del Suffix Array, utilizzarlo per costruire l’array LCP. In questo caso la complessità di tempo è O(n log n) per la costruzione del Suffix Array e O(n) per calcolare LCP del Suffix Array.

Un altro metodo consiste nel costruire in modo incrementale il Suffix Array dividendo

Il testo in blocchi di dimensioni adeguate e insieme al Suffix Array calcolare anche l'array LCP fianco a fianco. Anche questo metodo è efficiente in termini di spazio poiché la costruzione viene eseguita blocco per blocco.

È stata introdotta una nuova strategia, come già accennato all'inizio, per la costruzione incrementale del Suffix Array esteso utilizzando la Fattorizzazione di Lyndon che apre nuovi scenari per la costruzione efficiente in termini di spazio delle diverse varianti di Suffix Array comprese quelle di cui ho parlato: Suffix Array estesi e Suffix Array compressi.

Questa strategia sarà esposta più avanti, dopo aver parlato approfondito la Fattorizzazione di Lyndon e la costruzione del Suffix Array incrementale.

Infine il Capitolo 4, presenta più approfonditamente la costruzione del Suffix Array esteso usando i fattori di Lyndon.

Capitolo 2

Fattorizzazione di Lyndon

2.1. Nozioni di base

Dato due stringhe x e x', x

′ è una rotazione di x se x = uv e x ′ = vu, per alcune stringhe u e v. Più precisamente, ricordiamo che due parole x, y sono chiamate coniugate^[7] se esistono parole u, v tali che x = uv, y = vu. La relazione di coniugazione è una relazione di equivalenza. Una classe di coniugazione è una classe di questa relazione di equivalenza.

Le parole di Lyndon (Lyndon words) prendono il nome dal matematico Roger Lyndon che le introdusse nel 1954 sotto il nome di sequenze lessicografiche standard. Una parola si dice primitiva se non è potenza di un'altra parola. Una parola primitiva è chiamata parola di Lyndon^[14] se è strettamente più piccola di tutti i suoi suffissi. Esistono diverse proprietà reciprocamente equivalenti delle parole di Lyndon, tra cui:

Lemma

Anteprima

Vedrai una selezione di 11 pagine su 50