Dynamic Gap Selector: A Smith Waterman Sequence Alignment Algorithm with Affine Gap Model Optimisation

Abstract: Smith Waterman algorithm (S-W) is nowadays considered one of the best method to perform local alignments of biological sequences characterizing proteins, DNA and RNA molecules. Indeed, S-W is able to ensure better accuracy levels with respect to the heuristic alignment algorithms by extensively exploring all the possible alignment configurations between the sequences under examination. It has been proven that the first amino acid (AA) or nucleotide (NT) inserted/deleted (that identify a gap open) found during the alignment operations performed on sequences is more significant from a biological point of view than the subsequent ones (called gap extension), making the so called Affine Gap model a viable solution for biomolecules alignment. However, this version of S-W algorithm is expensive both in terms of computation as well as in terms of memory requirements with respect to others less demanding solutions such as the ones using a Linear Gap model. In order to overcome these drawbacks we have developed an optimised version of the S-Walgorithm based on Affine Gap model called Dynamic Gap Selector (DGS S-W). Differently from the standard S-W Affine Gap method, the proposed DGS S-W method reduces the memory requirements from 3*N*M to N*M where N and M represents the size of the compared sequences. In terms of computational costs, the proposed algorithm reduces by a factor of 2 the number of operations required by the standard Affine Gap model. DGS S-W method has been tested on two protein and one RNA sequences datasets, showing mapping scores very similar to those reached thanks to the classical S-W Affine Gap method and, at the same time, reduced computational costs and memory usage.

 not available