Traceback Memory Reduction for Three-Sequence Alignment Algorithm with Affine Gap Models

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 tra...

Full description

Saved in:
Bibliographic Details
Main Authors: Chien, Ruei-Ting, Lin, Mao-Jan, Yeh, Yang-Ming, Lu, Yi-Chang
Format: Conference Proceeding
Language:English
Subjects:
Dynamic programming
Hardware
Heuristic algorithms
Information processing
Memory management
System-on-chip
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2640-0103
DOI:10.23919/APSIPAASC55919.2022.9980113