Biology Reference
In-Depth Information
Fig. 5 Runtimes in terms of different number of threads
which comprises 100 sequences and has an average length of 408,
to evaluate the parallel scalability of MSAProbs. All tests in this
evaluation are conducted in a workstation with two Intel six-core
2.67 GHz CPUs and 96 GB memory, running the Linux operating
system (Ubuntu 12.10). Figure
5
shows the runtimes (measured in
wall clock time) in terms of different number of threads. MSAProbs
achieves a speedup of about 1.9 using 2 threads, about 3.4 using
4 threads, about 6.3 using 8 threads, and about 8.9 using 12 threads.
4
Practical Issues
1. In terms of speed, the most time-consuming parts are the pair-
wise posterior probability matrix computation and the weighted
probabilistic consistency transformation. The time complexity
for the former is
O
(
N
2
L
2
) and
O
(
N
2
L
3
) for the latter, where
N
is the number of sequences and
L
is the average sequence
length. Even though we have proposed some optimizations to
improve the speed, the inherent high computational complex-
ity still results in slow speed. In this case, we recommend the
use of multiple threads on multi-core CPUs to accelerate the
execution, considering the relatively good parallel scalability of
our program.
2. In terms of memory overhead, the memory space complexity
of our program is
O
(
|X||Y|
) for sequence pair
X
and
Y
.
In addition, we must store the pairwise posterior probabilities
for each sequence pair in the dataset. Hence, for a dataset of
N
sequences and with average sequence length
L
, the memory
space complexity can be calculated as
O
(
N
2
L
2
). Fortunately,
the posterior probability matrices tend to be sparse with
most entries near zero. Hence, we can significantly reduce the
memory overhead by storing all pairwise posterior probability
matrices in sparse matrix format. However, even after using
