Sequence Alignments on a Multi-Transputer System

Abstract

This thesis is concentrated on parallelizing a sequential algorithm for finding k best non-intersecting local sequence alignments. In this thesis, the DNA local sequence alignment and the related problems are formally defined and efficient algorithms for solving these problems are presented. The problem have important applications in molecular biology. Based on the analysis of the characteristics of the local sequence alignment problem and a multi-transputer system, the problem was partitioned into subproblems and nicely mapped onto the transputer nodes. Then, an efficient parallel program is designed and implemented. By comparing the outputs of the sequential program and the parallel program, the performance of the parallel program is estimated. An average speedup of 6.3 is achieved on a 8-node configuration and an average speed-up of 11 is achieved on a 16-node configuration.