Fast Sequence Similarity Computing with LCS on LARPBS

摘要

The problem of the longest common subsequence (LCS) is a fundamental problem in sequence alignment. In this paper, we first present fast parallel algorithms for sequence similarity with LCS. For two sequences of lengths m and n (m ≤ n), the algorithm uses n processors and costs O(m) computation time. Time-area cost of the algorithm is O(m n) which reaches optimality. Based on this algorithm, we also give a fast parallel algorithm which can compute the length of LCS in O(log m) time. To our best knowledge, this is the fastest one among the parallel LCS algorithms on array architectures.