Furthermore, we have developed an effective heuristic search, restricted
partitioning technique. Applying the iterative strategy, we realized that the
number of sequences in the divided groups is important. As partitioning
divides N sequences into k sequences and N-k sequences, a smaller k tends to
provide a larger improvement when using two-dimensional DP. The restricted
partitioning technique preferentially selects partitionings which have a small
k such as one or two. It can restrict the search space and reduce the execution
time remarkably. Parallel iterative aligners with this technique can manage
more sequences at the same time than those without it.
Demonstration
The demonstration system solves an alignment of 22 sequences using the
parallel iterative aligner. It is executed on PIM/m, which consists of 256
processing elements (PEs).
We use the restricted partitioning technique; the number of sequences in
the smaller divided group is restricted to one or two. 253 PEs (22C1 = 22 plus
22C2 = 231) are necessary to execute all restricted partitioning in parallel.
Additionally, one processor is used for a manager process which selects the
best alignment in every iteration. In total, 254 PEs are employed in this
demonstration.
The demonstration shows gradual improvement of the alignment in each
iteration. Code letters for amino acids in the display are colored according to
their properties (see next page). The score for each column using a bar graph
under the alignment is also shown. High-score columns, indicated by tall
bars, correspond to well-conserved sites in evolution. Representative sequence
patterns in the sites are regarded as motifs. In the final resultant data of this
demonstration, we can recognize a number of motifs. One of them is a famous
motif, the site of which binds ATP.
- 61 -
