## The Bioinformatics Lab

#### Topology aware coloring of gene regulatory networks

**Abstract:**

We consider the problem of finding a subnetwork in a given
biological network (i.e., target network) that is the most
similar to a given small query network. We aim to find
the optimal solution (i.e., the subnetwork with the largest
alignment score) with a provable confidence bound. There
is no known polynomial time solution to this problem in the
literature. Alon et al. has developed a state of the art coloring
method that reduces the cost of this problem. This
method randomly colors the target network prior to alignment
for many iterations until a user supplied confidence is
reached. Here we develop a novel coloring method, named
k-hop coloring (k is a positive integer), that achieves a provable
confidence value in a small number of iterations without
sacrificing the optimality. Our method considers the color
assignments already made in the neighborhood of each target
network node while assigning a color to a node. This
way, it preemptively avoids many color assignments that are
guaranteed to fail to produce the optimal alignment. We also
develop a filtering method that eliminates the nodes which
cannot be aligned without reducing the alignment score after
each coloring instance. We demonstrate both theoretically
and experimentally that our coloring method outperforms
that of Alon et al. which is also used by a number network
alignment methods including QPath and QNet by a factor
of three without reducing the confidence in the optimality
of the result. Our experiments also suggest that the resulting
alignment method is capable of identifying functionally
enriched regions in the target network successfully.

**Additional Data:**

Sample queries

The database networks

The sequence information for all networks

**People:**

- Gunhan Gulsoy
- Bhavik Gandhi
- Tamer Kahveci

Tamer Kahveci
Last modified: Thu Mar 23 10:20:32 EDT 2011