USING VIDEO-ORIENTED INSTRUCTIONS TO SPEED-UP SEQUENCE COMPARISON

Motivation: This document presents an implementation of the well-known Smith-Waterman algorithm for comparison of proteic and nucleic sequen ces, using specialized video instructions. These instructions, SIMD-li ke in their design, make possible parallelization of the algorithm at the instruction level. Results: Benchmarks on an ULTRA SPARC running a t 167 MHz show a speed-up factor of Two compared to the same algorithm implemented with integer instructions on the same machine. Performanc e reaches over 18 million matrix cells per second on a single processo r, giving to our knowledge the fastest implementation of the Smith-Wat erman algorithm on a workstation. The accelerated procedure was introd uced in LASSAP-a LArge Scale Sequence compArison Package software deve loped at INRIA-which handles parallelism at higher level. On a SUN Ent erprise 6000 sewer with 12 processors, a speed of neatly 200 million m atrix cells per second has been obtained. A sequence of length 300 ami no acids is scanned against SWISSPROT R33 (18 531 385 residues) in 29 s. This procedure is not restricted to databank scanning. It applies t o all cases handled by LASSAP (intra- and inter-bank comparisons, Z-sc ore computation, etc.).