Research On Linear Space Algorithms For Pairwise Sequence Alignment

Sequence alignment is a basic information disposal problem in bioinformatics. It isuseful for discovering functional, structural, and evolutionary information in DNA andprotein sequences. With the rapid increase of sequence data in biology sequencedatabase, it is very exigent to design efficient parallelization algorithms to deal withlarge-scale computation. Pairwise alignment algorithms of bioinformatics andcorresponding parallelization algorithms are studied in this paper. The main work andcontributions can be briefly summarized as follows:1. To improve the processing performance, shared address space platforms are usedto parallel the Hirschberg algorithm. Compared with Hirschberg algorithm, it furtherimproves the time performance, while using only linear space.2. In order to improve the performance of FA algorithm, we design non-recursivealgorithm based on recursive FA algorithm. The time performance is also improved withlinear-space requirement.And then, experiments and analysis for the improved algorithms are presented.Experiments show that the improved algorithms are faster than the original algorithmsin biology computing efficiency. It can offer sustainment for Bioinformatics researchand practice.