Drug discovery optimization: a meeting point for data mining, graph theory and operations research

How can I help finding the best compound to save a life?

In a glance, the answer is what research in optimizing drug design is about. Its main goal is to cheapen and speed-up drug development whilst producing more effective and less toxic pharmaceuticals. It is an interesting topic that involves much of what business analytics and optimization professionals use daily to solve problems in many other areas. For that reason, I decided to write about that for April’s INFORMS Blog Challenge: O.R. in Health Care.

Drug design basics: in vitro vs. in silico methods and QSAR analysis

Before a drug can be prescribed to humans, it must pass through a careful evaluation. However, it would not be reasonable or even feasible to test every possible compound for each desired effect, especially if such tests involve animals. Pharmaceutical researchers are interested in screening molecules on a huge data set, so that only those molecules that are most likely to work are ultimately tested in vitro, in animals and ultimately in humans. They accomplish that with computer-aided predictive analysis commonly called in silico tests.

In silico tests are designed in the belief that there exists a valid theory to extrapolate quantitatively the activity of a compound based on similar ones, using tools like Quantitative Structure-Activity Relationship (QSAR) analysis. The goal of a QSAR analysis is to find a function capable of predicting the activity of the main molecule of a compound based on the presence and quantity of certain molecular substructures. We are then lead to the quest for a way of representing molecules and to use available data about an activity to create trustable predictions for similar molecules.

The role of data mining and molecules as graphs

For many purposes, a molecule is just a graph with vertices and edges. However, the fact that molecular data are more structured does not mean that the problem is easier. Roughly* deciding whether one graph can be found inside another one is know as the Sub-Graph Isomorphism problem. That problem is NP-Complete, what means that there is not know an efficient algorithm to solve it.

(* By roughly, I ask you to forgive the lack of formality in which I defined sub-isomorphism: graphs are not said to be inside each other. A one-to-one correspondence between one graph or sub-graph and another one is called an isomorphism. However, if I was to tell it at first, I would lose most of the audience.)

More than just finding a sub-graph isomorphism, one is usually interested in find the most frequent ones. One interesting approach to Frequent Sub-Graph (FSG) mining is gSpan, a DFS-based mining algorithm proposed by Yan and Han. It consists of defining a unique lexicographic encoding for each sub-graph so that it can be counted more easily while exploring molecular data. There is also a controversy about the validity of 2D models such as graphs for modeling molecules, specially because some geometric subtleties differ a innocuous molecule from a a carcinogenic one. Thus, it is worth of notice that predictive models are not intended to skip in vitro tests but just point out which molecules are most likely to work out.

How can operations research fit in?

There are a number of O.R. applications for what we have been discussing here.

I would like to mention one interesting application of Linear Programming (LP) to QSAR analysis by Saigo, Kodawaki and Tsuda. Their approach consisted of using LP to build a regression function for prediction in which error is minimized. It is based on positive and negative relations between molecules and activities, that is, a quantitative relation among each molecule and the activity or a constraint imposing that such relation is not relevant. The decision variables of the problem are the coefficients associated with every possible substructure. Since there can be a lot of possible substructures, they start with a small problem and there is a column generation algorithm that tries to find a new variable whose addition to the problem might improve the results.

Final remarks: OR and the invisible good

The fun of many professions is to see the benefit of what you are doing. That is even more present in health care, since you are dealing with people and their lives. On the other hand, OR is the kind of invisible science, which is on its best use when the average people can not sense its presence. Notwithstanding, OR practitioners enjoy numbers and are glad to know that things are a bit better because of their work behind the scenes. Despite that, blogging about OR can help people notice the importance of the area to support others that are commonly visible to everyone.

Optimizing Public Policies for Urban Planning

Another possible title would be “Marrying an urban planner up to her research problems”.

It all happened when I started hearing my fiancée explaining the problems of Brazilian housing policy and ended up with an interesting model for sustainable housing subsidy that she presented at the Latin American Real Estate Society meeting of 2009.

The problem: Housing policy in Brazil

The main housing subsidy for low-income families in Brazil is based on a federal program roughly called “My House, My Life”, in which public subsidy consists of an amount of money for each constructed housing unit that varies solely according to the city.

In a place like São Paulo, the unavoidable consequence of such policy is to further sprawl low-income families towards suburban areas.
Most of them already spend much more than two hours per day to go to work.
Moreover, great distances prevent them from going to work on foot or bicycle, what raises public transportation demand and decreases their purchasing power.

São Paulo in 2009: Job offer vs. low-income settlement (source: SEMPLA).

What we did: A model for variable subsidy

We started looking for the main problems of distant placement of such families:

• Bad life quality due to the time wasted for displacing.
• More pollution due to the large displacements.
• Public expenditures to support the public transportation system.

Instead of creating a complex multi-criteria model to tackle that, we just considered that people must be placed at most one hour apart from 50% of the jobs in the city (seems fair, right?) and considered the criteria in which anything is actually done: money!

After all, how much does it cost to the government if families are so far from their jobs?

• If the place is too far, one must account the per-family cost on bringing adequate public transportation infrastructure up to there.
• Depending on the modal of transportation, there must be public subsidies and also the carbon footprint cost, which were accounted for two people per family to work for one generation (25 years).

Thus, if you have a 20K subsidy to place a house or apartment anywhere in the city, it would be fair to raise that in places where nothing else must be done. For instance, we realized that extending a subway line costs about 20K per family, that is, government actually spends the double to bring adequate infrastructure, if not more.

São Paulo’s downtown: A very good infrastructure and many abandoned buildings.

What’s next?

To what concern the O.R. community, it is not a challenging problem in terms of algorithms but there is a lot of room to improve modeling.
Unfortunately, we did not apply our model completely due to the lack of data, but we hope to do that someday.
However, it is already possible to devise the possibilities of reducing public expenditures, and forthcoming approaches would provide integrated decision models for housing subsidy and infrastructure investments.

Talking about multidisciplinary: O.R. at the Public Sector

A multidisciplinary approach might start at your own home, and it may point out interesting challenges that academia might not have been devised so far.
In Brazil, where public sector decisions are all but technical, there are big opportunities yet to be explored.