The Bioinformatics Lab

Home People Publications Projects Courses Funding Contact Archive

Topology aware coloring of gene regulatory networks

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


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