| Paper: | BIO-P2.6 | ||
| Session: | Bioinformatics | ||
| Time: | Wednesday, May 17, 16:30 - 18:30 | ||
| Presentation: | Poster | ||
| Topic: | Bio Imaging and Signal Processing: Computational biology and biological networks | ||
| Title: | Handling Updates of Pairwise Sequence Alignment | ||
| Authors: | Changjin Hong, Ahmed Tewfik, University of Minnesota, United States | ||
| Abstract: | 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. | ||
©2018 Conference Management Services, Inc. -||- email: webmaster@icassp2006.org -||- Last updated Friday, August 17, 2012