title: Heuristic reusable dynamic programming: efficient updates of local sequence alignment.
abstract: Recomputation of the previously evaluated similarity results between biological sequences becomes inevitable when researchers realize errors in their sequenced data or when the researchers have to compare nearly similar sequences, e.g., in a family of proteins. We present an efficient scheme for updating local sequence alignments with an affine gap model. In principle, using the previous matching result between two amino acid sequences, we perform a forward-backward alignment to generate heuristic searching bands which are bounded by a set of suboptimal paths. Given a correctly updated sequence, we initially predict a new score of the alignment path for each contour to select the best candidates among them. Then, we run the Smith-Waterman algorithm in this confined space. Furthermore, our heuristic alignment for an updated sequence shows that it can be further accelerated by using reusable dynamic programming (rDP), our prior work. In this study, we successfully validate "relative node tolerance bound" (RNTB) in the pruned searching space. Furthermore, we improve the computational performance by quantifying the successful RNTB tolerance probability and switch to rDP on perturbation-resilient columns only. In our searching space derived by a threshold value of 90 percent of the optimal alignment score, we find that 98.3 percent of contours contain correctly updated paths. We also find that our method consumes only 25.36 percent of the runtime cost of sparse dynamic programming (sDP) method, and to only 2.55 percent of that of a normal dynamic programming with the Smith-Waterman algorithm.
authors.affiliation: Department of Electrical Engineering, University of Minnesota, 4-192 EE/CSCI Building, 200 Union St. SE, Minneapolis, MN 55455, USA. hong@cs.umn.edu
authors.forename: Changjin
authors.initials: C
authors.lastname: Hong
authors.forename: Ahmed H
authors.initials: AH
authors.lastname: Tewfik
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D019295:Computational Biology / Q000379:methods*; D003196:Computer Graphics; D006801:Humans; D010363:Pattern Recognition, Automated; D011381:Programming Languages; D011506:Proteins / Q000737:chemistry; D015203:Reproducibility of Results; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods; D012815:Signal Processing, Computer-Assisted; D012984:Software
chemical_list: D011506:Proteins