Let us now have a closer look on how lower and upper bounds are derived.

Obtaining an inaccurate upper bound on δ(s, t) is fairly easy, since we can use the cost of any valid path through the lattice. Better estimates are available from heuristic linear-time alignment programs.

In Section 1.7.6, we have already seen how lower bounds on the k-alignment are often based on optimal pairwise alignments; usually, prior to the main search, these subproblems are solved in a backward direction, by ordinary dynamic programming, and the resulting distance matrix is stored for later access.

Let U* be an upper bound on the cost of an optimal multiple sequence alignment G. The sum of all optimal alignment costs for pairwise subproblems , call it L, is a lower bound on G. Carrillo and Lipman pointed out that by the additivity of the sum-of-pairs cost function, any pairwise alignment induced by the optimal multiple sequence alignment can at most be δ = U − L larger than the respective optimal pairwise alignment. This bound can be used to restrict the number of values that have to be computed in the preprocessing stage and have to be stored for the calculation of the heuristic: For the pair of sequences i, j, only those nodes v are feasible such that a path from the start node s_{i, j} to the goal node t_{i, j} exists with total cost no more than L_{i, j}+δ. To optimize the storage requirements, we can combine the results of two searches. First, a forward pass determines for each relevant node v the minimum distance d(s_{i, j}, v) from the start node. The subsequent backward pass uses this distance like an exact heuristic and stores the distance d(v, t_{i, j}) from the target node only for those nodes with .

Still, for larger alignment problems the required storage size can be extensive. In some solvers, the user is allowed to adjust δ individually for each pair of sequences. This makes it possible to generate at least heuristic alignments if time or memory doesn't allow for the complete solution; moreover, it can be recorded during the search if the δ-bound was actually reached. In the negative case, optimality of the found solution is still guaranteed; otherwise, the user can try to run the program again with slightly increased bounds.

The general idea of precomputing simplified problems and storing the solutions for use as a heuristic is the same as in searching with pattern databases. However, these approaches usually assume that the computational cost can be amortized over many search instances to the same target. In contrast, many heuristics are instance-specific, such that we have to strike a balance.

As we have seen, a fixed search order as in dynamic programming can have several advantages over pure best-first selection.

The remaining issue of a static exploration scheme consists of adequately bounding the search space using the h-values. A* is known to be minimal in terms of the number of node expansions. If we knew the cost δ(s, t) of a cheapest solution path beforehand, we could simply proceed level by level of the grid, however, only immediately prune generated edges e whenever . This would ensure that we only generate those edges that would have been generated by algorithm A* as well. An upper threshold would additionally help reduce the size of the Closed list, since a node can be pruned if all of its children lie beyond the threshold; additionally, if this node is the only child of its parent, this can give rise to a propagating chain of ancestor deletions.

We propose to apply a search scheme that carries out a series of searches with successively larger thresholds until a solution is found (or we run out of memory or patience). The use of such an upper bound parallels that in the IDA* algorithm.

The resulting algorithm, which we will refer to as iterative-deepening dynamic programming (IDDP), is sketched in Algorithm 18.1. The outer loop initializes the threshold with a lower bound (e.g., h(s)), and, unless a solution is found, increases it up to an upper bound. In the same manner as in the IDA* algorithm, to make sure that at least one additional edge is explored in each iteration, the threshold has to be increased correspondingly at least to the minimum cost of a fringe edge that exceeded the previous threshold. This fringe increment is maintained in the variable minNextThresh, initially estimated as the upper bound, and repeatedly decreased in the course of the following expansions.

In each step of the inner loop, we select and remove a node from the priority queue of which the level is minimal. As explained later in Section 18.2.5, it is favorable to break ties according to the lexicographic order of target nodes. Since the total number of possible levels is comparatively small and known in advance, the priority queue can be implemented using an array of linked lists; this provides constant time operations for insertion and deletion.

