Parallel characteristics of sequence alignment algorithms

Parallel algorithms for analyzing DNA and protein sequences are becoming increasingly important as sequence data continues to grow. This paper examines the parallel characteristics of four sequence alignment algorithms. The four algorithms presented are the dynamic programming algorithm developed by Needleman, Wunsch, and Sellers (the NWS algorithm), Fickett´s algorithm, a parallel algorithm using some of Fickett´s ideas, and an algorithm which uses some of Wilbur and Lipman´s ideas for constructing alignments which are not always optimal. The NWS algorithm contains the most parallelism but also does more work than any of the other algorithms which we studied. Fickett´s algorithm contains the least parallelism. However, a parallel algorithm which requires significantly fewer instructions than the NWS algorithm is obtained by modifying Fickett´s algorithm. The algorithms have been implemented for a dataflow computer in the dataflow language Id.