Abstract
Samba is a full custom parallel hardware accelerator dedicated to the comparison of biological sequences. It implements a parameterized version of the Smith and Waterman algorithm allowing the computation of local or global alignments with or without gap penalty. The speed-up provided by Samba over standard workstations ranges from 50 to 500, depending on the application. Samba was designed with an effort of less than one person/year. This includes the design, fabrication and test of a full-custom Vlsi chip which is used as a building block for the 128 processor systolic array implementing the string alignment algorithm. We describe the Samba architecture, its performance characteristics, and we detail its design steps, from the initial specification to its full implementation. We report a first application of Samba to the study of yeast orphan sequences.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
S.F. Altschul, W. Gish, W. Miller, E.W. Myers, and D.J. Lipman.-Basic local alignment search tool.-J. Mol. Biol, 215:403–410, 1990.
P. Bertin, D. Roncin, and J. Vuillemin.-Programmable active memories: a performance assessment.-In F. Meyer, B. Monien, and A.L. Rosenberg, editors, Parallel Architectures and their efficient use, pages 119–130. LNCS, Springer-Verlag, oct 1992.
E. Chow, T. Hunkapiller, and J. Peterson.-Biological Information Signal Processor.-In ASAP, pages 144–160, sep 1991.
Compugen.-The bioccelerator machine.-Israel, 1993.
O. Gotoh.-An Improved Algorithm for Matching Biological Sequences.-J. Mol. Biol., 162:705–708, 1982.
P. Guerdoux-Jamet and D. Lavenier.-Systolic filter for fast DNA similarity search.-In ASAP'95, Strasbourg, July 1995.
P. Guerdoux-Jamet and J.L. Risler.-Searching for a family to orphan sequences with SAMBA, a parallel hardware dedicated to biological applications.-Biochemistry, 1996.
D. Lavenier.-An Integrated 2D Systolic Array for Spelling Correction.-Integration: the VLSI journal, 15:97–111, August 1993.
D. Lavenier.-Samba. Systolic Accelerators for Molecular Biological Applications.-Internal Publication 988, IRISA, Irisa, Campus de Beaulieu, 35042, Rennes-Cedex, France, April 1996.
D. Lopresty and al.-Building and using a highly parallel programmable logic array.-Computers, pages 81–89, jan 1991.
S.B. Needleman and C.D. Wunsh.-A General Method Applicable to the Search of Similarities in the Amino Acid Sequence of Two Proteins.-J. Mol. Biol, 48:443–453, 1970.
W. R. Pearson and D.J. Lipman.-Improved tools for biological sequence comparison.-Proc. Natl. Acad. Sci., 85:3244–3248, 1988.
W.R. Pearson.-Searching protein sequence libraries: comparison of the sensitivity and selectivity of the smith and waterman and fasta algorithms.-Genomics, 11:635–650, 1991.
F. Raimbault and D. Lavenier.-ReLaCS for Systolic Programming.-In ASAP'93, October 1993.
T.F. Smith and M.S. Waterman.-Identification of common molecular subsequences.-J. Mol. Biol, 147:195–197, 1981.
S.S. Sturrock and J.F. Collins.-Mpsearch version 1.3.-Technical report, University of Edinburgh, Biocomputing Research Unit, 1993.
M.S. Waterman.-Mathematical Methods for DNA Sequences.-CRC Press, Inc, 1989.
C.T. White, R.K. Singh, P.B. Reintjes, J. Lampe, B.W. Erickson, W.D. Dettloff, V.L. Chi, and S.F. Altschul.-BioSCAN: A VLSI-Based System for Biosequence Analysis.-In IEEE Int. Conf on Computer Design: VSLI in Computer and Processors, pages 504–509. IEEE Computer Society Press, oct 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guerdoux-Jamet, P., Lavenier, D., Wagner, C., Quinton, P. (1996). Design and implementation of a parallel architecture for biological sequence comparison. In: Bougé, L., Fraigniaud, P., Mignotte, A., Robert, Y. (eds) Euro-Par'96 Parallel Processing. Euro-Par 1996. Lecture Notes in Computer Science, vol 1123. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61626-8_2
Download citation
DOI: https://doi.org/10.1007/3-540-61626-8_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61626-9
Online ISBN: 978-3-540-70633-5
eBook Packages: Springer Book Archive