dorsal/arxiv
View SchemaDetection of the dominant direction of information flow in densely interconnected regulatory networks
| Authors | I. Ispolatov, Sergei Maslov |
|---|---|
| Categories | |
| ArXiv ID | q-bio/0702057 |
| URL | https://arxiv.org/abs/q-bio/0702057 |
| Journal | BMC Bioinformatics 2008, 9:424. |
Abstract
Finding the dominant direction of flow of information in densely interconnected regulatory or signaling networks is required in many applications in computational biology and neuroscience. This is achieved by first identifying and removing links which close up feedback loops in the original network and hierarchically arranging nodes in the remaining network. In mathematical language this corresponds to a problem of making a graph acyclic by removing as few links as possible and thus altering the original graph in the least possible way. Practically in all applications the exact solution of this problem requires an enumeration of all combinations of removed links, which is computationally intractable. We introduce and compare two algorithms: the deterministic, 'greedy' algorithm that preferentially cuts the links that participate in the largest number of feedback cycles, and the probabilistic one based on a simulated annealing of a hierarchical layout of the network which minimizes the number of ``backward'' links going from lower to higher hierarchical levels. We find that the annealing algorithm outperforms the deterministic one in terms of speed, memory requirement, and the actual number of removed links. Implications for system biology and directions for further research are discussed.
{
"annotation_id": "42e75241-b841-4205-9c6f-7bb50c1af459",
"date_created": "2026-03-02T18:01:35.441000Z",
"date_modified": "2026-03-02T18:01:35.441000Z",
"file_hash": "b61375a9df34ae3b80278fc37cd98acffd5a1dcaed9c19d2138c07f60fddf00a",
"private": false,
"record": {
"abstract": "Finding the dominant direction of flow of information in densely\ninterconnected regulatory or signaling networks is required in many\napplications in computational biology and neuroscience. This is achieved by\nfirst identifying and removing links which close up feedback loops in the\noriginal network and hierarchically arranging nodes in the remaining network.\nIn mathematical language this corresponds to a problem of making a graph\nacyclic by removing as few links as possible and thus altering the original\ngraph in the least possible way. Practically in all applications the exact\nsolution of this problem requires an enumeration of all combinations of removed\nlinks, which is computationally intractable. We introduce and compare two\nalgorithms: the deterministic, \u0027greedy\u0027 algorithm that preferentially cuts the\nlinks that participate in the largest number of feedback cycles, and the\nprobabilistic one based on a simulated annealing of a hierarchical layout of\nthe network which minimizes the number of ``backward\u0027\u0027 links going from lower\nto higher hierarchical levels. We find that the annealing algorithm outperforms\nthe deterministic one in terms of speed, memory requirement, and the actual\nnumber of removed links. Implications for system biology and directions for\nfurther research are discussed.",
"arxiv_id": "q-bio/0702057",
"authors": [
"I. Ispolatov",
"Sergei Maslov"
],
"categories": [
"q-bio.MN",
"cond-mat.dis-nn"
],
"journal_ref": "BMC Bioinformatics 2008, 9:424.",
"title": "Detection of the dominant direction of information flow in densely interconnected regulatory networks",
"url": "https://arxiv.org/abs/q-bio/0702057"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e8b56c07-6254-40e6-b3c3-5b9c292346e8",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}