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.

Download

Publications