zbMATH — the first resource for mathematics

Natalie 2.0: sparse global network alignment as a special case of quadratic assignment. (English) Zbl 07042299
Summary: Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is still lagging behind. This holds in particular for the field of comparative network analysis, where one wants to identify commonalities between biological networks. Since biological functionality primarily operates at the network level, there is a clear need for topology-aware comparison methods. We present a method for global network alignment that is fast and robust and can flexibly deal with various scoring schemes taking both node-to-node correspondences as well as network topologies into account. We exploit that network alignment is a special case of the well-studied quadratic assignment problem (QAP). We focus on sparse network alignment, where each node can be mapped only to a typically small subset of nodes in the other network. This corresponds to a QAP instance with a symmetric and sparse weight matrix. We obtain strong upper and lower bounds for the problem by improving a Lagrangian relaxation approach and introduce the open source software tool Natalie 2.0, a publicly available implementation of our method. In an extensive computational study on protein interaction networks for six different species, we find that our new method outperforms alternative established and recent state-of-the-art methods.

92 Biology and other natural sciences
90 Operations research, mathematical programming
Full Text: DOI
[1] Szklarczyk, D.; Franceschini, A.; Wyder, S.; Forslund, K.; Heller, D.; Huerta-Cepas, J.; Simonovic, M.; Roth, A.; Santos, A.; Tsafou, K.P.; STRING v10: Protein-protein interaction networks, integrated over the tree of life; Nucleic Acids Res.: 2015; Volume 43 .
[2] Sharan, R.; Ideker, T.; Modeling cellular machinery through biological network comparison; Nat. Biotechnol.: 2006; Volume 24 ,427-433.
[3] Kanehisa, M.; Goto, S.; Hattori, M.; Aoki-Kinoshita, K.F.; Itoh, M.; Kawashima, S.; Katayama, T.; Araki, M.; Hirakawa, M.; From genomics to chemical genomics: New developments in KEGG; Nucleic Acids Res.: 2006; Volume 34 .
[4] Alon, U.; Network motifs: Theory and experimental approaches; Nat. Rev. Genet.: 2007; Volume 8 ,450-461.
[5] Elmsallati, A.; Clark, C.; Kalita, J.; Global alignment of protein-protein interaction networks: A survey; IEEE/ACM Trans. Comput. Biol. Bioinf.: 2015; Volume 99 .
[6] Singh, R.; Xu, J.; Berger, B.; Global alignment of multiple protein interaction networks with application to functional orthology detection; Proc. Natl. Acad. Sci. USA: 2008; Volume 105 ,12763-12768.
[7] Klau, G.W.; A new graph-based method for pairwise global network alignment; BMC Bioinf.: 2009; Volume 10 .
[8] Kuchaiev, O.; Milenkovic, T.; Memisevic, V.; Hayes, W.; Przulj, N.; Topological network alignment uncovers biological function and phylogeny; J. R. Soc. Interface: 2010; Volume 7 ,1341-54.
[9] Patro, R.; Kingsford, C.; Global network alignment using multiscale spectral signatures; Bioinformatics: 2012; Volume 28 ,3105-3114.
[10] Neyshabur, B.; Khadem, A.; Hashemifar, S.; Arab, S.S.; NETAL: A new graph-based method for global alignment of protein-protein interaction networks; Bioinformatics: 2013; Volume 29 ,1654-1662.
[11] Aladağ, A.E.; Erten, C.; SPINAL: Scalable protein interaction network alignment; Bioinformatics: 2013; Volume 29 ,917-924.
[12] Chindelevitch, L.; Ma, C.Y.; Liao, C.S.; Berger, B.; Optimizing a global alignment of protein interaction networks; Bioinformatics: 2013; Volume 29 ,2765-2773.
[13] Hashemifar, S.; Xu, J.; HubAlign: An accurate and efficient method for global alignment of protein-protein interaction networks; Bioinformatics: 2014; Volume 30 ,i438-i444.
[14] Vijayan, V.; Saraph, V.; Milenković, T.; MAGNA++: Maximizing accuracy in global network alignment via both node and edge conservation; Bioinformatics: 2015; Volume 31 .
[15] Clark, C.; Kalita, J.; A multiobjective memetic algorithm for PPI network alignment; Bioinformatics: 2015; Volume 31 ,1988-1998.
[16] Malod-Dognin, N.; Przulj, N.; L-GRAAL: Lagrangian graphlet-based network aligner; Bioinformatics: 2015; Volume 31 ,2182-2189.
[17] Natalie 2.0; ; .
[18] El-Kebir, M.; Brandt, B.W.; Heringa, J.; Klau, G.W.; NatalieQ: A web server for protein-protein interaction network querying; BMC Syst. Biol.: 2014; Volume 8 .
[19] NatalieQ; ; .
[20] Karp, R.M.; Reducibility Among Combinatorial Problems; Complexity of Computer Computations: New York, NY, USA 1972; ,85-103.
[21] Lawler, E.L.; The quadratic assignment problem; Manage Sci.: 1963; Volume 9 ,586-599. · Zbl 0995.90579
[22] Adams, W.P.; Johnson, T.; Improved linear programming-based lower bounds for the quadratic assignment problem; DIMACS Ser. Discr. Math. Theor. Comput. Sci.: 1994; Volume 16 ,43-77. · Zbl 0819.90049
[23] Kuhn, H.W.; The Hungarian method for the assignment problem; Naval Res. Logist. Q.: 1955; Volume 2 ,83-97. · Zbl 0143.41905
[24] Munkres, J.; Algorithms for the assignment and transportation problems; SIAM J. Appl. Math.: 1957; Volume 5 ,32-38. · Zbl 0083.15302
[25] Edmonds, J.; Karp, R.M.; Theoretical improvements in algorithmic efficiency for network flow problems; J. ACM: 1972; Volume 19 ,248-264. · Zbl 0318.90024
[26] Edmonds, J.; Path, trees, and flowers; Can. J Math: 1965; Volume 17 ,449-467. · Zbl 0132.20903
[27] Guignard, M.; Lagrangean relaxation; Top: 2003; Volume 11 ,151-200. · Zbl 1079.90087
[28] Held, M.; Karp, R.M.; The traveling-salesman problem and minimum spanning trees: Part II; Math. Progr.: 1971; Volume 1 ,6-25. · Zbl 0232.90038
[29] Caprara, A.; Fischetti, M.; Toth, P.; A heuristic method for the set cover problem; Oper. Res.: 1999; Volume 47 ,730-743. · Zbl 0976.90086
[30] LEMON Graph Library; ; .
[31] Ashburner, M.; Ball, C.A.; Blake, J.A.; Botstein, D.; Butler1, H.; Cherry, J. M.; Davis, A.P.; Dolinski, K.; Dwight, S.S.; Eppig, J.T.; Gene Ontology: Tool for the unification of biology; Nat. Genet.: 2000; Volume 25 ,25-29.
[32] Couto, F.M.; Silva, M.J.; Coutinho, P.M.; Measuring Semantic Similarity between Gene Ontology Terms; Data Knowl. Eng.: 2007; Volume 61 ,137-152.
[33] Wohlers, I.; Andonov, R.; Klau, G.W.; Algorithm Engineering for optimal alignment of protein structure distance matrices; Optim. Lett.: 2011; Volume 5 ,421-433. · Zbl 1259.90073
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.