The purpose of this algorithm is to calculate, given
sequences S and T, the maximum coverage of T using
only subsequences and reverse subsequences of S, with
a minimum length of l, eventually overlapped, and, in such
maximum coverage, minimizing the number of subsequences used.
The problem is solved executing a preelaboration of S (unrelated
from the sequence where the maximum coverage will be later searched,
so usable for every possible T) generating a graph who
enables to quickly recognize S subsequences.
First, we need to generate graph G from S and graph G'
from S reversed, then, using G, G' and T,
a fast calculation give the T maximum coverage.
|