A new, space-efficient local pairwise alignment methodology

Aligning large nucleotide sequences requires significant portion of the memory, what in some cases is found as a limiting factor. Local pairwise alignment methods require O(m) space, most of them being dynamic programming-based. In this paper we present a new, space-efficient methodology and an algorithm for optimal un-gapped local pairwise alignment, using non dynamic programming-based approach. A highest scoring un-gapped local alignment is found, identifying and combining exact nucleotide matching regions, shifting one of the sequences over the other. The number of shifts is score-dependent, what is a time complexity advantage. An implementation of the proposed methodology was tested on EMBL-EBI viroid genomes, always identifying an optimal un-gapped local alignment, requiring on average m/2 space