Gianluca Demartini
building Data Scientists since 2014

Il confronto approssimato tra stringhe è un settore molto importante in biologia computazionale. Questa importanza è spiegata dal fatto che i dati che si utilizzano non possono essere sempre corretti e quindi è intrinseca la presenza di errori nei dati che si hanno riguardo le molecole, e dal fatto che gli allineamenti spesso forniscono importanti informazioni riguardo la funzione di geni e proteine, infatti una forte somiglianza tra sequenze biomolecolari (DNA, RNA, sequenze di amminoacidi) di solito comporta una certa somiglianza strutturale o funzionale tra esse. Ovviamente queste sequenze codificano e riflettono la più complessa struttura che si ha in realtà a livello della cellula.
Un esempio in cui è appropriato l’uso di limitare il numero di differenze nell’allineamento di due sequenze biologiche è quello della localizzazione di geni le cui mutazioni causano, o contribuiscono, a certe malattie genetiche. Vengono confrontate sequenze di DNA che rappresentano geni di persone malate e di persone sane per trovare le differenze consistenti dato che molte malattie genetiche sono causate da cambiamenti molto piccoli in un gene.
Per risolvere questi problemi sono stati prodotti diversi algoritmi prima di quello proposto da Landau e da Vishkin, come ad esempio quelli basati su tecniche di programmazione dinamica o
quello proposto da E. Ukonnen con complessità comunque peggiori di quello qui studiato. Si vuole implementare l’algoritmo descritto da Gad M. Landau e Uzi Vishkin nell’articolo intitolato “Fast String Matching with k differences” e pubblicato nel 1988 sul “Journal of Computer and System Sciences”. L’obiettivo di questo algoritmo è di scoprire tutte le occorrenze di una stringa P
in un testo T accettando al più k errori durante il confronto.
In questo documento verrà dapprima presentato il problema generale dell’allineamento tra stringhe con le necessarie definizioni dei concetti essenziali, e quindi verranno presentati degli algoritmi che sono poi stati migliorati nel tempo fino a descrivere in dettaglio l’algoritmo di Landau-Vishkin presentando quali sono i suoi vantaggi rispetto ai precedenti. In fine vi sarà una descrizione del codice prodotto per realizzare l’implementazione dell’algoritmo studiato.
Per produrre l’implementazione dell’algoritmo di Landau-Vishkin si è per prima cosa implementato un algoritmo più semplice che risolve lo stesso problema con complessità peggiore (quello di Ukonnen), per poi modificare la parte fondamentale mantenendo la struttura del precedente, come fatto da Landau e da Vishkin con le loro idee. Un vantaggio dell’implementazione proposta è che i risultati vengono inseriti in un file e quindi possono essere riutilizzabili successivamente da altre applicazioni. Il difetto principale dell’implementazione invece è la sua complessità quadratica. Oltre al necessario miglioramento della complessità sarebbe utile sostituire l’utilizzo di file con l’utilizzo 6 di database sia per contenere le stringhe di input sia per contenere i risultati in output, in quanto la dimensione di questi, nell’utilizzo che ci si propone di effettuare, si suppone sia molto elevata e quindi si presenterebbero dei problemi di memoria fisica insufficiente a contenere i dati.