Assignments:

A simple pruning algorithm for a sequence graph is described in the appendix
of Heins article. In the following you should consider all possible sequence
graphs and not only those which can actually occur as a result of Heins or
Schwikowskis solution methods (which would probably be much harder to do).
Also assume that all paths in the sequence graph have the same length and
that the alphabet has the fixed size 4 (e.g. "ATGC").

1. Make your own formalized description of the algorithm.

2. Try to find the worst-case running time of the algorithm e.g. using
examples of worst-case behaviour.

3. Try to suggest one or more improvements to the algorithm with respect
to quality of solutions (size of the resulting graph) or with respect
to running time.

You are also welcome to refer to answers in existing literature or on the
web e.g. as a shortcut to item 2 (and maybe even item 3).

Deadline: March 16, 2005