Parallel Implementations of Local Sequence Alignment: Hardware and Software - Parallel Computing for Bioinformatics and Computational Biology - page 256

than 10 times is obtained for the MA of 600 GPCR proteins using 16 CPUs when
compared with the one which was run on a single processor. Total time to solution is
reduced from 1 h, 7 min (single processor) to just over 6.5 min (on 16 CPUs of the
SGI Origin 3000 series), and hence significantly increasing research productivity.
10.7.2.3 HT ClustalW Optimization The need to calculate large numbers of
multiple alignments of various sizes has become increasingly important in high-
throughput (HT) research environments. To address this need, SGI has developed
HT Clustal, basically, a wrapper program that launches multiple ClustalW jobs on
multiple processors, where each ClustalW job is usually executed independently on a
single processor. To reproduce this high throughput environment, the following mix
of heterogeneous MAs is constructed.
HT Clustal is used to calculate 100 different MAs for GPCR proteins (average
length 390 amino acids). Each input file contains between 10 and 100 sequences
taken randomly from a pool of 1000 GPCR sequences. The number of sequences
conforms to a Gaussian distribution with the average of 60 sequences and standard
deviation of 20.
To optimize the throughput performance, the input sequences are presorted based
on a relative file size. The purpose of the presorting is to minimize load unbalance
and hence improve the scaling of HT Clustal. Experimental studies have shown that
the improvement from presorting becomes significant when the average number of
jobs per CPU is on the order of five. When the average number of jobs per CPU is
greater than five, it shows that the statistical averaging reduces the load unbalance
and there is only minor improvement with presorting.
With presorting, it is possible to achieve almost linear speedups. For the earlier
example, the speedups of 31 times were achieved on 32 CPUs. For the larger test
cases, speedup of 116 times was found on a 128-CPU SGI Origin 3000 series server,
and hence reducing total time to solution from over 18.5 h to just less than 9.5 min.
Because individual ClustalW jobs are processed on a single processor, HT Clustal
can be used efficiently on both single system image SGI Origin 3000 series servers
and distributed Linux clusters.
10.7.2.4 MULTICLUSTAL Optimization The MULTICLUSTAL algorithm
was introduced as an optimization of the ClustalW MA [31]. The MULTICLUSTAL
alignment gives a domain structure, which is more consistent with the 3D structures
of proteins involved in this alignment.
The algorithm searches for the best combination of ClustalW input parameters
to produce more meaningful multiple sequence alignments (i.e., smaller number of
gaps with more clustering). It does so by performing ClustalW calculations for various
scoring matrices and gap penalties in the PW / GT and PA stages.
SGI has optimized the original MULTICLUSTAL algorithm by reusing the tree
calculated in the PW / GT steps. Therefore, the guide tree is calculated only once for
a given combination of PW parameters and is then used for all possible combinations
of PA parameters. The performance (relative to that of original MULTICLUSTAL