A Parallel Computing Approach to Genetic Sequence Comparison: The Master-Worker Paradigm

摘要

We have implemented a parallel computer version of a dynamic programming biological sequence comparison algorithm to study the potential applicability of using parallel computers for genetic sequence comparisons. Our parallel program is built using C-Linda ®, a machine-independent parallel programming language, and currently runs on a Sequent Symmetry ® parallel computer. C-Linda implements a shared associative memory model, “tuple space”, through which multiple processes can communicate and coordinate control. In our master-worker (MW) parallel implementation, a master process creates several worker processes, extracts a target sequence and multiple test sequences from a database and stores them in tuple space. Each worker reads the target and then repeatedly extracts test strings from tuple space, performs pairwise sequence comparisons using a local comparison algorithm to generate a similarity score, and returns the similarity scores to tuple space. The master collects the scores from tuple space and identifies the best match over all test sequences. The entire program is constructed so that alternative sequence comparison algorithms can be substituted quite easily. Comparisons of the total run-time, speedup, and efficiency were made for the MW parallel implementation and a sequential version.