Interactome algorithms - a problem in graph theory

Alessandro Macrì macri at informatik.uni-muenchen.de
Wed Apr 23 00:32:38 EST 2003


On 17 Apr 2003, Lord Snooty wrote:

> My questions are:
> 1. Does a general procedure exist to deduce candidate graphs that
> satisfy the table ?

Of course: brute force (generation of all graphs).
I don't know if there is a more efficient method. In fact your table is a
description of the transitive hull (reachability of each node from each
other node). So the problem would be to produce all possible graphs according
to a given transitive hull.
I simply don't know if there's an efficient algorithm but strongly suspect
it's NP-hard. Perhaps constraint reasoning would be a method to eliminate
large parts of the search space, but haven't got a clue how the rules would
look like.

> 2. How well would such a procedure generalise for both excitatory
> (positive) connections as described above, but also for inhibitory
> (negative) connections?

One weakness: it's not quantified. There is no possibility to express "half
activity of each A and B is sufficient to excite C" (corresponds to your
point 3).

> 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.

I'm not sure about it. Following my Intuition I would say it's still in the
same problem class.

ciao

-- 
Alessandro Macrì                                 "panta rhei" (Heraklit)
Tel +49 89 2180-4059                    macri at informatik.uni-muenchen.de
Fax +49 89 2180-4054        http://www.informatik.uni-muenchen.de/~macri
LMU München, LFE Bioinformatik, Theresienstr. 39, 80333 München, Zi. 305






More information about the Comp-bio mailing list