
Home Education Publications Hypercubes Miscellaneous	An Algebraic Algorithm for the Identification of Glass Networks with Periodic Orbits along Cyclic Attractors AUTHOR(S) Igor Zinovik, Daniel Kroening, and Yury Chebiryak PUBLISHER Proceedings of Algebraic Biology Conference, Lecture Notes in Computer Science vol. 4545, Springer Berlin / Heidelberg, pp. 140-154, 2007. LINKS PDF download Digital Object Identifier (DOI): 10.1007/978-3-540-73433-8_11 - an extended version of this paper is available as technical report 557, ETH Zurich Bibtex @inproceedings{zkc2007-ab, AUTHOR = { Zinovik, Igor and Kroening, Daniel and Chebiryak, Yury }, TITLE = { An Algebraic Algorithm for the Identification of {Glass} Networks with Periodic Orbits along Cyclic Attractors }, BOOKTITLE = { Proceedings of Algebraic Biology (AB) }, YEAR = { 2007 }, PUBLISHER = { Springer }, DOI = {10.1007/978-3-540-73433-8_11}, PAGES = { 140--154 }, SERIES = { Lecture Notes in Computer Science }, VOLUME = { 4545 }, } ABSTRACT Glass piecewise linear ODE models are frequently used for simulation of neural and gene regulatory networks. Efficient computational tools for automatic synthesis of such models are highly desirable. However, the existing algorithms for the identification of desired models are limited to four-dimensional networks, and rely on numerical solutions of eigenvalue problems. We suggest a novel algebraic criterion to detect the type of the phase flow along network cyclic attractors that is based on a corollary of the Perron-Frobenius theorem. We show an application of the criterion to the analysis of bifurcations in the networks. We propose to encode the identification of models with periodic orbits along cyclic attractors as a propositional formula, and solving it using state-of-the-art SAT-based tools for real linear arithmetic. New lower bounds for the number of equivalence classes are calculated for cyclic attractors in six-dimensional networks. Experimental results indicate that the run-time of our algorithm increases slower than the size of the search space of the problem. This research is supported in part by an award from IBM Research and by ETH Research Grant TH-19 06-3.

Home Education Publications Hypercubes Miscellaneous

An Algebraic Algorithm for the Identification of
Glass Networks with Periodic Orbits along Cyclic Attractors

AUTHOR(S)

Igor Zinovik, Daniel Kroening, and Yury Chebiryak

PUBLISHER

Proceedings of Algebraic Biology Conference, Lecture Notes in Computer Science vol. 4545, Springer Berlin / Heidelberg, pp. 140-154, 2007.

LINKS

PDF download
Digital Object Identifier (DOI): 10.1007/978-3-540-73433-8_11
- an extended version of this paper is available as technical report 557, ETH Zurich

Bibtex

@inproceedings{zkc2007-ab,
AUTHOR = { Zinovik, Igor
and Kroening, Daniel
and Chebiryak, Yury },
TITLE = { An Algebraic Algorithm for the Identification of {Glass} Networks with Periodic Orbits along Cyclic Attractors },
BOOKTITLE = { Proceedings of Algebraic Biology (AB) },
YEAR = { 2007 },
PUBLISHER = { Springer },
DOI = {10.1007/978-3-540-73433-8_11},
PAGES = { 140--154 },
SERIES = { Lecture Notes in Computer Science },
VOLUME = { 4545 },
}

ABSTRACT

Glass piecewise linear ODE models are frequently used for simulation of neural and gene regulatory networks. Efficient computational tools for automatic synthesis of such models are highly desirable. However, the existing algorithms for the identification of desired models are limited to four-dimensional networks, and rely on numerical solutions of eigenvalue problems. We suggest a novel algebraic criterion to detect the type of the phase flow along network cyclic attractors that is based on a corollary of the Perron-Frobenius theorem. We show an application of the criterion to the analysis of bifurcations in the networks. We propose to encode the identification of models with periodic orbits along cyclic attractors as a propositional formula, and solving it using state-of-the-art SAT-based tools for real linear arithmetic. New lower bounds for the number of equivalence classes are calculated for cyclic attractors in six-dimensional networks. Experimental results indicate that the run-time of our algorithm increases slower than the size of the search space of the problem.

This research is supported in part by an award from IBM Research and by ETH Research Grant TH-19 06-3.

An Algebraic Algorithm for the Identification of Glass Networks with Periodic Orbits along Cyclic Attractors