ETD system

Electronic theses and dissertations repository

 

Tesi etd-09292004-015610


Thesis type
Tesi di laurea specialistica
Author
Felicioli, Claudio
email address
c.felicioli@1d20.net
URN
etd-09292004-015610
Title
Sulla distanza di mutazione tra sequenze biologiche
Struttura
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
INFORMATICA
Commissione
relatore Marangoni, Roberto
relatore Prof. Luccio, Fabrizio
Parole chiave
  • algorithms
  • transformation distance
  • paralogy trees
Data inizio appello
15/10/2004;
Consultabilità
completa
Riassunto analitico
BpMatch è un nuovo algoritmo la cui funzione è di calcolare efficientemente, date le sequenze S e T, la massima copertura di T utilizzando solo sottosequenze e sottosequenze invertite complementate di S, di lunghezza minima l, eventualmente sovrapposte, e, nella copertura massima, di minimizzare il numero di sottosequenze utilizzate.
Il problema viene risolto eseguendo una preelaborazione di S (indipendentemente dalla sequenza di cui successivamente verrà poi cercata la massima copertura e, quindi, preelaborazione da effettuare una sola volta e valida per ogni T), generando un grafo che permetta un rapido riconoscimento delle sottosequenze di S.
I grafi G e G' devono essere generati rispettivamente dalla sequenza S e da S invertita e complementata, poi, utilizzando G, G' e T, il calcolo della copertura massima può essere computato in tempo O(u*log(log(n))) (n=|S| e u=|T|) nel caso medio ed in spazio lineare.
File