Joint Alignment of Multiple Protein–Protein Interaction Networks via Convex Optimization

Abstract

High-throughput experimental techniques have been producing more and more protein–protein interaction (PPI) data. The PPI network alignment greatly benefits the understanding of evolutionary relationship among species, helps identify conserved subnetworks, and provides extra information for functional annotations. Although a few methods have been developed for multiple PPI network alignment, the alignment quality is still far from perfect, and thus, new network alignment methods are needed. In this article, we present a novel method, denoted as ConvexAlign, for joint alignment of multiple PPI networks by convex optimization of a scoring function composed of sequence similarity, topological score, and interaction conservation score. In contrast to existing methods that generate multiple alignments in a greedy or progressive manner, our convex method optimizes alignments globally and enforces consistency among all pairwise alignments, resulting in much better alignment quality. Tested on both synthetic and real data, our experimental results show that ConvexAlign outperforms several popular methods in producing functionally coherent alignments. ConvexAlign even has a larger advantage over the others in aligning real PPI networks. ConvexAlign also finds a few conserved complexes, which cannot be detected by the other methods.

1. Introduction

Protein–protein interaction (PPI) networks provide valuable information for understanding of protein functions and system-level cellular processes. The alignment of PPI networks is a useful means for comparing the networks of different species, identifying evolutionarily and functionally conserved pathways/complexes, and protein function prediction. Studying the conserved modules may provide useful information about the molecular mechanism contributing to their functions.

PPI networks can be aligned either locally or globally. Local network alignment methods aim to find conserved subnetworks among a set of input networks (Koyutürk et al., 2006; Ciriello et al., 2012), while global network alignment (GNA) methods maximize the overall match between input networks (Singh et al., 2007, 2008; Kuchaiev and Pržulj, 2011; Patro and Kingsford, 2012; Neyshabur et al., 2013; Todor et al., 2013; Hashemifar and Xu, 2014; Saraph and Milenković, 2014; Vijayan et al., 2015). More methods are developed for pairwise network alignment. With the availability of more PPI networks, it becomes inevitable to align multiple networks. Existing GNA methods such as NetworkBlast-M (Sharan et al., 2005; Kalaev et al., 2008) and GraemLin2.0 (Flannick et al., 2008) are designed for local alignment of multiple networks, whereas others such as IsoRankN (Liao et al., 2009), SMETANA (Sahraeian and Yoon, 2013), NetCoffee (Hu et al., 2014), BEAMS (Alkan and Erten, 2014), and FUSE (Gligorijević et al., 2015) are for GNA. Most methods make use of both sequence similarity and network topology, and are designed for many-to-many alignments.

NetworkBlast-M starts with a set of highly conserved regions and then extends them greedily. GraemLin2.0 integrates phylogenetic information and network topology and then uses a hill-climbing algorithm to generate the alignment. IsoRankN applies IsoRank to compute pairwise alignment scores first and then uses a PageRank-Nibble algorithm to cluster the proteins. SMETANA uses a semi-Markov random walk model to measure similarity between proteins. BEAMS constructs a weighted k-partite graph in which edge weights are derived from protein sequence similarity. NetCoffee applies a triplet approach to compute the edge weights of the k-partite graph. Both BEAMS and NetCoffee apply a heuristic on the k-partite graph to build an alignment. BEAMS fulfills this by greedily merging a set of disjoint cliques whereas NetCoffee does this by applying a simulated annealing method. FUSE applies a non-negative matrix tri-factorization method to compute edge weights of the k-partite graph.

Although a few GNA methods have been developed, GNA is still far from mature, especially for multiple network alignment (MNA). First, many existing methods do not optimize alignment of all proteins simultaneously. They either use a seed and extension or progressive strategy to build an MNA, so they cannot easily fix errors introduced at an early stage. Second, many existing methods do not fare well in detecting proteins that are functionally conserved across multiple (≥4) PPI networks, partially due to their greedy strategy of building an MNA.

This article presents a novel one-to-one algorithm, ConvexAlign, to align multiple PPI networks using a new scoring scheme that integrates network topology, sequence similarity, and interaction conservation score. We formulate GNA problem as an integer program and relax it to a convex optimization problem, which enables us to simultaneously align all the PPI networks, without resorting to the widely used seed and extension or progressive alignment methods. We use an alternating direction method of multipliers (ADMM) method to solve the relaxed convex optimization problem and optimize all the protein mappings together. Experimental results indicate that ConvexAlign outperforms state-of-the-art methods in terms of biological alignment quality and finding conserved complexes.

