Bio-sequence analysis with cradle's 3SoC™ software scalable system on chip

ABSTRACT

With the dramatically increasing amounts of genomic sequence database, there is a need for faster and more sensitive searching for sequence similarity analysis. The Smith-Waterman algorithm, which utilizes dynamic programming, is a common method for performing exact local alignments between two protein or DNA sequences. The Smith-Waterman algorithm is exhaustive and generally considered to be the most sensitive, but long computation times limit the use of this algorithm. This paper presents a preliminary implementation of Smith-Waterman algorithm using a new chip multiprocessor architecture with multiple Digital Signal Processors (DSP) on a single chip leading to high performance at low cost.

REFERENCES

• 1: Altschul, S.F., Gish, W., Miller, W., Myers, E.W. and Lipman, D.J. Basic local alignment search tool. J. Mol. Biol.215, (1990), 403--410
• 2: R. D. Bjornson , A. H. Sherman , S. B. Weston , N. Willard , J. Wing, TurboBLAST(r): A Parallel Implementation of BLAST Built on the TurboHub, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.325, April 15-19, 2002
• 3: Jennifer Eyre , Jeff Bier, DSP Processors Hit the Mainstream, Computer, v.31 n.8, p.51-59, August 1998 [doi>10.1109/2.707617]
• 4: Gotoh, O. An improved algorithm for matching biological sequences J. Mol.Biol.(1982) 162, 705--708
• 5: Grate, L., Diekhan, M., Dahle, D. and Hughey, H. Sequence Analysis With the Kestrel SIMD parallel Processor. Pacific Symposium on Biocomputing 2001 pp.263--74
• 6: Hughey, R. Parallel hardware for sequence comparison and alignment. (1996) Comput. Appl. Biosci. 12, 473--479
• 7: Lau, F. An Integrated Approach to Fast, Sensitive, and Cost-Effective Smith-Waterman Multiple Sequence Alignment. Bioinformatics Module, (2000) MB&B 452
• 8: Needleman, S. and Wunsch, C. A general method applicable to the search for similarities in the amino acid sequence of two sequences. . J. Mol. Biol., 48(3), (1970), 443--453
• 9: Rogens, T. and Seeberg. E. Six-fold speed-up of Smith-Waterman sequence database searches using parallel processing on common microprocessors. Bioinformatics, 16, (2000), 699--706.
• 10: Bertil Schmidt , Heiko Schröder , Manfred Schimmler, Massively Parallel Solutions for Molecular Sequence Analysis, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.201, April 15-19, 2002
• 11: Smith, T.F. and Waterman, M.S. Identification of common molecular subsequences. J. Mol. Biol., 147, (1981), 195--197
• 12: Taylor, Stewart Applying MMX Technology to the Smith-Waterman Algorithm. Department of Electrical Engineering, Stanford University, <u>www.stanford.edu/~sntaylor/mis299/report.htm</u>
• 13: Yamagucchi Y., Maruyama, T. High Speed Homology Search with FPGA. Pacific Symposium on Biocomputing 2002
• 14: 3SoC Documentation--3SoC 2003 Hardware Architecture, Cradle Technologies, Inc. Mar 2002.
• 15: 3SoC Programmer's Guide, Cradle Technologies, Inc., http://www.cradle.com, Mar 2002.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES

General Terms:
Design, Performance

Keywords:
3SoC chip, Digital Signal Processors, Smith-Waterman algorithm