Improvements on Dynamic Programming for Bicriteria Pairwise Sequence Alignment

In this article, we consider dynamic programming algorithms for solving two bicriteria formulations of the pairwise sequence alignment problem. A pruning technique based on the comparison of lower and upper bounds is introduced that reduces the number of states to be processed. The experimental results suggest that this technique leads to a pruning of 5 % to 35 % for the four problem variants considered in this article.