2. Methods

Definition. We represent a PPI network by an undirected graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G = ( V , E )$$ \end{document} , where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V$$ \end{document} is the set of proteins and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E$$ \end{document} the set of interactions. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d ( u )$$ \end{document} denote the degree of vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$u$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$e = ( u , v ) \in E$$ \end{document} represent an edge. A one-to-one global alignment \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal A}$$ \end{document} between \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$N$$ \end{document} networks \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${G_i} = ( {V_i} , {E_i} ) , 1 \le i \le N$$ \end{document} is given by a decomposition of all nodes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal V} = \cup _{i = 1}^N{V_i}$$ \end{document} such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal V} = {{ \cal A}_1} \cup \cdots \cup {{ \cal A}_K}$$ \end{document} , where each \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \cal A}_i}$$ \end{document} contains at most one protein from each network and any two \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \cal A}_i}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \cal A}_j}$$ \end{document} are disjoints. We call each \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${A_i}$$ \end{document} in the alignment a cluster. Proteins in each cluster are mutually aligned to one another.

2.1. Develop a much more sensitive scoring function

Our goal is to find an alignment that maximizes the number of preserved edges and the number of matched orthologous proteins. Our scoring function consists of two items; one for protein similarity and the other for interaction conservation, that is, we score an alignment \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal A}$$ \end{document} as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} f ( { \cal A} ) = ( 1 - { \lambda _2} ) {f_{{ \rm{node}}}} ( { \cal A} ) + { \lambda _2}{f_{{ \rm{edge}}}} ( { \cal A} ) , \tag{1} \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${f_{{ \rm{node}}}}$$ \end{document} is for node similarity and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${f_{{ \rm{edge}}}}$$ \end{document} for interaction conservation. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \lambda _2}$$ \end{document} describes the tradeoff. Similar to multiple sequence alignment, we also use a sum-of-pairs scoring function for MNA. In particular, the node score \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${f_{{ \rm{node}}}} ( { \cal A} )$$ \end{document} sums the scores among all pairs of aligned proteins: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {f_{{ \rm{node}}}} ( { \cal A} ) = \mathop \sum \limits_{1 \le i < j \le N} \mathop \sum \limits_{{{ \cal A}_k} \in { \cal A} , {v_i} , {v_j} \in {{ \cal A}_k}} {\rm node} ( {v_i} , {v_j} ) , \tag{2} \end{align*} \end{document}

2.2. Integer and convex programming formulation

Let M be the number of proteins in all the input PPI networks, that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$M = \mathop \sum \limits_{i = 1}^N { \vert {V_i} \vert }$$ \end{document} . We represent a valid multiple alignment \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal A}$$ \end{document} by a binary matrix Y = (Y₁;Y₂; \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\cdots$$ \end{document} ; Y_N) ∈{0,1}^M×K, where each block Y_i encodes the association between V_i and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal A}$$ \end{document} . Each row of Y corresponds to one vertex and each column to one alignment cluster. That is, ∀v_i ∈V_i, Y_i (v_i, A_j) = 1 if, and only if, v_i is in cluster A_j. Although Y is a good representation of an MNA, the objective function with Y as a variable is nonlinear and, thus, hard to optimize. Inspired by Huang and Guibas (2013), we introduce another alignment matrix X as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} X = \left( { \begin{matrix} {{I_{ \vert {V_1} \vert }}} & {{X_{12}}} & \cdots & {{X_{1N}}} \\ {X_{12}^T} & {{I_{ \vert {V_2} \vert }}} & \cdots & {{X_{2N}}} \\ \vdots & \cdots & \ddots & \vdots \\ {X_{1N}^T} & \cdots & \cdots & {{I_{ \vert {V_N} \vert }}} \\ \end{matrix} } \right) = \left( { \begin{matrix} {{Y_1}} \\ {{Y_2}} \\ \vdots \\ {{Y_N}} \\ \end{matrix} } \right) \cdot { \left( { \begin{matrix} {{Y_1}} \\ {{Y_2}} \\ \vdots \\ {{Y_N}} \\ \end{matrix} } \right) ^T} , \end{align*} \end{document}

where each block X_ij = Y_iY_j^T is a binary matrix encoding the mapping between V_i and V_j. That is, X_i,j(v_i,v_j) = 1, if and only if, v_i and v_j are aligned (i.e., in the same alignment cluster).

