An Algorithm for the Sequence Alignment with Gap Penalty Problem using Multiway Divide-and-Conquer and Matrix Transposition

We present a cache-efficient parallel algorithm for the sequence alignment with gap penalty problem for shared-memory machines using multiway divide-and-conquer and not-in-place matrix transposition. Our r−way divide-and-conquer algorithm, for a fixed natural number r≥2, performs Θ(n³) work, achieves Θ(n^{log_r⁡(2r−1)}) span, and incurs O(n³/(BM)+(n²/B)log⁡M) serial cache misses for n>γM, and incurs O((n²/B)log⁡(n/M)) serial cache misses for αM<n≤γM, where, M is the cache size, B is the cache line size, and α and γ are constants.