Studies in the optimization of sequence alignment have been carried out in
bioinformatics. In this paper, we have focused on two aspects: memory usage and
execution time. Our study suggests that cache memory does not have a significant
effect on system performance. Our attention then turns to optimize
Smith—Waterman's algorithm. Two instruction level methods have been
proposed and 2—8 fold speed improvements have been observed after the
optimization has been implemented. Further improvements on system performance have
been achieved by overlapping computation with system I/O usage.
Alpern, B.
,
Carter, L.
, and
Gatlin, K.S.
(1995).
Microparallelism and high performance protein matching
, in Proceedings of the 1995 ACM/IEEE Supercomputing
Conference, San Diego, CA.
2.
Altschul, S.F.
,
Gish, W.
,
Miller, W.
,
Myers, E.W.
, and
Lip-man, J.
(1990).
Basic local alignment search tool
, Journal of Molecular Biology, 251:
403—410
.
3.
Bader, D.
,
Li, Y.
,
Li, T.
, and
Sachdeva, V.
(2005).
Bioperf: A benchmark suite to evaluate high-performance computer
architecture on bioinformatics
, in Proceedings of IEEE International Symposium on Workload
Characterization, Austin, TX.
4.
Barroso, L.
and
Gharachorloo, K.
(1998).
Memory system characterization of commercial workloads
, in 25th International Symposium on Computer Architecture
(ISCA'98), pp. 3—14, Barcelona, Spain.
5.
Camp, N.
,
Cofer, H.
, and
Gomperts, R.
(1998). High-throughput Blast, Technical Report,
Silicon Graphics Inc White Paper
.
6.
Demmel, J.
,
Dongarra, J.
,
Eijkhout, V.
,
Fuentes, E.
,
Petitet, A.
,
Vuduc, R.
,
Whaley, R.C.
, and
Yelick, K.
(2005).
Self adapting linear algebra algorithms and software
, Proceedings of the IEEE, Special Issue on Program
Generation, Optimization, and Adaptation, 93(2): 293—312.
7.
Frigo, M.
and
Johnson, S.G.
(2005).
The design and implementation of FFTW3
, Proceedings of the IEEE, Special Issue on Program
Generation, Optimization, and Adaptation, 93(2): 216—231.
8.
Galison, F.
(2001). The Fasta and Blast programs, http://bioweb.pasteur.fr/seqanal/blast/.
9.
Gusfield, D.
(2001). Algorithms on strings, trees, and sequences: Computer
science and computational biology,
Cambridge University Press, Cambridge
, UK.
10.
Hennessy, J.L.
and
Patterson, D.A.
(1999). Computer architecture: A quantitative approach
, 2nd edn,
San Francisco: Morgan Kaufmann
.
11.
Im, E.J.
,
Yelick, K.
, and
Vuduc, R.
(2004).
Sparsity: Optimization framework for sparse matrix kernels
, International Journal of High Performance Computing
Applications, 18(1):
135—158
.
12.
Lee, D.
,
Crowley, P.
,
Baer, J.
,
Anderson, T.
, and
Bershad, B.
(1998). Execution characteristics of desktop applications on
Windows NT, in 25th Annual International Symposium on Computer
Architecture (ISCA'98), pp. 27—38,
Barcelona
, Spain.
13.
Mirkovie, D.
and
Johnsson, S.L.
(2001).
Automatic performance tuning for the UHFFT library
, in Proceedings of International Conference on Computational
Science, Lecture Notes in Computer Science, vol. 2073, pp.
71—80, Berlin: Springer.
14.
Puschel, M.
,
Moura, J.M.F.
,
Johnson, J.
,
Padua, D.
,
Veloso, M.
,
Singer, B.
,
Xiong, J.
,
Franchetti, F.
,
Gacic, A.
,
Voronenko, Y.
,
Chen, K.
,
Johnson, R.W.
, and
Rizzolo, N.
(2005).
Spiral: Code generation for DSP transforms
, in Proceedings of the IEEE, Special Issue on Program Generation,
Optimization, and Adaptation, 93(2): 232—275.
15.
Rognes, T.
and
Seeberg, E.
(2000).
Six-fold speed-up of Smith— Waterman sequence database searches
using parallel processing on common microprocessors
, Bioinformatics, 16(8):
699—706
.
16.
Smith, T.
and
Waterman, M.
(1981).
Identification of common molecular subsequences, Journal of MolecularBiology, 147(1):
195—197
.
17.
Thompson, J.D.
,
Higgins, D.G.
, and
Gibson, T.J.
(1994).
Clustal w: improving the sensitivity of progressive multiple sequence
alignment through sequence weighting, positions-specific gap penalties and
weight matrix choice
, Nucleic Acids Research , 22:
4673—4680
.
18.
Wozniak, A.
(1996).
Using video-oriented instructions to speed up sequence comparison
, Bioinformatics, 13(2):
145—150
.
19.
Xu, Z.
,
Sohum, S.
,
Min, R.
, and
Hu, Y.
(2004).
An analysis of cache performance of multimedia applications
, IEEE Transactions on Computers, 53(1):
23—38
.
20.
Zhang, Z.
,
Schwartz, S.
,
Wagner, L.
, and
Miller, W.
(2000).
A greedy algorithm for aligning DNA sequence, Journal of ComputationalBiology, 7(12):
203—214
.