\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X$$ \end{document} is a positive semidefinite matrix. Since this section considers only one-to-one mapping, for any two \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$j$$ \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( i \ne j )$$ \end{document} , each row or column of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${X_{ij}}$$ \end{document} has at most one nonzero element, that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${X_{ij}} \vec 1 \le \vec 1$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X_{ij}^T \vec 1 \le \vec 1$$ \end{document} , where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vec 1$$ \end{document} is a vector of appropriate size with all entries 1. Regarding the Proposition 1 in Supplementary Material Section D, we may encode a one-to-one GNA using \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X$$ \end{document} , which leads to a linear formulation of the objective function. In particular, the node score can be formulated as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {f_{{ \rm{node}}}} = \mathop \sum \limits_{1 \le i < j \le N} \mathop \sum \limits_{v \in {V_i} , v^{\prime} \in {V_j}} { \rm{node}} ( v , v^{\prime} ) {X_{ij}} ( v , v^{\prime} ) = \mathop \sum \limits_{1 \le i < j \le N} \langle {C_{ij}} , {X_{ij}} \rangle , \tag{4} \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${C_{ij}}$$ \end{document} is a matrix composed of the values of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${\rm node} ( v , v^{\prime} )$$ \end{document} . To formulate \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${f_{{ \rm{edge}}}}$$ \end{document} , we introduce indicator variables \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${y_{ij}} ( {v_i} , {v_j} , {v^{\prime} _i} , {v^{\prime} _j} )$$ \end{document} for edge correspondences: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {y_{ij}} ( {v_i} , {v_j} , {v^{\prime} _i} , {v^{\prime} _j} ) = {X_{ij}} ( {v_i} , {v_j} ) {X_{ij}} ( {v^{\prime} _i} , {v^{\prime} _j} ) , \quad \forall ( {v_i} , {v^{\prime} _i} ) \in {E_i} , ( {v_j} , {v^{\prime} _j} ) \in {E_j} , 1 \le i < j \le N. \tag{5} \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {f_{{ \rm{edge}}}} = \mathop \sum \limits_{1 \le i < j \le N} \mathop \sum \limits_{ ( {v_i} , {{v^{\prime} }_i} ) \in {E_i} , ( {v_j} , {{v^{\prime} }_j} ) \in {E_j}} {y_{ij}} ( {v_i} , {v_j} , {v^{\prime} _i} , {v^{\prime} _j} ) = \mathop \sum \limits_{1 \le i < j \le N} \langle \vec 1 , {{ \bf{y}}_{ij}} \rangle , \tag{6} \end{align*} \end{document}

The nonlinear constraint (5) can be replaced by the following linear inequalities [c.f. Kumar et al., (2008) and Huang et al., (2011)]: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \forall {v^{\prime} _j} \in {V_j} , \mathop \sum \limits_{{{v^{\prime} }_i}: ( {v_i} , {{v^{\prime} }_i} ) \in {E_i}} y ( {v_i} , {v_j} , {v^{\prime} _i} , {v^{\prime} _j} ) \le {X_{ij}} ( {v_i} , {v_j} ) \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \forall {v^{\prime} _i} \in {V_i} , \mathop \sum \limits_{{{v^{\prime} }_j}: ( {v_j} , {{v^{\prime} }_j} ) \in {E_j}} y ( {v_i} , {v_j} , {v^{\prime} _i} , {v^{\prime} _j} ) \le {X_{ij}} ( {v_i} , {v_j} ) \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \forall {v_j} \in {V_j} , \mathop \sum \limits_{{v_i}: ( {v_i} , {{v^{\prime} }_i} ) \in {E_i}} y ( {v_i} , {v_j} , {v^{\prime} _i} , {v^{\prime} _j} ) \le {X_{ij}} ( {v^{\prime} _i} , {v^{\prime} _j} ) \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \forall {v_i} \in {V_i} , \mathop \sum \limits_{{v_j}: ( {v_j} , {{v^{\prime} }_j} ) \in {E_j}} y ( {v_i} , {v_j} , {v^{\prime} _i} , {v^{\prime} _j} ) \le {X_{ij}} ( {v^{\prime} _i} , {v^{\prime} _j} ) . \tag{7} \end{align*} \end{document}

It is easy to prove that (5) implies (7). On the other direction, considering that the coefficient of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \bf{y}}$$ \end{document} is positive, and we want to maximize (6), we shall be able to prove that (7) implies (5). We replace (5) by (7) to obtain linear constraints and summarize (7) in the matrix form as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {B_{ij}}{{ \textbf{\textit{y}}}_{ij}} \le {{ \cal F}_{ij}} ( {X_{ij}} ) , \tag{8} \end{align*} \end{document}

