The threat of patents on crystallographic algorithms and software

Vincent Favre-Nicolin

CEA Grenoble, DRFMC/SP2M/Nano-structures et Rayonnement Synchrotron, 17 rue des Martyrs 38054 Grenoble Cedex 9, 38054 Grenoble Cedex 9, France.
E-mail:
vincefn@users.sourceforge.net – WWW: http://objcryst.sourceforge.net/

As of today crystal structures can be determined with relatively limited costs once the diffraction data has been collected: most software is available for free, and even better many programs are open-source, so that you can modify the algorithm to suit your needs.

Much more important, there is an almost absolute freedom in algorithm development. Any new or improved algorithm can be developed, published and distributed freely for using or testing, with no other demand than acknowledging the works of your peers.

This almost ideal situation (in terms of research freedom) could disappear soon due to the extension of patents to algorithms and software. The aim of this article is to present a short introduction to patents, and show how software patents have the power to shut down a large number of open-source software, and could lead to a dramatic decrease in the availability of new algorithms.

I Patents

Ia The good: encouraging publication of knowledge

A common misunderstanding is that patents exist to protect inventors from anyone stealing their discoveries without a legitimate retribution. In the days before patents, inventors (individuals or companies) had a simple way to protect their inventive craft: keeping it secret, so that no-one could copy it. And often the new technique would be lost after the death of the inventors. Patents were introduced to stop this loss of knowledge, by establishing a contract: the inventor would publish his discovery in detail, and in return all people in society would have to pay him for the right to use his inventions for a given time after his invention was made public. So the original and most important aim of patents is to encourage scientific and technological discoveries and their open distribution (protecting inventors is just a means, not a goal).

Patents are vital in today's world: the most obvious sector in which they are useful is the pharmaceutical industry: after spending 10-15 years developing a new drug, involving many different scientists, it is clearly legitimate that the corporation get the exclusive right to use or license (allowing other corporations to produce the drug) this discovery for the following 20 years, if only to pay back for the years of research. Compared to the workload required for the discovery (dozens of "man-years" of work), 20 years is relatively small. And of course, after 20 years the knowledge is public domain, so all can benefit from it.

Now what is an invention, worthy of being patented ? In the USA, it must be "new, non obvious and useful" and in Europe "new, inventive and susceptible of industrial application", both very broad definitions. In other words, there is -in practice- little or no criterion on the complexity, cleverness, and development time corresponding to the invention.

And this has led to strange situations with patents: indeed, a drug discovery is protected just as much as (to give a famous example) US Patent #6,368,227, which is a new "Method of swinging on a swing" , sideways swinging to be more technical...

Of course the above (real!) example is fun and probably harmless, even if you'd better tell your kids to use their swing only in the normal way for the next 20 years, lest a lawyer comes by and sues for patent infringement.

Ib The bad: upstream vs downstream patents

The vagueness of the patent system, leads to a increasing number of granted patents on relatively "small" or partial inventions. So instead of just granting patents on complete discoveries (directly susceptible of industrial application), patents can be deposited on "upstream" inventions, which are new but cannot be used as such.

Examples can be found (again) in the pharmaceutical industry. Instead of patenting a finalized drug, individual molecules/proteins are regularly patented (upstream patents). The trouble with the abundance of these upstream patents is that a disease with complex treatments (e.g., cancer ) require a combination of a number of these molecules, and very often it is not even be possible to do research on a combination of these molecules, because some holder of an "upstream" patent will either refuse or ask unreasonable royalties. So the excess in the patenting is not simply affecting the marketing of new drugs (as should be), but also their development, leading to a result exactly opposite to the original spirit of the patent system.

Such effects of current patent systems can be seen in various industries, where corporations are applying for many upstream patents. These can be used to gain a monopoly on a broad family of methods, but very often they are just "defensive patents", i.e. only to be used if sued by another corporation, resulting in a "cold war" of patents, where each corporation holds patents useful to others, so that none dare sue. And as it is extremely costly to apply for a patent, and much more to defend it, small companies can be easy preys for larger ones.

Ic The ugly: trivial patents and parasites

Worse than upstream patents are those that are altogether obvious and yet not screened by patent offices. This lack of screening is due to the evaluation process, which cannot be done by specialists in the field (peer review), due to the secrecy necessary with patents. Not being an expert in the field, the examiner has little chance to be aware of any "prior art" not mentioned in the application, or of its obvious nature.

