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. - 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

FICARRA, ELISA;
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.
2014
2nd International Work-Conference on Bioinformatics and Biomedical Engineering (IWBBIO 2014)
Granada
April 7-9 2014
2
1347
1358
Urgese, Gianvito; Paciello, Giulia; Acquaviva, Andrea; Ficarra, Elisa; Graziano, Mariagrazia; Zamboni, Maurizio
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. - 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).
File in questo prodotto:
File Dimensione Formato  
IWBBIO_2014_paper_143.pdf

Accesso riservato

Dimensione 1.66 MB
Formato Adobe PDF
1.66 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1240308
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 8
social impact