where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${B_{ij}}$$ \end{document} is coefficient and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \cal F}_{ij}}$$ \end{document} is a linear operator that picks the corresponding element of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${X_{ij}}$$ \end{document} for each constraint. That is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${{ \cal F}_{ij}} ( {X_{ij}} ( {v_i} , {v_j} ) ) = < {P_{ij}} , {X_{ij}} >$$ \end{document} , where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${P_{ij}}$$ \end{document} is a binary matrix with the same dimension as \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${X_{ij}}$$ \end{document} , and only one element \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${P_{ij}} ( {v_i} , {v_j} )$$ \end{document} is equal to 1.

Finally, by integrating (4), (6), and (8) and Proposition 1 (Supplementary Material), we have the following integer program: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} { \rm{maximize}} \quad \mathop \sum \limits_{1 \le i < j \le N} \left( ( 1 - { \lambda _2} ) \langle {C_{ij}} , {X_{ij}} \rangle + { \lambda _2} \langle \vec 1 , {y_{ij}} \rangle \right) \tag{9} \end{align*} \end{document}

subject to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$ {{ \textbf{\textit{y}}}_{ij}} \in { \{ 0 , 1 \} ^{ \vert {E_i} \vert \times \vert {E_j} \vert }} , \quad \quad 1 \le i < j \le N$$ \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {B_{ij}}{{ \textbf{\textit{y}}}_{ij}} \le {{ \cal F}_{ij}} ( {X_{ij}} ) , \quad\quad\ \ \ 1 \le i < j \le N \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {X_{ij}} \vec 1 \le \vec 1 , \ X_{ij}^T \vec 1 \le \vec 1 , \quad\quad1 \le i < j \le N \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {X_{ij}} \in { \{ 0 , 1 \} ^{ \vert {V_i} \vert \times \vert {V_j} \vert }} , \quad\quad1 \le i < j \le N \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} X \succeq 0 , \quad {X_{ii}} = {I_{ \vert {V_i} \vert }} , \quad\quad\ 1 \le i \le N \end{align*} \end{document}

The key constraint is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X \succeq 0$$ \end{document} , which enforces cycle consistency in the alignments. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X \succeq 0$$ \end{document} still holds even when N = 2.

2.3. Optimization via convex relaxation

It is NP-hard to directly optimizing (9) since the variables are binary. We first relax y_ij and X_ij to real values between 0 and 1: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} { \rm{maximize}} \quad \mathop \sum \limits_{1 \le i < j \le N} \Big ( ( 1 - { \lambda _2} ) \langle {C_{ij}} , {X_{ij}} \rangle + { \lambda _2} \langle 1 , {y_{ij}} \rangle \Big) \tag{10} \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} { \rm{subject}} \ { \rm{to}} \quad {{ \textbf{\textit{y}}}_{ij}} \ge { \bf{0}} , \ {B_{ij}}{{ \textbf{\textit{y}}}_{ij}} \le {{ \cal F}_{ij}} ( X ) , \quad \quad \quad \quad 1 \le i < j \le N \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} {X_{ij}} \vec 1 \le \vec 1 , \ X_{ij}^T \vec 1 \le \vec 1 , \ {X_{ij}} \ge 0 , \quad \quad \quad 1 \le i < j \le N \end{align*} \end{document} \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} X \succeq 0 , \quad {X_{ii}} = {I_{ \vert {V_i} \vert }} , \quad \quad \quad \quad \quad \quad \quad 1 \le i \le N \end{align*} \end{document}

Afterward, we use ADMM to solve the convex relaxationship (10). The basic idea is to augment its Lagrangian dual and iteratively optimize a subset of variables while keeping the others fixed (details in Supplementary Material Section H). Finally, we propose a greedy rounding strategy to convert fractional solution to integral. We collect all the protein pairs with an indicator value \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$X ( u , v ) > 0.05$$ \end{document} and place them in a decreasing order into a sorted list \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} . Then, we build an alignment graph starting with an empty edge set by scanning through \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} . For each scanned protein pair \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( u , v )$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \cal X}$$ \end{document} in the alignment graph, we add an edge to connect this pair as long as such an addition does not violate the constraint that no protein in one network is aligned to two proteins in another network. After all pairs are scanned, we decompose the alignment graph into connected components, each corresponding to a cluster of mutually aligned proteins. The set of all the clusters forms an alignment. Most components are cliques. For the very few nonclique components, we just add some edges to make them cliques. This rounding strategy works reasonably well (Supplementary Material Section E).