Blooming on to of these trivial and often very broad patents are so-called "patent parasites", small companies who live by buying and holding trivial (and therefore upstream) patents and suing large corporations for the right to use them. As these companies only live by holding patents (and not using them), the sued corporations cannot use any of their "defensive" patents. Most companies will simply give in and pay, as winning a trial would cost them significantly more than agreeing to the licensing terms.

A good example can be found on http://youmaybenext.com/ : a company (Pangea Intellectual Properties) holds patents on trivial methods such as "using graphical and textual information on a video screen for purposes of making a sale", which applies to about every e-commerce web site.

Another example is a patent held by Forgent, which claims that a 16-year-old patent applies to jpeg compression, despite the fact that it was developed as an open standard. Companies like Sony have preferred to pay rather than engage in long and costly trials, yielding more than $20 million in revenues for Forgent.

II Software patents

IIa Background

Software has been relatively less affected by patents, mostly because the European patent convention (the Munich Convention) explicitly forbids "discoveries, scientific theories and mathematical methods" and "programs for computers". However this is rapidly changing with a strong lobbying from large corporations to legalize the use of patents in Europe as well: the European Patent Office is already granting patents on software in spite of the Munich Convention, and there is a European Directive being worked on by the European Commission. See http://swpat.ffii.org/ and links therein for more information.

IIb Patentability of software- the weight of trivial inventions

The patentability of software is largely debated for several reasons:

    • the 20-year term of patents is grossly unadapted to the computing world, patents would only add inertia.
    • most of them are seen as invalid, either because there exists "prior art" (someone else published or used the same technique before the patent application), or because it represents a "trivial" method
    • the "research" cost of software methods is vastly smaller than for industrial-grade techniques. (anyone can be inventive with a 1000 €($) computer). Most of the costs involved in software are in the writing, debugging, testing the interaction with other parts of the application/operating system, but rarely in a research of new software methods or algorithms.
    • even without worldwide patentability of software methods, the computing world has been thriving for the last 20 years, contributing substantially to the world's economical growth. What could patents improve ?
    • copyright laws (see II.c) already protect software

More fundamentally, there is no indication that software patents have encouraged technological progress in any form, which is the raison d'être of patents. The opposite effect could be dramatically true, e.g. British Telecom holds a patent which -BT claimed- covered the hyperlink (the cornerstone of the World Wide Web). Should this claim be legitimate (it has finally been outruled last summer), and have been enforced -say- ten years ago, the World Wide Web would never have developed as remarkably as it did, slowing down the technological revolution that is the widespread use of the Internet.

Another famous software patent is held by Amazon who patented the idea of "buying using a single click" on a web site, and is now suing -successfully- companies who also use this obvious idea, hindering the development of e-commerce.

So software patents are mostly effective to create a monopoly for the patent holder, locking technological development rather than encouraging it.

Of course there are a very few algorithms which require long research and careful tuning before being validated (e.g. video encoding), but these methods are still outdated far before the 20-year term of patents, and are too few to legitimate all other patents.

IIc Copyright protection

Another reason to exclude software from being patentable is that copyright laws already provide a fair protection for authors, by outlawing any unlicensed copying of the end product (the complete program).

IId Opposing patents

If most software patents are illegitimate, why not fight them before a court ? That seems like the legitimate way of solving all issues, but patent litigation costs far too much for that to be practical, especially if you intend to go against a large corporation with an experienced legal department. Even "challenging" a patent (which is done with the patent office and not before a court), requires a significant amount of money, if only to hire a specialized attorney (unless you can talk legalese). This is hardly possible for small companies or individuals, which are the ones who would need the most to be defended against abusive patents.

IIe Open-source / free software

Open-Source and Free Software have played an increasing role in the computing world since the late 1980's, and now allowing complete operating systems with a full suite of applications for the end users. Unfortunately, this kind of software is the easiest prey to software patents because:

  • it does not use software to make profit since it is available for free, and can be modified and redistributed for free as well. Therefore not only do free software companies have little money (to use for legal defense), but they are not interested in getting "defensive" patents themselves, as it is inherently against their principles.
  • many OSS/Free software developers are individuals programming on their spare time, and have neither the money nor the time to defend themselves against even the most trivial patents

In other words, if software patents are made legal worldwide, large corporations will have the power to shut down a large part of free software, by enforcing patents so trivial that they can affect a wide range of applications. It would be a striking paradox that the patent system, which was set up to ensure the spread of knowledge, could be used to annihilate the efforts of hundreds of thousands of individuals who have contributed, by their selfless efforts, to open computing knowledge.

So far there has been little or no patent litigation against OSS/Free software, companies like HP, IBM, Thomson having a policy of not prosecuting against open-source developers. But this is a purely unofficial policy, without any formal assurance that this will continue.

