A One-Phase Parallel Algorithm for the Sequence Alignment Problem
Thierry Lecroq, Jean‐Frédéric Myoupo, David Semé · Parallel Processing Letters · 1998
This paper introduces a new linear systolic algorithm [10] for the sequence alignment problem [18]. It is made up of min(n, m) processors and computes the edit distance and the sequence alignment of two sequences Target and Source in time min(n, m) + 2.max(n, m), where n and m denote the lengths of Target and Source respectively. Its characteristics make it faster and more efficient than the previous linear array algorithm for the alignment search.