 S, G2, G2/M, M \}
\end{equation}

 \begin{equation} 		   
         B = \{ (x,y) \in A \times A \}
\end{equation}
         
\begin{equation}         
  		N(x) = \{ y \in A / (x,y) \in B \} 
\end{equation}



The idea is based on the fact that, if two consecutive proteins in a candidate pathway are expressed in the same cell cycle phase, which is a self-loop edge in the graph, or if the second protein is expressed in a phase that follows the one of the first protein, then the interaction is more likely to be real. 
As the information extracted from Cyclebase includes two checkpoints, G1/S and G2/M, we use them as a part of the cycle, so that the sequence remains in order. 
We based our method on the information reported by Cyclebase, which already estimates peak gene expression by a probabilistic approach using several gene expression experiments. 

   
\begin{figure}[ht]
 \centering
\includegraphics[scale=1.2]{cyclefig.pdf}
 \caption{Graph representation of a cell cycle $CG(A,B)$.}
 \label{fig2}
\end{figure}

We incorporate temporality in the form of cell cycle phases to check if two consecutive proteins in a candidate pathway are likely to participate in a pathway.
If all proteins forming edges in a candidate pathway satisfy the expected transitions in cell cycle dynamics or protein complex involvement, the \textit{candidate pathway} is a \textit{consistent pathway}.

 We model the cell cycle transition as the function $T$ that maps each protein (seen as a node in $V$) to the set of cell cycle phases (seen as nodes in $A$) where it is expressed. To define $T$, we use information from Cyclebase 3.0 \footnote{www.cyclebase.org}, from where we may use the information on cell cycle peak expression (in which case the resulting function is called $T_{pk}$), or the information on cell cycle phenotype (in which case we call $T_{ph}$ the resulting function). In addition, we consider the protein complex involvement function $L$ to map proteins to protein complexes in which they participate, where $PC$ are predicted or gold standard complexes. 
The procedure that involves functions $T$ and $L$ can be used in any order as they are independent. 


\bigskip

\begin{tabular}{ll}

$T: V \mapsto C \subseteq A$
&
\hspace{1cm}
$L: V \mapsto R \subseteq PC$
\end{tabular}

\bigskip


Then, given $CG(A,B)$ and $\mathcal{P} = \{P_1, P_2, \dots, P_n\}$, we decide whether a candidate pathway $P_i$ is TRUE or FALSE as shown in Algorithm \ref{Alg1}. Consistent pathways are candidate pathways that are TRUE after applying Algorithm \ref{Alg1}.

\bigskip


\begin{algorithm}
\caption{Signaling consistent pathway decision using cell-cycle and protein complex rules.}
\label{Alg1}
\begin{algorithmic}[1]
\REQUIRE Candidate pathway $P \in \mathcal{P}$, functions $T_{pk}$, $T_{ph}$, $L$. 
\ENSURE Returns TRUE (consistent pathway) if a candidate pathway satisfies the cell-cycle dynamics or protein complex rules.
\FOR {$v_i,v_{i+1} \in P$}
\IF {$(|T_{pk}(v_{i+1}) \cap N(T_{pk}(v_{i}))|>0) \vee (|T_{ph}(v_{i+1}) \cap N(T_{pk}(v_{i}))|>0) \vee (|T_{pk}(v_{i+1}) \cap N(T_{ph}(v_{i}))|>0) \vee (|T_{ph}(v_{i+1}) \cap N(T_{ph}(v_{i}))|>0)$}
\STATE continue
\ELSIF {($|L(v_i) \cap L(v_{i+1})|>0$)}
\STATE continue
\ELSE 
\RETURN FALSE
\ENDIF
\ENDFOR
\RETURN TRUE
\end{algorithmic}
\end{algorithm}




