Bacteria are susceptible to phage (viral) infections. One of the most important properties of phages is host specificity. Phages can be so selective that they will distinguish varieties among apparently identical organisms. By exposing au isolate growing on the surface of an agar plate to a battery of different phages a pattern develops contingent on the susceptibility or resistance of the culture to the phages. A culture sensitive to a particular phage is destroyed and the destruction is manifested by areas devoid of bacterial growth. Using phages to differentiate bacteria is referred to as phage typing.
Phage typing can be extremely important in many health situations because it can identify random, unrelated organisms as well as the isolates that are actually responsible for a given problem. Aside from relating an organism to an outbreak, this laboratory method can also be used for surveillance, assessing strain distribution, and ascertaining the effectiveness of therapeutic measures. Phage typing requires the use of a standard collection of dissimilar phages. In the process of developing a phage typing set, numerous phages are first isolated and tests are undertaken to determine if they are different and useful in delineating the types of organisms under study. To make the procedure more cost effective and less labor-intensive the final set is reduced to a manageable number with the assistance of a computer.
Selecting a smallest phage typing set is an NP-hard combinatorial search problem so no efficient algorithm for finding it is believed to exist. However, with a powerful computer very good solutions and sometimes optimal solutions can be found by intelligent searching.
Using a variety of heuristic techniques and a variety of computers small phage sets have been found previously for Salmonella, Escherichia coli, and Staphylococcus epidermidis. These programs have been rewritten to take advantage of the greater speed and address space of the IBM 3090. We are now able to obtain better results because searching can be done more exhaustively and are able to find optimal phage typing sets, something that we were not able to do with earlier programs running on less powerful computers. We are currently working on a phage typing set for Staphylococcus aoreus.
Besides finding optimal solutions we also tested a greedy algorithm. Our results suggest that the greedy algorithm works well and should enable us to solve very large problems using powerful computers.