A New Dominant Point-Based Parallel Algorithm for Multiple Longest Common Subsequence Problem

Description

This work introduces a new parallel algorithm for computing a multiple longest common subsequence (MLCS). Given a set of strings, the longest common subsequence can be obtained by removing a number of symbols from each sequence. Although there was a lot of research done in the parallelization of MLCS algorithms for the special case of two sequences, so far there were no any general parallel methods for computing MLCS of an arbitrary number of sequences. Our method is a parallel approach to dominant points-based method recently proposed by Hakata and Imai. The parallel algorithm is presented and the related theoretical results as well as the algorithm’s implementation on IBM SP3 using MPI system are discussed. Keywords: longest common subsequence, dominant points, parallel algorithms, IBM SP3