A New Parallel Method Based On Balanced Division For Sequence Alignment

Pairwise sequence alignment is one of common methods in analyzing sequence, which also is the base of multiple sequence alignment and data search. So to now, many methods on solving pairwise sequence alignment are available, thereinto, the dynamic programming is the most basic, effective method. But it is large in time and space complexity, it is restricted in practical. So the key problem to be solved is to reduce the time and space complexity when maintain accuracy to sequence alignment.There are many pairwise sequence alignment algorithms. The fast known parallel space-optimal algorithm for pairwise sequence alignment takes optimal space O (( m+ n)/p), but O (( m+n)2 /p) time. The most space saving time-optimal algorithm takes O ( mn/p) time, but O ( m+ n/p) space.In the article, we present an algorithm that requires O( mn/p) time and O (( m+n)/p) space. The new sequence alignment method based on balanced dividing and parallel. It reduces time and space complexity by introducing data dividing technique, using High Performance computer system such as group system.