Handling Updates of a Pairwise Sequence Alignment

Sequence alignment or decoding in molecular biology is mostly done via computationally expensive dynamic programming (DP) based approaches. Unfortunately, as sequencing errors are discovered frequently, researchers must repeat all previous similarity analysis for the erroneous sequence. This can take hours or days. In this work, we derive relative tolerance bounds on node distances from a root node that guarantee that partial shortest path distances remain optimal. We then propose an algorithm that uses these bounds to skip all unperturbed parts of a sequence when recomputing an alignment. We also discuss techniques to reduce the memory requirements of the algorithm by focusing on the highly conserved segments of the sequence. Experimental results establish that our proposed alignment procedure can update alignment decisions of modified sequence with 4.6% to 18% of the number of computations required by the normal Needleman-Wunsch algorithm, depending on sequence length. Higher computational savings are achieved with longer sequences