Research On Parallel FastLSA Algorithm For Sequence Alignment Based On PC Clustering System

Sequence alignment is a fundamental problem in bioinformatics.There are three existing algorithms :Needleman-Wunsch Algorithm,Hirschberg Algorithm and FastLSA Algorithm(abbreviation for Fast Linear Space Alignment),which are widely used for biology sequence alignment, nevetheless, it is proven that FastLSA algorithm is the most ffective one.In this paper, we use a simple but effective form of wavefront parallelism to parallelized FastLSA algorithm,which we called Parallel FastLSA. Compared with FastLSA algorithm, it further improves the time performance,while still use only linear space.The thesis describes in detail the experimental software and hardware environment of the Parallel FastLSA algorithm:building of Personal Computer Parallel Clustering System based on Linux operation System and software Distributed shared memory System. We also analyze the efficiency of Parallel FastLSA and give detailed accounts of its theoretical and practical performance. Our experimental results show that Parallel FastLSA exhibits good speedups, and also that the efficiency of Parallel FastLSA increases with the length of the sequences that are aligned.