III Software patents and crystallography

IIa General patents

Our field is already subject to a number of patents. Some are general (upstream) patents not directly related to crystallography:

- the "Marching Cubes" algorithm is quite popular: if you have ever used a system which displays electronic density in 3D using wireframes, chances are that your software uses that algorithm and is infringing on US Patent 4,710,876 "System and Method for the Display of Surface Structures Contained Within the Interior Region of a Solid Body" and 4,885,688, "Minimization of directed points generated in three dimensional dividing cubes method".

- Of course structure determination is hungry with Fourier transforms, and although the initial FFT algorithm is not patented, there are hundreds of patents related to FFTs...

- Other "general" patents are about molecular representation, such as US Patent 5,249,137 [Xerox Corp.], whose abstract is: "A computer-aided chemical illustration system is disclosed. Techniques provided include: 1) efficient drawing of bonds; 2) drawing different bond types during a single mode; 3) determining bisect angles for bonds; 4) labeling atoms on the fly; 5) automatic alignment of atom labels; 6) custom alignment of atom labels; 7) changing the type, style, or orientation of an object while it is being drawn; 8) detection of ring structures; and 9) shifting bonds around on a ring".

- The following applies to every 3D representation where you can rotate the molecule with a mouse: US Patent #4,835,528 [Texas Instruments]: "Cursor control system". Excerpt from abstract: "A cursor control system for computer displays moves a cursor unambiguously in three dimensions using a two dimensional input device".

I'll let you guess how many structure determination packages should be thrown away due to the above.

IIb Crystallographic patents

There are also a number of patents directly applicable to our field. Just to list only a few:

- US Patent #6411676 [Nonius]: "Method for determining parameters of a unit cell of a crystal structure using diffraction". Method: uses a 2D detector, and several orientations of the crystal.

- US Patent #6,438,205 [Accelrys] "System and method for reducing phase ambiguity of crystal structure factors". related to phase distributions,...

- US Patent #6,198,796 [Rigaku]: "Method and apparatus of automatically selecting Bragg reflections, method and system of automatically determining crystallographic orientation". Uses

the two most intense Bragg reflections as a basis for orientation.

- US Patent #6,438,204 [Accelrys]: "Linear prediction of structure factors in x-ray crystallography"

- US Patent #6,345,235 [Edgecombe and Ableson]: "Method and apparatus for determining multi-dimensional structure". excerpt from the abstract: "The method is applicable to a wide range of data relating to fields such as crystallography, fluid dynamics, edge detection, and financial markets, to determine the topology of structures contained therein"

- US Patent #4,592,082 [USA]: "Quantitative determination of mineral composition by powder X-ray diffraction". Excerpt from abstract: "Ratios of the highest intensity peak of each mineral to be quantified in the sample and the highest intensity peak of a reference mineral contained in the sample are used to calculate sample composition".

- US Patent #5,353,236 [Subbiah]: "High-resolution crystallographic modeling of a macromolecule". Comprises electron density envelopes, phase determination and recycling, MIR,...

- US Patent #6,192,103 [Bede Scientific, Inc.]: "Fitting of X-ray scattering data using evolutionary algorithms"

- World Patent #WO9906824 [Shankland and David]: "Method and apparatus for determining molecular crystal structures". Includes methods: powder diffraction, description using torsion angles, reduction of data to intensities & covariance matrix, genetic algorithms...

- US Patent #20020107643 [Hendrickson and Honig]: "Process for pan-genomic determination of macromolecular atomic structures". Includes methods: genomics database, cloning, purifying, crystallization, MAD measurements, phasing, structure determination, combined analysis of structures in the same family,...

- US Patent #5,418,944 [IBM]: "Knowledge-based molecular retrieval system and method using a hierarchy of molecular structures in the knowledge base"

- US Patent #5,386,507 [Teig and Kahn]: "Computer graphics system for selectively modeling molecules and investigating the chemical and physical properties thereof". Uses an editor presenting simultaneously 2D and 3D representations.

- US Patent #4,855,931 [Saunders / Yale]: "Stochastic method for finding molecular conformations". Uses random displacements of atoms, with constraints and energy evaluation...

...

An interesting game to play after reading these patents is to list all the software you are regularly using for crystallography, and decide how many are infringing on one or several existing patents. Then, try to work without this software (assuming they would not be granted a license to use the technology)...

Of course, by studying carefully all the patents and the date at which they where deposited, you will see that all rely largely on "prior art", and on ideas that are obvious to us specialists. So you could prove most of them are actually invalid... if you have the money and the time to go to court...

IIc Crystallography be with patents – locking innovative research

