PBNA: An Improved Probabilistic Biological Network Alignment Method

Now we generalize the alignment problem into the situation where $G_1$ is deterministic while $G_2$ is probabilistic. A main challenge of probabilistic network alignment is to compute R. This is because that the nature of probabilistic network makes it almost impossible to choose one specific deterministic network and the corresponding A of it from all possible alternatives. There are $2^{|E_2|}$ alternative matrices. We solve this problem using an approach proposed in Prob^{[ 4 ]}: All of these matrices are modeled with a matrix of random variables and A is replaced with its expected value, $E(\text{𝑨})$ . Now the question is how to compute $E(\text{𝑨})$ ?

The degree of every node, namely $d_v$ , is obviously probabilistic in probabilistic networks. $d_v$ can be any value in the sequence $0,\mathrm{\cdots },d_v^{\max }(d_v^{\max }$ is the largest possible degree of node $v)$ . Let a discrete random variable $D_v$ model the degree of node $v$ . Then $P(D_v=k),k=0,1,\mathrm{\cdots },d_v^{\max }$ is the sequence of degree distribution of node $v$ in probabilistic network $G_2$ .

Algorithm 1 Computing $\text{𝐸}\mathbf{}\mathrm{(}\text{𝐴}\mathrm{)}$ according to Eq. ( 8 ).

A is now a random matrix with entries that depend on $D_v$ , and Eq. ( 5 ) is converted into Eq. ( 6 ) as the following form:

