AAAligner: Anchor-based Approach to Fast Genome Sequence Alignment

Sequence alignment has become the gold standard in vast areas of genome sequence analysis with the aim of finding variations in these sequences. These variations may well be associated with traits or diseases. The dynamic programming approach, although innovative, is not efficient for long sequences and tremendous effort toward its improvement to make it faster and memory efficient has been pursued in various directions. The first one is parallelization for multicores, multiprocessors, and distributed systems. The second direction is utilization of General Purpose Graphic Processing Units (GPGPUs) by making alignment algorithms GPGPU-enable. The third approach aims at reducing both time and space complexities by breaking down a long pair of sequences into many short pairs and aligning each short pair separately. The last approach is inherently more efficient, assuming that the breaking method is effective, and at the same time the alignment of all pairs could potentially be done in parallel. In this paper, the Anchor-based Approach Aligner (AAAligner) is introduced which recursively breaks the two sequences along their Longest Common Subsequences (LCS) until each pair of sequences to be aligned are short enough. AAAligner is organized as a Divide and Conquer (DaC) approach and its time and space complexities shown to be very effective in reducing the overall execution time as well as space requirement compared to state of the art methods.