MULE: Software for Detecting Conserved Interaction Patterns in Biological Networks
Molecular interaction data plays an important role in understanding biological processes at
a modular level by providing a framework for understanding cellular organization, functional
hierarchy, and evolutionary conservation.
An important computational problem for comparative analysis of these networks is to identify
subgraphs that are common to a large fraction of a given set of networks.
This problem is computationally intractable due to their relation to subgraph isomorphism.
MULE (Mining Uniquely Labeled Edgesets) uses a graph simplification technique based
on ortholog contraction, which is ideally suited to biological networks, to render
this problem computationally tractable and scalable to large numbers of networks.
MULE can be used as a pruning heuristic to simplify the harder graph mining task
or a closely related, but computationally simpler task, which also
provides significant biological insights by identifying conserved interaction
patterns among protein families.
- M. Koyuturk, Y. Kim, S. Subramaniam, W. Szpankowski, and A. Grama,
Detecting conserved interaction patterns in biological networks,
Journal of Computational Biology,
13(7), 1299-1322, 2006.
- M. Koyuturk, A. Grama, and W. Szpankowski,
An efficient algorithm for detecting frequent subgraphs in biological networks,
BioInformatics Suppl. on ISMB/ECCB'04,
20, i200-i207, 2004.