Zhenping Li, Zhang Shihua, Wang Yong, Zhang Xiang-Sun, Chen Luonan
Beijing Wuzi University, Beijing 101149, China.
Bioinformatics. 2007 Jul 1;23(13):1631-9. doi: 10.1093/bioinformatics/btm156. Epub 2007 Apr 27.
With more and more data on molecular networks (e.g. protein interaction networks, gene regulatory networks and metabolic networks) available, the discovery of conserved patterns or signaling pathways by comparing various kinds of networks among different species or within a species becomes an increasingly important problem. However, most of the conventional approaches either restrict comparative analysis to special structures, such as pathways, or adopt heuristic algorithms due to computational burden.
In this article, to find the conserved substructures, we develop an efficient algorithm for aligning molecular networks based on both molecule similarity and 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 with or without loops.
Matlab code and data are available from http://zhangroup.aporc.org/bioinfo/MNAligner or http://intelligent.eic.osaka-sandai.ac.jp/chenen/software/MNAligner, or upon request from authors.
Supplementary data are available at Bioinformatics online.
随着越来越多的分子网络数据（如蛋白质相互作用网络、基因调控网络和代谢网络）可用，通过比较不同物种之间或同一物种内的各种网络来发现保守模式或信号通路成为一个日益重要的问题。然而，大多数传统方法要么将比较分析限制在特殊结构（如通路）上，要么由于计算负担而采用启发式算法。
在本文中，为了找到保守子结构，我们开发了一种基于分子相似性和结构相似性的高效算法，通过整数二次规划（IQP）来比对分子网络。这种IQP可以松弛为相应的二次规划（QP），几乎总能确保得到整数解，从而使分子网络比对无需任何近似即可处理。所提出的框架非常灵活，可应用于多种分子网络，包括加权和未加权、有向和无向、有环或无环的网络。
补充数据可在《生物信息学》在线获取。
