| We introduce a novel parallel algorithm for optimal pairwise sequence alignment, called Parallel FastLSA. Parallel FastLSA is the parallel version of an existing algorithm, FastLSA, whose name is an abbreviation for Fast Linear Space Alignment. FastLSA finds an optimal alignment for two biological sequences using linear space, and it is proven to be empirically faster than two other frequently used alignment algorithms: Needleman-Wunsch and Hirschberg. Parallel FastLSA is designed to further improve the time performance of FastLSA, while still using only linear space.; We describe in detail the Parallel FastLSA algorithm and how the algorithm is implemented. We also analyze the effectiveness of Parallel FastLSA and give detailed accounts of its theoretical and empirical performance. Our experimental results show that Parallel FastLSA exhibits good speedups, almost linear for 8 processors or less, and also that the efficiency of Parallel FastLSA increases with the size of the sequences that are aligned. |