The first part of the Algorithm \ref{Alg1} (Cell Cycle rule), lines 2-3, evaluates whether a protein-protein interaction, $(v_{i},v_{i+1})$ is supported by: 
\begin{enumerate}
 \item Peaks of expression: where $v_{i+1}$ peak must be in the next phase of $v_{i}$ peak.
 \item Peaks and phenotypes: where $v_{i+1}$ phenotype must be in the next phase of $v_{i}$.
 \item Phenotypes and peaks: where $v_{i+1}$ peak must be in the next phase of $v_{i}$ phenotype.
 \item Phenotypes: where $v_{i+1}$ phenotype must be in the next phase of $v_{i}$ phenotype.
\end{enumerate}

The next phase in the graph of a protein can be only as indicated in Figure \ref{fig2}, that is, staying in the same one or going to other phases in the Cyclebase cell cycle. In case the cell cycle is not satisfied we verify the complex rule, line 4, that is, our approach verifies if either the cell cycle rule or the complex rule is satisfied. If none of these two rules is satisfied, we discard such interaction (lines 6-7) and, consequently, the candidate pathway.

 The pathways that pass the filter of Algorithm \ref{Alg1} are furthered filtered as follows. Taking advantage of the high relationship between the proteins when they collaborate in a complex, we evaluate all the proteins of each \textit{consistent pathway} to calculate the highest coverage that the complexes have on the pathways. This can be seen in Algorithm \ref{Alg2}, where we  
compute the number of common protein complexes where proteins in a \textit{consistent pathway} participate in (lines 1-3 in Algorithm \ref{Alg2}).
Then, we compute the protein complex coverage $r$ (line 4 in Algorithm \ref{Alg2}) and choose the pathways that are over the threshold given by the coverage ratio $cv$.
This filter is related with the level of cohesion within the pathway, appreciating that certain proteins in it carry out functions together, beyond temporality.


\begin{algorithm}
\caption{Signaling consistent pathway with protein complex coverage.}
\label{Alg2}
\begin{algorithmic}[1]
\REQUIRE Consistent pathway $P_c$ and coverage ratio $cv$. 
\ENSURE Returns TRUE (Predicted pathway) if a consistent pathway satisfies the $cv$.

\FOR {$v_i \in  P_c$}
\STATE $Freq[L(v_i)]++$
\ENDFOR
\STATE $r=max(Freq)/|P_c|$
\IF {$r>=cv$}
\RETURN TRUE
\ELSE 
\RETURN FALSE
\ENDIF

\end{algorithmic}
\end{algorithm}


\subsection{Ranking algorithms}\label{subsec_rankalgs}

A post-processing step of our method ranks consistent pathways according to different criteria. In this section, we describe the main metrics used in such process, which are the edge and path metrics shown in Equation \ref{edgemetrics}. These metrics compute a value for each pathway $P_p$, which is used to rank the pathways in a priority queue.

\begin{equation}\label{edgemetrics}
 Edge\; Weight = \min/\max/Avg\;_{\forall_e \in P_p} w(e) 
\end{equation}
\begin{equation}
 Edge\; Use = \min/\max/Avg\;_{\forall_e \in P_p} Freq(e) 
\end{equation}
\begin{equation}
 Path\; Weigh = \prod_{e \in P_p} w(e)
\end{equation}



The \textit{Edge Weight} returns the minimum, average or maximum weight of an interaction in a pathway. The \textit{Edge Use} is the number of times a certain edge is present in all predicted pathways. It is also considered as in its minimum, maximum, and average values. The \textit{Path Weight} is the multiplication of all the edge weight values, $w(e)$, from a pathway. Path weight is used to break ties when ranking by other metrics.

In preliminary experiments, we also considered vertex centrality metrics such as \textit{degree}, \textit{betweenness} and \textit{closeness}. However, such results are not reported here since edge and path metrics always outperformed vertex metrics in our evaluation.

\section{Evaluation}

This section describes the experimental evaluation performed to compare the proposed method with state of the art methods for discovering signaling pathways. We first