When the search progresses along antidiagonals, we do not have to fear back leaks, and are free to prune Closed nodes. We only want to delete them lazily and incrementally when being forced to by the algorithm approaching the computer's memory limit, however.

When deleting an edge e, the backtrack pointers of its child edges that refer to it are redirected to the respective predecessor of e, the reference count of which is increased accordingly. In the resulting sparse solution path representation, backtrack pointers can point to any optimal ancestors.

After termination of the main search, we trace back the pointers starting with the goal edge; this is outlined Alg. 18.5, which prints out the solution path in reverse order. Whenever an edge e points back to an ancestor e′ that is not its direct parent, we apply an auxiliary search from start edge e′ to goal edge e to reconstruct the missing links of the optimal solution path. The search threshold can now be fixed at the known solution cost; moreover, the auxiliary search can prune those edges that cannot be ancestors of e because they have some coordinate greater than the corresponding coordinate in e. Since also the shortest distance between e and e′ is known, we can stop at the first path that is found at this cost. To improve the efficiency of the auxiliary search even further, the heuristic could be recomputed to suit the new target. Therefore, the cost of restoring the solution path is usually marginal compared to that of the main search.

Which edges are we going to prune, in which order? For simplicity, assume for the moment that the Closed list consists of a single solution path. According to the Hirschberg approach, we would keep only one edge, preferably lying near the center of the search space (e.g., on the longest antidiagonal), to minimize the complexity of the two auxiliary searches. With additional available space allowing us to store three relay edges, we would divide the search space into four subspaces of about equal size (e.g., additionally storing the antidiagonals halfway between the middle antidiagonal and the start node respectively the target node). By extension, to incrementally save space under diminishing resources we would first keep only every other level, then every fourth, and so on, until only the start edge, the target edge, and one edge halfway on the path would be left.

Since in general the Closed list contains multiple solution paths (more precisely, a tree of solution paths), we would like to have about the same density of relay edges on each of them. For the case of k sequences, an edge reaching level l with its head node can originate with its tail node from level l − 1,…, l − k. Thus, not every solution path passes through each level, and deleting every other level could result in leaving one path completely intact, while extinguishing another totally. Thus, it is better to consider contiguous bands of k levels each, instead of individual levels. Bands of this size cannot be skipped by any path. The total number of antidiagonals in an alignment problem of k sequences of length N is k⋅N − 1; thus, we can decrease the density in steps.

A technical implementation issue concerns the ability to enumerate all edges that reference some given prunable edge, without explicitly storing them in a list. However, the reference counting method described earlier ensures that any Closed edge can be reached by following a path bottom-up from some edge in Open. The procedure is sketched in Algorithm 18.6. The variable sparse denotes the interval between level bands that are to be maintained in memory. In the inner loop, all paths to Open nodes are traversed in a backward direction; for each edge e′ that falls into a prunable band, the pointer of the successor e on the path is redirected to its respective backtrack pointer. If e was the last edge referencing e′, the latter one is deleted, and the path traversal continues up to the start edge. When all Open nodes have been visited and the memory bound is still exceeded, the outer loop tries to double the number of prunable bands by increasing sparse.

The procedure SparsifyClosed is called regularly during the search, for example, after each expansion. However, a naive version as described earlier would incur a huge overhead in computation time, particularly when the algorithm's memory consumption is close to the limit. Therefore, some optimizations are necessary. First, we avoid tracing back the same solution path at the same (or lower) sparse interval by recording for each edge the interval when it was traversed the last time (initially zero); only for an increased variable sparse can there be anything left for further pruning. In the worst case, each edge will be inspected times. Second, it would be very inefficient to actually inspect each Open node in the inner loop, just to find that its solution path has been traversed previously, at the same or higher sparse value; however, with an appropriate bookkeeping strategy it is possible to reduce the time for this search overhead to O(k).

As we have seen, the estimator h_pair, the sum of optimal pairwise goal distances, gives a lower bound on the actual path length. The tighter the estimator is, the smaller the search space the algorithm has to explore.