Network Motif Search

In order to discover network motifs, two data matrices were created. The overall matrix D consists of binary entries Dij, where a 1 indicates binding of regulator j to intergenic region i, a 0 indicates no binding. The regulator matrix R is a subset of D, containing only the rows corresponding to the intergenic region assigned to each regulator, in the same order as the columns of regulators. All analyses were performed in Matlab.

The algorithms used to find each motif are described below.

Autoregulatory motif: Find each non-zero entry on the diagonal of R.

Feedforward loop: For each master regulator (column of R), find non-zero entries, which correspond to regulators bound. For each master regulator / secondary regulator pair, find all rows in D bound by both regulators.

Multi-component loop: For each regulator (column of R), find the regulators to which it binds. For each of these, find the regulators it binds. If any of these are the original regulator, you have a multi-component loop of two. For all others, find regulators to which they bind. If any of these are the original, you have a multi-component loop of three. Repeat to find larger loops.

Single input module: Find the intergenic regions bound by only one regulator. That is, take the subset of rows of D such that the sum of each row is 1. Then for each regulator (column), find non-zero entries. Each set (greater than three promoter regions) is a SIM.

Multi-input module: Find the intergenic regions bound by more than one regulator. That is, take the subset of rows of D such that the sum of each row is greater than 1. Then, for each row, find any other row bound by the same regulators. The collection of rows bound by the same regulators correspond to a MIM. Once a row is assigned to a MIM, remove it from further analysis.

Regulator cascade: For each regulator (column of R), use a recursive algorithm to find chains of all lengths. That is, for each regulator whos promoter is bound by the regulator before it in the chain, find the regulator promoters to which it binds. Repeat until the chain ends. There are three possible ways to end a chain: a regulator that does not bind to the promoter of any other regulator, a regulator that binds to its own promoter, or one that binds to the promoter of another regulator earlier in the chain.