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.
Dynamic Gap Selector: A Smith Waterman Sequence Alignment Algorithm with Affine Gap Model Optimisation / Urgese, Gianvito; Paciello, Giulia; Acquaviva, Andrea; Ficarra, Elisa; Graziano, Mariagrazia; Zamboni, Maurizio. - STAMPA. - 2:(2014), pp. 1347-1358. (Intervento presentato al convegno 2nd International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO 2014) tenutosi a Granada nel April 7-9 2014).
Dynamic Gap Selector: A Smith Waterman Sequence Alignment Algorithm with Affine Gap Model Optimisation
URGESE, GIANVITO;PACIELLO, GIULIA;ACQUAVIVA, ANDREA;FICARRA, ELISA;GRAZIANO, MARIAGRAZIA;ZAMBONI, Maurizio
2014
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.File | Dimensione | Formato | |
---|---|---|---|
IWBBIO_2014_paper_143.pdf
accesso aperto
Tipologia:
2. Post-print / Author's Accepted Manuscript
Licenza:
Pubblico - Tutti i diritti riservati
Dimensione
1.66 MB
Formato
Adobe PDF
|
1.66 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2527508
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo