TALCO is a novel method for Tiling genome sequence ALignment using COnvergence of traceback pointers, that, similar to prior tiling techniques, maintains a constant memory footprint during the acceleration step independent of alignment length. However, unlike previous techniques, TALCO also ensures optimal alignments under banding constraints. TALCO does this by leveraging the convergence of traceback paths beyond a tile to a single point on the boundary of that tile – a strategy that seems to generalize well to a broad set of sequence alignment algorithms. To demonstrate generalizability, we apply TALCO to widely-used banded sequence alignment algorithms, X-Drop and WFA-Adapt. We call the modified algorithms TALCO-XDrop and TALCO-WFAA, respectively.
This repository contains CPU and ASIC implementations of TALCO-XDrop and TALCO-WFAA.
.
└── 1. dataset
└── 2. hardware # ASIC implementations
└── TALCO-XDrop
└── TALCO-WFAA
└── scripts
└── baselines
└── 3. software # CPU implementations
└── TALCO-XDrop
└── TALCO-WFAA
└── scripts
└── baselines
If you use TALCO in your work, please cite the following paper:
- Sumit Walia, Cheng Ye, Arkid Bera, Dhruvi Lodhavia, Yatish Turakhia, "TALCO: Tiling Genome Sequence Alignment using Convergence of Traceback Pointers", In 2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA), [Paper][Video].
We appreciate any feedback and suggestions. Feel free to raise an issue or submit a pull request on GitHub or contact Sumit Walia (swalia AT ucsd DOT edu).