ETD

• algorithms
• paralogy trees
• transformation distance

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.