2. NCA
In the case when both matrices A and S are unknown, the decomposition problem in Equation (1) admits an infinite number of solutions. Fortunately, prior information is becoming available for many biological systems, e.g., ChIP-on-chip (ChIP-on-chip (also known as ChIP-chip) represents a technology that combines chromatin immunoprecipitation (“ChIP”) with a DNA microarray (“chip”)) data indicate whether a certain gene interacts with a certain TF. This prior information is incorporated within NCA mathematically via the constraint A(I)=0, where I presents the indices of zero elements in the connectivity matrix A, indicating a certain level of connectivity information. NCA requires three identification criteria to ensure a unique solution up to a scalar ambiguity:1 The connectivity matrix A must be full-column rank.2 If a column of A is removed along with all of the rows corresponding to the nonzero entries of the removed column, the remaining matrix must still be full-column rank.3 The TFA matrix S must have full row rank.
To test whether the system meets the above-mentioned first two criteria, matrix A must be first initialized based on the prior knowledge available about connectivity. Specifically, aij is assigned to zero if (i,j)∈I, and it assumes any arbitrary nonzero value otherwise. Once A is initialized, matrix A is tested to see if it presents a full-column rank. Then, we sequentially remove each column of A, as well as the genes connected to the removed TF and test whether the remaining reduced matrix still presents full-column rank. Consider TRNs in Figure 1 as an example. The initialized connectivity matrices for Figure 1a,b are illustrated in Figure 2a,b, respectively. The initialized connectivity matrix in Figure 2a is not identifiable, since the reduced matrix obtained by removing the first column along with the first, third and fifth rows is not full-column rank. This condition violates the second criterion of NCA. The initialized connectivity matrix in Figure 2b, on the other hand, satisfies all three identification criteria. In terms of the third criterion, it cannot be tested a priori, but it implies that the number of TFs must be less than or equal to the number of time points, i.e., M≤K. This rank criterion is verified after S is simulated using NCA [17].
Figure 2  An example of (a) a non-identifiable pattern and (b) an identifiable pattern.   NCA aims to solve the following optimization problem:(2) minA,S ||X−AS||F2,s.t. A(I)=0, where ||·||F denotes the Frobenius norm. NCA employs an alternate least-squares (ALS) approach to iteratively update A and S. At iteration j, given A(j−1), i.e., the value of A at iteration (j−1), the estimate of S(j) is obtained by solving the following least-squares (LS) problem:(3) S(j)=argminS||X−A(j−1)S||F2s.t.  si,j(l)≤si,j≤si,j(u), where the constraint is included to ensure that the elements of S remain in the domain of biologically-sensitive values [17]. The optimization problem Equation (3) can be solved by standard convex optimization tools, such as the interior point method [24]. Once S(j) is obtained, the next step is to update A(j) via the following optimization problem:(4) A(j)=argminA||X−AS(j)||F2s.t.  A(I)=0, ai,j(l)≤ai,j≤ai,j(u), where the constraint ai,j(l)≤ai,j≤ai,j(u) is also used to constrain the domain of A. Particularly, eliminating the zero elements in A removes the connectivity constraint A(I)=0. This leads to a new least-squares problem with a lesser number of variables, which can also be solved using the same method employed to solve Equation (3). If the decrease in the total least-squares error after updating A is above a preset value e, the algorithm keeps running. Otherwise, it stops. A diagram illustrating the operation of the NCA is shown in Figure 3. Simulation results in [17] demonstrate that NCA was successfully applied to the microarray data generated from yeast Saccharomyces cerevisiae, and the activities of various TFs during the cell cycle were reconstructed.
Figure 3  Network component analysis (NCA) algorithm.

3