Keywords: Complex Infections, Epidemics, Epidemiology 

Testing a sample for the presence of a disease is a well-solved problem, but testing the sample for individual strains of the disease can be tricky. When the sample has a complex infection, that is, one with more than one strain, then disambiguating the constituent strains is an NP-hard problem. Previous approaches use a “templating” method, in which the strains are assumed to come from a set of previously known “template” strains, an assumption which is frequently false.

To address this, we have developed StrainRecon, an algorithm that uses mixed-integer optimization to estimate the strains within a mixed sample. In addition to being template-less, allowing us to estimate strains with arbitrary identities, StrainRecon also provides a measure of uncertainty of each of its estimations.

This ability to disambiguate complex infection lets us address several previously unsolved problems, including:

Malaria Epidemiology in Africa

Africa has a very high prevalence of malaria. Identifying how malaria spreads throughout it is key to planning public health interventions to help contain and treat it. However, due to its high prevalence, many of its infections are complex, making analysis difficult. StrainRecon allows us to peer into these complex infections, allowing epidemiological studies into its malaria populations that were previously intractable.

Proportions of samples with different number of strains and average Multiplicity-of-Infection by year 

Evaluating Drug Trials

New anti-malarial drugs are constantly being developed and tested. If a patient tests positive for malaria, takes the drug, and later tests negative for it, then the drug likely worked. If they still test positive for malaria, though, then the drug is assumed to have failed. However, there is a more sinister possibility: the patient may have been cured of their infection, but then re-infected before their second test. In regions with a high prevalence of malaria, this can be a serious concern in drug trials.

To address this possibility, it’s not enough to simply test for malaria- the individual strains in a test subject must be compared before and after drug administration. StrainRecon makes this possible. With StrainRecon, we can not only do this comparison, but also quantify the likelihood that the strains in each sample do or don’t match.

Comparing strains in samples from an individual taken 3 days apart

Analyzing Enteric Diseases and their most deadly strains

Infections of enteric diseases, like E. Coli, Salmonella, and Listeria, vary greatly in their virulence. It is thought that certain combinations of strains may be particularly strong, but until now, there has been no way to find the individual strains in such infections. StrainRecon gives us the resolution to do precisely this, letting us compare the strains found in severe cases to those found in mild cases in order to uncover the more concerning combinations of strains.