(6) $$A[i,j][u,v]=\{\begin{array}{cc}\frac{1}{d_u{D}_v},\hfill & \text{if}(u,v)\in C;\hfill \\ \frac{1}{mn},\hfill & \text{if}{d}_u{D}_v=0\text{OR}\hfill \\ & \left((i,u)\in E_1,(j,v)\in E_2\right);\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$

In order to compute the expectation of A described in Eq. ( 6 ), we focus on its one specific entry $A[i,j][u,v]$ . Note that the related information of node $u$ is deterministic as it is from $G_1$ . $d_u$ is deterministic, and whether $(u,v)$ is included in $C$ of $(i,j)$ is also deterministic (see Algorithm 1). According to Eq. ( 6 ), if node $u$ is isolated, namely $d_u=0$ , $A$ $[i,j][u,v]$ is a constant, ${\displaystyle \frac{1}{mn}}$ ; if $u$ is not isolated and $(i,u)\notin E_1$ , $A[i,j][u,v]$ is constant, 0; if $(u,v)\notin C$ , $A[i,j][u,v]$ is also constant, ${\displaystyle \frac{1}{mn}}$ . For the remaining cases, $A[i,j][u,v]$ is a random variable whose expectation needs to be computed. The definition of expectation of a discrete random variable is

(7) $$E\left[A[i,j][u,v]\right]=$$ $$\underset{k}{\sum }kP(A[i,j][u,v]=k)$$

The possible values of $A[i,j][u,v],$ denoted with $k$ , can be $0$ , ${\displaystyle \frac{1}{mn}}$ , or ${\displaystyle \frac{1}{d_u{D}_v}}$ according to Eq. ( 6 ). From the above discussion, we know that the prerequisite for $A[i,j][u,v]$ being a random variable is that $(u,v)\in C$ . Therefore, node $v$ has no possibility being an isolated node. According to Eq. ( 6 ), $A[i,j][u,v]$ can only be ${\displaystyle \frac{1}{d_u{D}_v}}$ . Moreover, $(u,v)\in C$ leads to $(j,v)\in E_2$ . And if the probabilistic edge $(j,v)$ is guaranteed to appear in $E_2$ , it implies that $j$ and $v$ are neighbors. The degree of $v$ is at least 1. Thus, the probability distribution of the random variable $D_v$ should take this prior information into consideration. In mathematical way, this can be expressed as a conditional probability $p(D_v=$ $k|(j,v)\in E_2)$ , for $k=1,\mathrm{\cdots },d_v^{\text{max}}$ . Finally, the expectation of matrix A can be computed as following:

(8) $$E\left[A[i,j][u,v]\right]=$$ $$\{\begin{array}{c}\frac{1}{d_u}\times \underset{k=1}{\overset{d_v^{\max }}{\sum }}\frac{1}{k}P(D_v=k|(j,v)\in E_2),\hfill \\ \mathrm{if}(u,v)\in C;\hfill \\ \frac{1}{mn},\text{if}{d}_u=0\text{OR}(u,v)\notin C;\hfill \\ 0,\text{otherwise}\hfill \end{array}$$

The main technical difficulty in Eq. ( 8 ) is how to compute the conditional degree distribution $P(N_v=k|(j,v)\in E_2)$ .

Definition 1^{[ 4 ]} Let $X$ be a discrete random variable taking integer values from $0$ to $N$ . The PGF of $X$ is defined as the polynomial of $z$ :

(9) $$Q_X\left(z\right)=E[z^X]=\underset{k=0}{\overset{N}{\sum }}P(X=k)z^k$$

Example 1 Let $X$ be a discrete random variable taking values from $\{0,1,2\}$ . The probability distribution is $\{0.09,0.45,0.7\}$ . The PGF of $X$ is the polynomial $Q_X\left(z\right)=0.09+0.45z+0.7z^2$ .

Thus, we know that by simply listing the coefficients of PGF, the distribution of $X$ will be obtained. And the following Theorem 1 can be used to compute PGF of $D_v$ .

Theorem 1^{[ 4 ]} Let $G=(V,E,P)$ be a probabilistic network and $E_v$ be the set of edges incident on node $v$ . The PGF of the degree distribution of $v$ is

(10) $$Q_{D_v}\left(z\right)=\underset{e\in E_v}{\prod }\left(1-p_e+p_{e}z\right)$$

Example 2 In Fig. 1 , the PGF of the distribution for node $b$ is the multiplication of the polynomials corresponding to each incident edge: $\left(0.85+0.15z\right)\left(0.5+0.5z\right)=0.425+0.5z+0.075z^2$ . The degree distribution of $a$ is $P(N_b=0)=0.425$ , $P(N_b=1)=0.5$ , $P(N_b=2)=0.075$ .

Thus, the degree distribution of node $v$ can be computed by the PGF of $D_v$ conveniently. The time complexity of the entire process then decreases from $O(2^{d_v^{\max }})$ (exhaustive method) to $O({(d_v^{\max })}^2)$ ^{[ 4 ]}.

Note that our goal in Eq. ( 8 ) is to compute the conditional degree distribution $P(D_v=k|(j,v)\in$ $E_2)$ . In fact, the condition that a particular edge $e$ is present can be expressed by dividing the PGF of $D_v$ by $(1-p_e+p_{e}z)$ , which is the PGF of $D_v$ if edge $e$ is the only edge incident on node $v$ . The result of the division produces the PGF of $D_v^{\prime }$ , which is the degree of node $v$ without considering the edge $e$ at all. Finally, by shifting the distribution of $D_v^{\prime }$ by one position, we get the conditional degree distribution $P(D_v=k|e\in E_v)=P(D_v^{\prime }=k-1)$ . The intuitive explanation of this dividing-and-shifting procedure is that the probability of the degree of node $v$ being $k$ under the condition that edge $e$ is already present equals to the probability of the degree of node $v$ being $k-1$ under the condition that node $v$ doesn’t have edge $e$ at all.

The pseudo code for computing $E(\text{𝑨})$ according to Eq. ( 8 ) is shown in Algorithm 1.

Algorithm 1 demonstrates how to compute $E(\text{𝑨})$ in three major steps:

(1) Lines 1-3: construct the PGF for every node in probabilistic network $G_2$ ;

(2) Lines 4-6: for every possible pair $(u,v)$ where $u\in V_1$ and $v\in V_2$ , compute its initial similarity score for finding the set of Contributor according to Line 5;

(3) Line 7 to end: for every entry of A, compute its similarity score according to three rules in Eq. ( 8 ): Lines 8-14 are for the first rule; Lines 15-17 are for the second rule; and Lines 18-20 are for the third.