Traceback Memory Reduction for Three-Sequence Alignment Algorithm with Affine Gap Models
Journal
Proceedings of 2022 Asia-Pacific Signal and Information Processing Association Annual Summit and Conference, APSIPA ASC 2022
ISBN
9786165904773
Date Issued
2022-01-01
Author(s)
Abstract
In many hardware aligners, on-chip traceback is not supported because it requires large memory usage. The issue becomes even worse for three-sequence alignment, which is an algorithm to improve the accuracy of multiple sequence alignment. In this paper, we propose a design to reduce the usage of traceback memory for three-sequence alignment with affine gap penalty models. Using the pre-computed results from the forward dynamic programming stage, we are able to encode traceback directions with fewer bits. Our algorithm could save 37.5% memory usage when compared to direct implementations. The proposed bit-reduction method can be further combined with existing region-reduction traceback methods to lower required memory sizes.
Type
conference paper