As biological data about genes and their interactions proliferates, scientists have the opportunity to identify sets of proteins whose interactions make them worthy of further investigation. This paper reports on a knowledge discovery technique to support that work. Foretell is an algorithm originally designed to support search for solutions to constraint satisfaction problems. Recent adaptations enable Foretell to detect sets of genes that interact heavily with one another. We provide empirical results, and describe ongoing work on biological meaning and knowledge infusion from the user.

Constraint satisfaction problems are mathematical models of real-world problems. In contrast to randomly generated artificial problems, real-world problems usually have non-random structure. Knowledge about that structure, when identified in advance, can make search to find solutions more effective. This paper introduces DrawCSP, a visualization program that can show both the original and the discovered structure of constraint satisfaction problems. DrawCSP provides insight into both search algorithm design and into the challenges real-world problems present.

In a constraint satisfaction problem, the tightness of an individual constraint only describes the influence that the variables within its scope have on one another. Clusters provide a broader view; they are dense, tight subproblems within a problem. A set of clusters for a problem and the links between them provide an abstraction of it. That abstraction can be used to guide search, to curtail inference, and to provide explanations to the user. This work is a hybrid of global and local search, where local search creates an abstraction and then global search exploits it. Heuristics reference clusters to order variables and to propagate more thoughtfully with respect to them. Results are provided on a variety of challenging benchmark problems.