[Biodevelopers] The SIMD-Smith-Waterman patent? (fwd)

[Heikki Hyyro]

There was some discussion here about Cencel's patent for parallelizing the
Smith-Waterman algorithm. I sent the comment below to Cencel as also I
became curious about the matter. I wonder how they react.


---------- Forwarded message ----------
Date: Wed, 18 Feb 2004 12:09:13 +0200 (EET)
From: Heikki Hyyro <helmu at cs.uta.fi>
To: sencel at sencel.com
Subject: The SIMD-Smith-Waterman patent?

Dear recipient,

I would like to know about the patent of the SIMD Smith-Waterman patent. I
am mainly interested in what are the parts of it that you would be ready
to defend.

The patent application I have seen contains the following (I numbered the
different claims):

The main features of the implementation according to the invention, are:
1. Vectors parallel to the query sequence
2. Vector generalisation of the SWAT-optimisations
3. 8-way parallel processing with 8-bit values
4. Query sequence profiles
5. Unsigned arithmetics
6. Saturated arithmetics
7. General code optimisations

As far as I see, the situations is as follows:

As MMX and other such techniques are especially designed for speeding up
this type of computations where several data-items are handled with
instructions of the same type, and MMX etc. are third-party techniques,
the claim cannot arise from simply using MMX etc; that is not yet an
invention. The above claims 2, 3 and 6 are quite direct uses of MMX, which
do not fulfill the criterion of not being obvious.

The column-wise tiling order is a well-established technique in the field
of bit-parallel algorithms for string matching, and those algorithms also
encode the match-information of the pattern (a quite direct correspondence
to what you call "query sequence profiles"). This type of work is for
example a bit-vector algorithm by Gene Myers, published in Journal of ACM
in 1999. Thus claims 1 and 4 are, in fact, not very new innovations...

The use of unsigned arithmetics amounts only to a coding trick, that is
obvious (and surely not new).

And finally, general optimizations, as described in the application, seemd
like well-known wayt to optimize code. So nothing very innovative here,
either.

So the question is: what parts of the patent would you defend? To me it
seems to stand on a quite shaky ground, at best.

Best regards,
Heikki Hyyrö, PhD
Researcher (specializing in bit-parallel algorithms)
University of Tampere, Finland