3. Results

We compare ConvexAlign with state-of-the-art methods IsoRankN (Liao et al., 2009), SMETANA (Sahraeian and Yoon, 2013), NetCoffee (Hu et al., 2014), BEAMS (Alkan and Erten, 2014), and FUSE (Gligorijević et al., 2015). We ran SMETANA, NetCofee, and FUSE with their default parameters. For BEAMS and IsoRankN, we set three values for their parameter α = {0.3, 0.5, 0.7}.

Test data: We use the PPI networks of Homo sapiens (human), Saccharomyces cerevisiae (yeast), Drosophila melanogaster (fly), Caenorhabditis elegans (worm), and Mus musculus (mouse) taken from IntAct (Kerrien et al., 2011). The network properties are shown in Table 1.

Table 1.

Properties of Networks of Five Species

	Mouse	Worm	Yeast	Fly	Human
No. of proteins	2897	4305	5674	8374	9003
No. of interactions	4372	7747	49,830	25,611	34,935

We also use NAPAbench (Sahraeian and Yoon, 2012), an extensive alignment benchmark that contains synthetic PPI network families generated by three different network models: crystal growth (Kim and Marcotte, 2008), duplication-mutation-complementation (Vázquez et al., 2003), and duplication with random mutation (Solé et al., 2002). We use the eight-way alignment data set, which contains 3 network families, each with 8 networks of 1000 nodes. The eight-way alignment data set simulates a network family of closely related species, so this benchmark has very different properties as the aforesaid five real PPI networks.

Alignment quality measures: We evaluate MNA quality using several topological and functional consistency metrics proposed in different studies. These metrics are defined in Supplementary Material Section F. Functional consistency measures, however, are more important than topological measures since one of the important applications of network alignment is to functional annotation transfer. For topological analysis of the output clusters, we use c-coverage, ratio of conserved interaction (RCI), and conserved interaction quality (CIQ). A multiple alignment with a higher c-coverage is not necessarily biologically meaningful since it may align many unrelated proteins together. Therefore, we also use GO terms to measure functional consistency of an alignment. GO terms describe roles of proteins in terms of their associated biological process (BP), molecular function (MF), and cellular component (CC). We exclude root GO terms from analysis, that is, GO terms on level higher than 5. We also exclude CC because proteins with matched CC are not usually considered functionally similar. Moreover, CC only annotates a small percentage of the proteins. The functional consistency measures specificity, average of functional similarity (AFS), mean normalized entropy (MNE), conserved orthologous interactions (COI), and sensitivity are based on the observation that functionally related proteins are more likely to have similar GO terms.

3.1. Alignment quality on real data

Topological quality: Supplementary Table S1 lists the topological evaluation of the competing methods. The first four multirows show the results for the clusters consisting of proteins belonging to c = 2, 3, 4, 5 species, respectively. In each multirow, the top and bottom rows show c-coverage and the number of proteins in the clusters, respectively. ConvexAlign has a larger c-coverage when c = 4, 5 than the other methods except SMETANA and NetCoffee. However, as we show later, many of the clusters generated by these two methods are not functionally conserved. The total coverage of BEAMS and IsoRank is better than the others because they produce many clusters composed of proteins from two or three species. These clusters cannot explain the data as well as clusters containing proteins from four or five species can. ConvexAlign has a better RCI than all other methods except SMETANA. These conserved interactions are very helpful in identifying the functional modules conserved among networks of different species.

Biological quality: Table 2 and Supplementary Table S2 provide the functional consistency measures of the competing methods. In the first four multirows, the top and middle rows show the number of consistent and annotated clusters, respectively, and the bottom row shows specificity. Regardless of c, ConvexAlign outperforms the other methods in terms of specificity and the number of consistent clusters. Although SMETANA, NetCoffee, and FUSE generate a larger number of clusters for c = 4, 5 than ConvexAlign, their clusters are not very functionally consistent. The fifth row shows that ConvexAlign has much higher specificity than the others when all the resulting clusters (c ≥ 2) are considered.

Table 2.

Functional Consistency of Output Clusters

	IsoRankN (0.5)	SMETANA	NetCoffee	BEAMS (0.5)	FUSE	ConvexAlign
