MNAligner
Alignment of
Molecular Networks by Quadratic Programming
[Version 1.0]
Dec 18, 2006
see also:
http://zhangroup.aporc.org/bioinfo/mnaligner/
METHOD
======
Motivation
With more and more data on molecular networks (e.g. protein interaction
network, gene regulatory network and metabolic network) available, the
discovery of conserved patterns or signal pathways by comparing various kinds
of networks among different species or within a species becomes an increasingly
important problem. However, due to the high complexity to compare molecular
networks, most of the conventional approaches either restrict comparative
analysis to special structures, such as pathways, or adopt heuristic algorithms
so as to make the computation of the alignment problem tractable.
Results In this paper,
to find the conserved substructures, we develop an efficient algorithm for
aligning molecular networks based on both the nodes' similarity and the network
architecture similarity, by using integer quadratic programming (IQP). Such an
IQP can be relaxed into the corresponding quadratic programming (QP) which
almost always ensures an integer solution, thereby making molecular network
alignment tractable without any approximation. The proposed framework is very
flexible and can be applied to many kinds of molecular networks including
weighted and unweighted, directed and undirected
networks. It can not only detect simple linear paths or tree subnets, and also
uncover general subnet patterns. Meanwhile,
it not only can find the simple topological substructure such as chains and
trees, but also can reveal biologically meaningful units with cycles.
REFERENCE
Zhenping Li, Shihua Zhang, Yong
Wang, Xiang-Sun Zhang and Luonan Chen. Alignment of molecular networks by
integer quadratic programming, In submission.
SOFTWARE
Contents:
NetAlign.m – The mail function to implement our QP
model.
Two examples from our manuscript
(undirected and directed):
NetworkAlignment-eg1.m
NetworkAlignment-eg2.m
Generate Random Networks
(undirected and directecd) from (http://www.cmth.bnl.gov/~maslov/matlab.htm):
GenRandomNet.m
GenRandomDirNet.m
Solve QP model with interior
algorithm from Ye (http://www.stanford.edu/~yyye/matlab.html).
spsolqp.m
spphase1.m
spphase2.m
This is a beta
version of the program for preliminary testing. The program is still under
development.