• degenerate string
• elastic string
• false positive
• pan-genome
• pangenoma
• pangenome
• pattern matching
• survey

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.