9. For every node, we need to record the direction from where the minimum contribution is coming, so that we can do the traceback. There are 2^k -1 possible directions (3 directions for 2 sequences, 7 directions for 3 sequences). We can store this information using one integer/pointer for each matrix entry that is calculated. Additionally, we need to store the cost function/matrix, the gap costs used, and the sequences themselves. Their size is neglegible compared to the matrix.
Return to Chapter 3
Self-Assessment.