c = 2
Consistent	1259	295	495	1568	0	1914
Annotated	2862	931	931	3456	2	2326
Specificity	0.44	0.39	0.53	0.45	0.00	0.82
c = 3
Consistent	466	188	462	1084	0	1155
Annotated	2153	1556	1640	2442	1356	1741
Specificity	0.22	0.12	0.28	0.44	0.00	0.66
c = 4
Consistent	106	170	406	624	175	661
Annotated	723	2019	1640	1136	3557	1079
Specificity	0.15	0.08	0.25	0.55	0.05	0.61
c = 5
Consistent	19	183	406	359	456	493
Annotated	112	1621	1955	600	2293	763
Specificity	0.17	0.11	0.21	0.60	0.20	0.65
c ≥ 2
Specificity	0.32	0.14	0.29	0.48	0.09	0.71
COI	188	480	553	1311	168	1668
COI/CI	0.13	0.04	0.21	0.41	0.09	0.59
MNE	2.19	2.44	2.39	1.95	2.34	1.93
Sensitivity	0.46	0.36	0.22	0.31	0.35	0.51

Note that for MNE, the smaller the better, while for the other measures, the larger the better.

CI, conserved interactions; COI, conserved orthologous interactions; MNE, mean normalized entropy.

These results suggest that ConvexAlign finds more functionally consistent clusters, not only by generating small clusters (i.e., c = 2, 3) but also more important large clusters (i.e., c = 4, 5). These clusters (especially when c = 4, 5) are very valuable because they may provide useful information about the orthology relationship among the proteins, identifying conserved subnetworks and predicting the function of unannotated proteins. In the sixth multirow, the bottom row shows the ratio of COI to the number of conserved interactions. ConvexAlign yields a COI/CI around 60% (i.e., 1.44 times larger than the second best ratio by BEAMS), indicating that ConvexAlign is able to identify conserved interactions between orthologous proteins. It also suggests that although SMETANA has the largest RCI, many of those conserved interactions are possibly formed by nonorthologous proteins. ConvexAlign also outperforms other methods in terms of MNE and sensitivity.

Table 3 shows the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overline {AFS}$$ \end{document} separately for clusters composed of proteins in three, four, and five species in both categories BP and MF. The \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overline {AFS}$$ \end{document} obtained by ConvexAlign is 6%–20% larger than the other methods, indicating that on average the clusters generated by ConvexAlign are functionally more consistent. That is, ConvexAlign outperforms the other methods in terms of not only the number of consistent clusters but also the average GO semantic similarity. The distribution of AFS scores that is shown in Supplementary Figure S1 further confirms that ConvexAlign yields clusters with higher functional similarity in both categories, MF and BP.

Table 3.

	IsoRankN (0.5)	SMETANA	NetCoffee	BEAMS (0.5)	FUSE	ConvexAlign
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \overline {AFS} _{BP}}$$ \end{document}
c = 3	1.02	0.74	1.03	1.63	0.23	1.74
c = 4	0.97	0.68	0.99	1.61	0.63	1.79
c = 5	1.01	0.85	1.16	1.67	1.09	1.71
\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \overline {AFS} _{MF}}$$ \end{document}
c = 3	0.94	0.69	0.99	1.33	0.27	1.54
c = 4	1.02	0.74	1.03	1.63	0.67	1.74
c = 5	1.06	0.94	1.18	1.68	1.08	1.74

We also apply ConvexAlign without using f_edge (i.e., λ₂ = 0) to show how edge preserving will improve the alignment accuracy. When λ₂ = 0, the specificity is equal to 0.29 when c = 2 and is less than 0.50 when c = 3, 4, 5. Moreover, RCI = 0.01 and COI/CI = 0.16. These results indicate that preserving the edges may cause the nodes in dense subnetworks to align with each other. Thus, by applying f_edge, ConvexAlign may align the similar modules together resulting in a more functionally meaningful alignment.

3.2. Alignment quality on synthetic data

Figure 1 shows the number of consistent clusters generated by different methods and their specificity on clusters composed of proteins in c = 2, 3, 4, 5, 6, 7, 8 species, respectively. In terms of the number of consistent clusters, ConvexAlign is slightly better than the second best method BEAMS regardless of c, but much better than the others. In terms of specificity, ConvexAlign has a much larger advantage over the other methods when c = 4, 5, 6, 7, 8. Fuse finds none or a few (1 or 2) consistent clusters when c = 3, 4, 5, 6. These results indicate that ConvexAlign aligns proteins in a functionally consistent way, without generating too many spurious clusters in which the proteins appear to be unrelated. Supplementary Figures S2 and S3 show that ConvexAlign outperforms all the other methods in terms of MNE, COI, and RCI.

