A Parallel Implementation for Finding the Longest Common Subsequence

摘要

Searching for the Longest Common Subsequence (LCS for short) is one of the most fundamental tasks in bioinformatics. In this paper, we present a parallel implementation of the LCS computation for heterogeneous master-worker platforms. It is the first parallel implementation on cluster environment for this problem. We also report a set of numerical experiments on a heterogeneous platform where computational resources have different computing powers. Also, the workers are connected to the master by communication links of same capacities. The obtained experimental results demonstrate the proposed parallel implementation is efficient with low communication overhead.