Loading...
Loading...

Go to the content (press return)

Formalization of block pruning: reducing the number of cells computed in exact biological sequence comparison algorithms

Author
De Sandes, E.; Teodoro, G.; Walter, M. E.; Martorell, X.; Ayguade, E.; Melo, A.
Type of activity
Journal article
Journal
Computer journal
Date of publication
2018-05-01
Volume
61
Number
5
First page
687
Last page
713
DOI
https://doi.org/10.1093/comjnl/bxx090 Open in new window
Repository
http://hdl.handle.net/2117/120445 Open in new window
URL
https://academic.oup.com/comjnl/article-abstract/61/5/687/4539903 Open in new window
Abstract
Biological sequence comparison algorithms that compute the optimal local and global alignments calculate a dynamic programming (DP) matrix with quadratic time complexity. The DP matrix H is calculated with a recurrence relation in which the value of each cell Hi,j is the result of a maximum operation on the cells’ values Hi-1,j-1, Hi-1,j and Hi,j-1 added or subtracted by a constant value. Therefore, it can be noticed that the difference between the value of cell Hi,j being calculated and the v...
Citation
De Sandes, E., Teodoro, G., Walter, M. E., Martorell, X., Ayguade, E., Melo, A. Formalization of block pruning: reducing the number of cells computed in exact biological sequence comparison algorithms. "Computer journal", 1 Maig 2018, vol. 61, núm. 5, p. 687-713.
Keywords
Biological sequence comparison algorithms, Dynamic progamming
Group of research
CAP - High Performace Computing Group

Participants

Attachments