Authors: Azzedine Boukerche Alba Cristina Magalhaes Alves de Melo Edans Flavius de Oliveira Sandes Mauricio AyalaRincon
Publish Date: 2007/04/05
Volume: 10, Issue: 2, Pages: 187-202
Abstract
Biological Sequence Comparison is one of the most important operations in Computational Biology since it is used to determine how similar two sequences are Smith and Waterman proposed an exact algorithm SW based on dynamic programming that is able to obtain the best local alignment between two sequences in quadratic time and spaceIn order to compare long biological sequences SW is rarely used since the computation time and the amount of memory required becomes prohibitive For this reason heuristic methods like BLAST are widely used Although faster these heuristic methods do not guarantee that the best result will be producedIn this paper we propose an exact parallel variant of the SW algorithm that obtains the best local alignments in quadratic time and reduced space The results obtained in two clusters 8machine and 16machine for DNA sequences longer than 32 KBP kilo basepairs were very close to linear and in some cases superlinear For very long DNA sequences 16 MBP we were able to reduce execution time from 1225 hours to 154 hours in our 8machine cluster As far as we know this is the first time 16 MBP sequences are compared with an exact SW variant In this case 30240 best local alignments were obtained
Keywords: