TY - GEN

T1 - Finding steady states of large scale regulatory networks through partitioning

AU - Ay, Ferhat

AU - Gulsoy, Gunhan

AU - Kahveci, Tamer

PY - 2010/12/1

Y1 - 2010/12/1

N2 - Identifying steady states that characterize the long term outcome of regulatory networks is crucial in understanding important biological processes such as cellular differentiation. Finding all possible steady states of regulatory networks is a computationally intensive task as it suffers from state space explosion problem. Here, we propose a method for finding steady states of large-scale Boolean regulatory networks. Our method exploits scale-freeness and weak connectivity of regulatory networks in order to speed up the steady state search through partitioning. In the trivial case where network has more than one component such that the components are disconnected from each other, steady states of each component are independent of those of the remaining components. When the size of at least one connected component of the network is still prohibitively large, further partitioning is necessary. In this case, we identify weakly dependent components (i.e., two components that have a small number of regulations from one to the other) and calculate the steady states of each such component independently. We then combine these steady states by taking into account the regulations connecting them. We show that this approach is much more efficient than calculating the steady states of the whole network at once when the number of edges connecting them is small. Since regulatory networks often have small in-degrees, this partitioning strategy can be used effectively in order to find their steady states. Our experimental results on real datasets demonstrate that our method leverages steady state identification to very large regulatory networks.

AB - Identifying steady states that characterize the long term outcome of regulatory networks is crucial in understanding important biological processes such as cellular differentiation. Finding all possible steady states of regulatory networks is a computationally intensive task as it suffers from state space explosion problem. Here, we propose a method for finding steady states of large-scale Boolean regulatory networks. Our method exploits scale-freeness and weak connectivity of regulatory networks in order to speed up the steady state search through partitioning. In the trivial case where network has more than one component such that the components are disconnected from each other, steady states of each component are independent of those of the remaining components. When the size of at least one connected component of the network is still prohibitively large, further partitioning is necessary. In this case, we identify weakly dependent components (i.e., two components that have a small number of regulations from one to the other) and calculate the steady states of each such component independently. We then combine these steady states by taking into account the regulations connecting them. We show that this approach is much more efficient than calculating the steady states of the whole network at once when the number of edges connecting them is small. Since regulatory networks often have small in-degrees, this partitioning strategy can be used effectively in order to find their steady states. Our experimental results on real datasets demonstrate that our method leverages steady state identification to very large regulatory networks.

KW - Network partitioning

KW - Regulatory networks

KW - Steady states

UR - http://www.scopus.com/inward/record.url?scp=79952795731&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79952795731&partnerID=8YFLogxK

U2 - 10.1109/GENSIPS.2010.5719669

DO - 10.1109/GENSIPS.2010.5719669

M3 - Conference contribution

AN - SCOPUS:79952795731

SN - 9781612847924

T3 - 2010 IEEE International Workshop on Genomic Signal Processing and Statistics, GENSIPS 2010

BT - 2010 IEEE International Workshop on Genomic Signal Processing and Statistics, GENSIPS 2010

T2 - 2010 IEEE International Workshop on Genomic Signal Processing and Statistics, GENSIPS 2010

Y2 - 10 November 2010 through 12 November 2010

ER -