As can be seen from the above list of patents, a large range of inventions can be patented: probably more than half of the articles published in Acta Cryst. A and J. Appl. Cryst could lead to patents on new crystallographic developments. The first result of enforcing these patents would be of course to restrict the distribution of all the free computer programmes which are daily used in every crystallographic laboratory.

But the issue of patents on software and algorithms goes beyond the problem of those based on prior art or trivial ideas. A lot of highly complex algorithms are used and improved regularly: direct methods, Fourier recycling and density modification, maximum likelihood... Nobody could deny the innovative (sometimes brilliant) character of these research results. But these algorithms are so vital to all modern crystallographic research that patenting them, giving a single group or corporation the right to use or license them, would considerably hinder research progress. Many complex algorithms are "fundamental theory" to the Crystallographic Community and therefore should never be patented. It would be like asking aircraft engineers to build new airplanes without using gravity laws because these are patented.

IV Conclusion and perspective on the debate at the European level

To add (certified) neutral information, it is interesting to read the report by an intellectual property expert on "The Patentability of Computer Programmes" presented at the European Parliament. Excerpts follow:

  • "It has not been demonstrated that software patents contribute to innovation. The opposite may be true as well."
  • "Proponents of the patent system all too easily assume that patents are good for SMEs [Small and Medium-sized Enterprises]. In fact, patents can have serious negative consequences for SMEs. For many software-developing SMEs software copyright protection is probably sufficient, obviating any need for patent protection."
  • "Developers of Open Source Software are relatively vulnerable to patent infringement claims, particularly in respect of trivial patents. Rooting out such patents may obviate the need for special protection of Open Source Software developers."
  • and from the conclusion: "Patents may not really be needed to stimulate investments in software development, while, on the other hand, software might be more susceptible to the potential negative effects of patents. Software development really is a matter of ideas , and it may not be appropriate to grant exclusive rights on many of those ideas, even if they are novel and not obvious. Still, there do not seem to exist compelling reasons to deny patentability to all software-related inventions in principle."

The last sentence unfortunately tells a lot about the decision process engaged in Europe. Although the report asserts that no single evidence as been brought of positive effects of software patents, the current trend would still be to allow these, because of the pressure to "harmonize" legislation with other countries (USA, Japan), and -probably more important- the intense lobbying of large US software corporations. Indeed, the latter, having been granted numerous patents other the years in the USA, would gain much to see software patents granted in Europe.

The aforementioned document nevertheless indicates that it would be necessary to rule out all inventions which are "trivial" or use "prior art" in order to eliminate the most damaging effects of software patents. The trouble is that the current practice of patent offices around the world clearly indicates that this is not possible, if only because patent reviewers cannot be all-knowing and evaluate correctly the validity of patent applications on vastly different subjects (moreover all countries would have to follow the same policy for that to be effective).

Many small points in this article can be argued upon, but it should remain clear that software patents are a threat: the delicate balance (existing in other fields) between "encouraging publication of inventions" and "locking patents" (monopolies, patent parasites) is clearly broken in the field of software development.

As researchers in a scientific field hungry with algorithms, we could doubly lose from software patents, first on the availability of free software, and second on the liberty of doing academic research on new algorithms and distributing them.

Of course, there is a fair chance that even with software patents legalized worldwide, companies involved in crystallographic software would not enforce them against open-source software and academic developers, since corporate and academic developers generally live close together. But with the increasing perception of patents as legal assets, and as decision-making about these matters falls out of the hands of scientists, this may not last. This "sitting duck" policy could prove deadly, and it would be well for the crystallographic community to voice its dissent against software patents, notably with politicians.

Further references have been collected by L. Cranswick and can be found at http://www.ccp14.ac.uk/maths/software-patents/

Searching patents databases

It is possible to search granted patents and applications using the web-based interfaces of Patent Offices. The most efficient is the US Patent Office http://www.uspto.gov/patft/ (see Fig 1 below), with 3910 granted patents and 1140 applications for a search with keyword "crystallography" through years 1976-2003. It is also possible to search European patents (although less practical) through a web interface: http://ec.espacenet.com/espacenet/

Be careful to try different terms for the search, as the language used for patents is often quite different than the one used in scientific publications (read a few patents to get an idea). And do not forget to include in your search all methods applicable, i.e. optimization algorithms, graphics displays, databases, mathematical transforms,...

[Patent Office search interface]

Fig 1: Web interface to search the US Patent Office database of granted patents via http://www.uspto.gov/patft/. Be sure to try different wording for your search, and also try a wider search to include upstream mathematical/computer methods,...