Interactome algorithms - a problem in graph theory

Lord Snooty fred at fred.com
Tue Apr 22 03:47:18 EST 2003

Imagine we have a set of nodes interconnected in some way, and we wish
to deduce the connections.
A connection is defined as directed and reinforcing. A node is defined
as either ON or OFF.
For example, the graph
A->B->C
implies that C will be ON only if both A and B are ON (logical AND).
However, in the graph
A->
C
B->
C will be ON if either A or B is ON (logical OR).

We are given the collection of nodes, and also given a table showing the
ON/OFF node states which are observed when
each node in turn is turned OFF (inhibited). It may or may not be the
case that we need to know which actual node was
inhibited, for each line in the table. For N nodes, we have an N-line
table with N columns per line, of course.

Notes
1. There may be many possible solutions for a given table, or possibly -
I am not sure - even no solution.
2. No restriction is placed on the graph topology, and in particular we
allow loops, and nested loops, to exist.
3. There's no concept of time; all measurements in the table are made
after equilibrium is reached.

My questions are:
1. Does a general procedure exist to deduce candidate graphs that
satisfy the table ?
2. How well would such a procedure generalise for both excitatory
(positive) connections as described above, but also
for inhibitory (negative) connections?
3. How well would such a procedure generalise for a graded response? In
this case we go from a digital node to an
analog node, and then not only must we deduce the topology, but also the
coupling coefficients of the connections.

Andrew Palfreyman