ABSTRACT:

Finding the longest common subsequence (LCS) of multiple strings is an NP-hard drawback, with many applications within the areas of bioinformatics and computational genomics. Although significant efforts are made to handle the matter and its special cases, the increasing complexity and size of biological data need additional efficient strategies applicable to an arbitrary number of strings. In this paper, we tend to gift a new algorithm for the final case of multiple LCS (or MLCS) drawback, i.e., finding an LCS of any number of strings, and its parallel realization. The algorithm is based on the dominant purpose approach and employs a fast divide-and-conquer technique to compute the dominant points. When applied to a case of 3 strings, our algorithm demonstrates the identical performance as the fastest existing MLCS algorithm designed for that specific case. When applied to a lot of than 3 strings, our algorithm is significantly faster than the most effective existing sequential strategies, reaching up to two-3 orders of magnitude faster speed on massive-size issues. Finally, we have a tendency to present an efficient parallel implementation of the algorithm. Evaluating the parallel algorithm on a benchmark set of each random and biological sequences reveals a close to-linear speedup with respect to the sequential algorithm.