Research On Algorithm Of Comparing Bio-sequences Similarity

Bioinformatics is a new discipline between biology and computer science, it utilizes computersto handle and research the data of biology. In bioinformatics, comparing the similarity of biologicalsequences is the most foundation problem. The research of sequences similarity comparingalgorithm play an important role in bioinformatics.After discussing the earliest sequences similarity comparing algorithm—two sequencesglobal similarity comparing algorithm based on dynamic programming and the evolution model ofbiological sequences, the paper deduces the coherence between computing of evolutive relation andsimilarity of two biological sequences. Also the paper give an introduction of all kind algorithms inthis field.Then the paper discusses some issue in the optimization of dynamic programmingalgorithm. In practical application, the spacial complexity of algorithm is the bottleneck ofproblem's scale. The paper introduce a new algorithm—"Fast Alignment(FA)". The spacial andtemporal complexity of this algorithm are between basic dynamic programming algorithm andhirschberg algorithm. By adjusting the argument K of FA, we can get the most time-savingexecution of FA under any memory constrain. At the same time, the paper researches theparallelable of dynamic program, and discusses two kinds of parallel algorithm on SMP computer.After that, the paper give a parallel algorithm on cluster of SMP computers, and discuss how todivide the data getting more effective execution of parallel algorithm.Dynamic programming algorithm have a non-crossed properity, but comparing the sequenceswhich have rearranged and reversal subsequence need the algorithm which have crossed properity.The paper introduces a new algorithm which have crossed properity. Comparing with basic dynamicprogramming algorithm, this algorithm have many merits. The paper also gives a parallel method ofthis algorithm.Finally, the paper discusses two programs correlative with sequences similarity comparingalgorithm—PHRAP and BLAST. The PHRAP program assemble many subsequences in DNAsequencing to a long DNA sequence by their overlap. The BLAST program searches similaritysequences of a query sequence at biological sequences database. The paper gives their parallelmethod and implementation of them.