logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-06102022-190809


Tipo di tesi
Tesi di laurea magistrale
Autore
BELFIORE, ALESSANDRO
URN
etd-06102022-190809
Titolo
Colouring ED strings: an on-line algorithm to avoid false positive matches
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
relatore Prof.ssa Pisanti, Nadia
Parole chiave
  • degenerate string
  • elastic string
  • false positive
  • pan-genome
  • pangenoma
  • pangenome
  • pattern matching
  • survey
Data inizio appello
01/07/2022
Consultabilità
Tesi non consultabile
Riassunto
Prendiamo in rassegna i principali algoritmi usati nell'ambito del pattern matching on-line sui pan-genomi, con particolare attenzione agli algoritmi che usano il formato EDS. Formuliamo una definizione di EDS "colorate", aggiungendo al problema le informazioni relative alle sorgenti dei genomi, e presentiamo una soluzione on-line che risolve questo problema con complessità O(Nm) dove N rappresenta la dimensione del testo e m la lunghezza del pattern, quando m è minore della lunghezza della parola di macchina. Infine implementiamo due possibili algoritmi basati su recenti algoritmi che costituiscono lo stato dell'arte e analizziamo i risultati.

We survey the most important algorithms used in pattern matching on pan-genomes, with a particular focus on algorithms employing the EDS format. We then formulate a definition of "coloured" EDS, augmenting the setting with information on the sources of the data and we present an on-line algorithm solving the problem in O(Nm), where N is the size of the text, m the size of the pattern, and m is smaller than the size of the computer word. Lastly we implement two possible algorithms based on recent state-of-the-art algorithms, and we analyze the results.
File