FIG. 1.

Specificity and the number of consistent clusters generated by the competing methods for different c on synthetic data. Only the best performance for IsoRankN and BEAMS is shown.

3.3. Finding conserved subnetworks

One of the applications of network alignment is to reveal subnetworks conserved across the species. These subnetworks are helpful for extracting biological information that cannot be inferred from sequence similarity alone. Figure 2 shows one conserved complex detected by ConvexAlign among the five species, but not appearing in the alignments generated by other methods. This complex is enriched for proteasome (with p-value< 10⁻⁷), which is essential for the degradation of most proteins, including misfolded or damaged proteins.

FIG. 2.

The ConvexAlign-detected proteasome complex in each input PPI network. PPI, protein–protein interaction.

In Figure 2, the interactions in IntAct are displayed in solid lines. For fly, mouse, and worm, some edges (shown by dotted lines) are missing in IntAct but present in the STRING database (Szklarczyk et al., 2011) with experimental evidence at the highest confidence. Note that our input networks consist of interactions only from IntAct but not STRING. This suggests that ConvexAlign is able to predict missing interactions. PANTHER (Mi et al., 2010) suggests that most of the aligned proteins are least divergent orthologs (Supplementary Table S3). There are some missing proteins from different species in some of the clusters. This is because either there are no orthologs in those species or there is no alignment for them. For example, cluster 5 has no proteins from worm and fly. PANTHER could not find any orthologous protein in those species either. Cluster 6 misses orthologous proteins in fly and yeast, which are aligned by ConvexAlign to proteins not in this proteasome complex. In addition, this proteasome complex has different number of nodes in different species, which implies that ConvexAlign is able to deal with inserted and deleted nodes.

Figure 3 shows another conserved subnetwork detected only by ConvexAlign that is related to DNA replication (with p-value<6⁻¹⁰). PANTHER suggests that the aligned proteins are orthologous and functionally related (Supplementary Table S4). It is worth mentioning that none of the abovementioned clusters appears in the alignment generated when λ₂ = 0, indicating that edge preserving improves finding common functional/structural modules in the networks.

FIG. 3.

The ConvexAlign-detected DNA replication complex in each input PPI network.

3.4. Running time

ConvexAlign is computationally efficient compared to the other methods. Tested on the alignment of the networks of five species, it takes ConvexAlign, IsoRankN, BEMAS, FUSE, NetCoffee, and SMETANA 480, 1129, 900, 780, 15, and 37 minutes, respectively, to terminate. Although NetCofee has the smallest running time, it does not yield alignments with significant functional consistency.

4. Discussion

This article presents a new method, ConvexAlign, for global alignment of multiple PPI networks. ConvexAlign describes a new scoring function that integrates sequence and topological similarity between the matched proteins and interaction consistency. ConvexAlign uses a novel convex formulation to simultaneously align all the proteins in multiple input networks, resulting in better alignment quality. Such a formulation allows us to use an alternating direction method of multipliers (ADMM) method to find its optimal solution. We have tested ConvexAlign on real PPI networks, and the synthetic data evaluated the output alignments by different performance metrics and compared it to state-of-the-art methods. Experimental results show that on average ConvexAlign generates more functionally consistent clusters consisting of proteins from most of the input species. That is, ConvexAlign can explain a larger amount of data in a more functionally meaningful way. ConvexAlign can also find a few conserved and biologically important complexes that cannot be detected by the other alignment methods.

Footnotes

Author Disclosure Statement

No competing financial interests exist.

References

ConvexAlign source code available freely for noncommercial purposes at https://github.com/hashemifar/ConvexAlign

Alkan

, and Erten

2014. BEAMS: Backbone extraction and merge strategy for the global many-to-many alignment of multiple PPI networks. Bioinformatics, 30, 531–539.

Ciriello

, Mina

, Guzzi

P.H.

, et al. 2012. AlignNemo: A local network alignment method to integrate homology and topology. PLoS One, 7, e38107–e38107.

Flannick

, Novak

, Do

C.B.

, et al. 2008. Automatic parameter learning for multiple network alignment. J. Comput. Biol., 16, 214–231.

Gligorijević

, Malod-Dognin

, and Pržulj

2015. FUSE: Multiple network alignment via data fusion. Bioinformatics DOI: 10.1093/bioinformatics/btv731.

Hashemifar

, and Xu

2014. HubAlign: An accurate and efficient method for global alignment of protein–protein interaction networks. Bioinformatics, 30.17, i438–i444.

