Suboptimal Alignments

Suboptimal alignments

The -suboptimal alignments have to be a subset of the paths that can be traced through . Those paths can be enumerated in a rooted tree in the following way: We think of as a subgraph of the type I graph, i.e. there is an arc between the points whenever there is one in the type I graph. The root of the tree corresponds to the sink . From the root a branch is introduced for every point in that is connected to the sink by an arc. Generally a branch from a node of the tree (corresponding to a point (i,j) in ) is introduced for each (k,l) for which there is an arc from (k,l) to (i,j) in the type I graph. Then every path from the leaves to the root of the tree corresponds to an alignment and every path that can be traced in is represented. As pointed out above, such a path may score worse than .

Therefore the next task is to exclude the paths which score under the cutoff. Consider two inner nodes of the tree (corresponding to points (i,j) and (k,l) in ) that are linked by an edge from the first one to the second one. Due to the construction of the tree (k,l) is a predecessor of (i,j) in the type I graph. Similarly to the computation of the suboptimal points, the score of a branch (alignment) consists of the score from the root to and including the inner node (i,j) (=: t(i,j)), the gap penalty G((i,j),(k,l)) to get from (i,j) along a branch to (k,l) and the score from (k,l) to the end of a path (which can at best be L^-(k,l)). When inspecting the tree in a depth first search, t(i,j) can be computed while calculating down a path. t(i,j) is initialized to w(i,j) for i=|s| or j=|t|. Then being in node (i,j) a branch leading to (k,l) is accepted iff
(Algorithm SOA)