La funzione dell'algoritmo è di calcolare, date le
sequenze S e T, la copertura massima di T utilizzando
solo sottosequenze e sottosequenze inverse e complementate di S, con lunghezza
minima l, eventualmente sovrapposte tra di loro, ed in tale copertura
massima minimizzare il numero di sequenze utilizzate. Il problema è
stato risolto eseguendo una preelaborazione di S (indipendente
dalla sequenza sulla quale si andrà poi a cercare la copertura massima e
quindi utilizzabile per ogni possibile T) generando un grafo che
permette di riconoscere rapidamente le sottosequenze di S. Si generano
quindi il grafo G usando S ed il grafo G' usando
S invertito e complementato, utilizzando poi G, G' e T si
esegue un calcolo rapido della copertura massima.
|