Gianluca Demartini
building Data Scientists since 2014

Algoritmo di Landau-Vishkin: implementazione

Tesi in formato pdf (scaricata 1522 volte da luglio 2011)

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.

1. Introduzione
2. Allineamento di sequenze con errori
3. Contesto storico
4. Un algoritmo inefficiente per l’allineamento di stringhe con errori
5. Algoritmo di Landau-Vishkin
5.1 Struttura dell’algoritmo
5.2 Suffix Tree
5.2.1 Trovare il Lowest-Common-Ancestor in tempo costante
5.3 Pseudo-codice dell’algoritmo di Landau-Vishkin
5.4 Complessità dell’algoritmo di Landau-Vishkin
5.4.1 Complessità utilizzando un suffix tre
6. Descrizione del codice sorgente
6.1 File Alg.H
6.2 File Main.C
6.2.1 La funzione main
6.3 File Triple.C
6.3.1 La funzione addTriple
6.3.2 La funzione findCover
6.4 File BuildMaxLen.C
6.4.1 La funzione build_maxlen
6.5 File File.C
6.5.1 La funzione openpattern
6.5.2 La funzione opentext
6.5.3 La funzione writeresults
6.5.4 La funzione fsize
6.6 File Check.C
6.6.1 La funzione check
7. Testing dell’implementazione
8. Conclusioni
Bibliografia

Gianluca Demartini, Ph.D.
Information School, University of Sheffield

Regent Court
211 Portobello Road
S1 4DP Sheffield, UK

Office: +44 114 222 2637
Mobile: +39 349 5119466
http://diuf.unifr.ch/main/en/staff#eXascale_

Photo of Gianluca

Dr. Gianluca Demartini is a Senior Lecturer in Data Science at the University of Sheffield, Information School. His research is currently supported by the UK Engineering and Physical Sciences Research Council (EPSRC) and by the EU H2020 framework program. His main research interests are Information Retrieval, Semantic Web, and Human Computation. He received the Best Paper Award at the European Conference on Information Retrieval (ECIR) in 2016 and the Best Demo Award at the International Semantic Web Conference (ISWC) in 2011. He has published more than 70 peer-reviewed scientific publications including papers at major venues such as WWW, ACM SIGIR, VLDBJ, ISWC, and ACM CHI.
He has given several invited talks, tutorials, and keynotes at a number of academic conferences (e.g., ISWC, ICWSM, WebScience, and the RuSSIR Summer School), companies (e.g., Facebook), and Dagstuhl seminars. He is an ACM Distinguished Speaker since 2015.
He serves as area editor for the Journal of Web Semantics, as Student Coordinator for ISWC 2017, and as Senior Program Committee member for the AAAI Conference on Human Computation and Crowdsourcing (HCOMP), the International Conference on Web Engineering (ICWE), and the ACM International Conference on Information and Knowledge Management (CIKM). He is Program Committee member for several conferences including WWW, SIGIR, KDD, IJCAI, ISWC, and ICWSM. He was co-chair for the Human Computation and Crowdsourcing Track at ESWC 2015. He co-organized the Entity Ranking Track at the Initiative for the Evaluation of XML Retrieval in 2008 and 2009.
Before joining the University of Sheffield, he was post-doctoral researcher at the eXascale Infolab at the University of Fribourg in Switzerland, visiting researcher at UC Berkeley, junior researcher at the L3S Research Center in Germany, and intern at Yahoo! Research in Spain. In 2011, he obtained a Ph.D. in Computer Science at the Leibniz University of Hanover focusing on Semantic Search.

Algoritmo di Landau-Vishkin: implementazione

Tesi in formato pdf (scaricata 1522 volte da luglio 2011)

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.

1. Introduzione
2. Allineamento di sequenze con errori
3. Contesto storico
4. Un algoritmo inefficiente per l’allineamento di stringhe con errori
5. Algoritmo di Landau-Vishkin
5.1 Struttura dell’algoritmo
5.2 Suffix Tree
5.2.1 Trovare il Lowest-Common-Ancestor in tempo costante
5.3 Pseudo-codice dell’algoritmo di Landau-Vishkin
5.4 Complessità dell’algoritmo di Landau-Vishkin
5.4.1 Complessità utilizzando un suffix tre
6. Descrizione del codice sorgente
6.1 File Alg.H
6.2 File Main.C
6.2.1 La funzione main
6.3 File Triple.C
6.3.1 La funzione addTriple
6.3.2 La funzione findCover
6.4 File BuildMaxLen.C
6.4.1 La funzione build_maxlen
6.5 File File.C
6.5.1 La funzione openpattern
6.5.2 La funzione opentext
6.5.3 La funzione writeresults
6.5.4 La funzione fsize
6.6 File Check.C
6.6.1 La funzione check
7. Testing dell’implementazione
8. Conclusioni
Bibliografia