, Kehr

, and Reinert

2014. NetCoffee: A fast and accurate global alignment approach to identify functionally conserved proteins in multiple networks. Bioinformatics, 30, 540–548.

Huang

, and Guibas

2013. Consistent shape maps via semidefinite programming. Comput. Graph. Forum, 32, 177–186.

Huang

, Koltun

, and Guibas

2011. Joint shape segmentation with linear programming. ACM Trans. Graph., 30, 125:1–125:12.

10.

Kalaev

, Smoot

, Ideker

, et al. 2008. NetworkBLAST: Comparative analysis of protein networks. Bioinformatics, 24, 594–596.

11.

Kerrien

, Aranda

, Breuza

, et al. 2011. The IntAct molecular interaction database in 2012. Nucleic Acids Res. 40, D841–D846.

12.

Kim

W.K.

, and Marcotte

E.M.

2008. Age-dependent evolution of the yeast protein interaction network suggests a limited role of gene duplication and divergence. PLoS Comput. Biol., 4, e1000232.

13.

Koyutürk

, Kim

, Topkara

, et al. 2006. Pairwise alignment of protein interaction networks. J. Comp. Biol., 13, 182–199.

14.

Kuchaiev

, and Pržulj

2011. Integrative network alignment reveals large regions of global network similarity in yeast and human. Bioinformatics, 27, 1390–1396.

15.

Kumar

M.P.

, Kolmogorov

, and Torr

P.H.S.

2008. An analysis of convex relaxations for MAP estimation of discrete MRFs. J. Mach. Learn. Res., 10, 71–106.

16.

Liao

C.S.

, Lu

, Baym

, et al. 2009. IsoRankN: Spectral methods for global alignment of multiple protein networks. Bioinformatics, 25, i253–i258.

17.

, Dong

, Muruganujan

, et al. 2010. PANTHER version 7: Improved phylogenetic trees, orthologs and collaboration with the Gene Ontology Consortium. Nucleic Acids Res. 38(Suppl 1), D204–D210.

18.

Neyshabur

, Khadem

, Hashemifar

, et al. 2013. NETAL: A new graph-based method for global alignment of protein–protein interaction networks. Bioinformatics, 29, 1654–1662.

19.

Patro

, and Kingsford

2012. Global network alignment using multiscale spectral signatures. Bioinformatics, 28, 3105–3114.

20.

Sahraeian

S.M.E.

, and Yoon

B.-J.

2012. A network synthesis model for generating protein interaction network families. PLoS One, 7, e41474.

21.

Sahraeian

S.M.E.

, and Yoon

B.-J.

2013. SMETANA: Accurate and scalable algorithm for probabilistic alignment of large-scale biological networks. PLoS One, 8, e67995.

22.

Saraph

, and Milenković

2014. Magna: Maximizing accuracy in global network alignment. Bioinformatics, 30, 2931–2940.

23.

Sharan

, Suthram

, Kelley

R.M.

, et al. 2005. Conserved patterns of protein interaction in multiple species. Proc. Natl. Acad. Sci. U.S.A., 102, 1974–1979.

24.

Singh

, Xu

, and Berger

2007. Pairwise global alignment of protein interaction networks by matching neighborhood topology. RECOMB’07 Proceedings of the 11th Annual International Conference on Research in Computational Molecular Biology. Springer, Berlin, Heidelberg, pp. 16–31.

25.

Singh

, Xu

, and Berger

2008. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proc. Natl. Acad. Sci. U.S.A., 105, 12763–12768.

26.

Solé

R.V.

, Pastor-Satorras

, Smith

, et al. 2002. A model of large-scale proteome evolution. Adv. Complex Syst., 5, 43–54.

27.

Szklarczyk

, Franceschini

, Kuhn

, et al. 2011. The STRING database in 2011: functional interaction networks of proteins, globally integrated and scored. Nucleic Acids Res. 39(Suppl 1), D561–D568.

28.

Todor

, Dobra

, and Kahveci

2013. Probabilistic biological network alignment. IEEE/ACM Trans. Comput. Biol. Bioinf., 10, 109–121.

29.

Vázquez

, Flammini

, Maritan

, et al. 2003. Modeling of protein interaction networks. Complexus, 1, 38–44.

30.

Vijayan

, Saraph

, and Milenković

2015. MAGNA++: Maximizing Accuracy in Global Network Alignment via both node and edge conservation. Bioinformatics, 31, 2409–2411.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.66 MB