Combinatorial optimization in rapidly mutating drug-resistant viruses

Resistance to chemicals is a common current problem in many pests and patho gens that formerly were controlled by chemicals. An extreme case occurs in rapidly mutating viruses such as Human Immunodeficiency Virus (HIV), where the emergence of selective drug resistance within an individual patient may become an important factor in treatment choice. The HIV patient subpopulat ion that already has experienced at least one treatment failure due to drug resistance is considered more challenging to treat because the treatment o ptions have been reduced. A triply nested combinatorial optimization proble m occurs in computational attempts to optimize HIV patient treatment protoc ol (drug regimen) with respect to drug resistance, given a set of HIV genet ic sequences from the patient. In this paper the optimization problem is ch aracterized, and the objects involved are represented computationally. An i mplemented branch-and-bound algorithm that computes a solution to the probl em is described and proved correct. Data shown includes empirical timing re sults on representative patient data, example clinical output, and summary statistics from an initial small-scale human clinical trial.