An algorithm for score aggregation over causal biological networks based on random walk sampling

BMC Research Notes

Alain Sewer²  Florian Martin²  Brian P Frushour¹  Ty M Thomson¹  Dmitry M Vasilyev¹ 

[1] Selventa, One Alewife Center, Cambridge, MA 02140, USA;Philip Morris International R&D, Philip Morris Products S.A, Quai Jeanrenaud 5, 2000 Neuchâtel, Switzerland

关键词: Random walk;    Spanning tree;    Signed graph;    Causal consistency;    Causal biological network;   

Others  :  1130560
DOI  :  10.1186/1756-0500-7-516

 received in 2014-03-21, accepted in 2014-07-31,  发布年份 2014

【 摘 要 】

Background

We recently published in BMC Systems Biology an approach for calculating the perturbation amplitudes of causal network models by integrating gene differential expression data. This approach relies on the process of score aggregation, which combines the perturbations at the level of the individual network nodes into a global measure that quantifies the perturbation of the network as a whole. Such "bottom-up" aggregation relates the changes in molecular entities measured by omics technologies to systems-level phenotypes. However, the aggregation method we used is limited to a specific class of causal network models called "causally consistent", which is equivalent to the notion of balance of a signed graph used in graph theory. As a consequence of this limitation, our aggregation method cannot be used in the many relevant cases involving "causally inconsistent" network models such as those containing negative feedbacks.

Findings

In this note, we propose an algorithm called "sampling of spanning trees" (SST) that extends our published aggregation method to causally inconsistent network models by replacing the signed relationships between the network nodes by an appropriate continuous measure. The SST algorithm is based on spanning trees, which are a particular class of subgraphs used in graph theory, and on a sampling procedure leveraging the properties of specific random walks on the graph. This algorithm is applied to several cases of biological interest.

Conclusions

The SST algorithm provides a practical means of aggregating nodal values over causally inconsistent network models based on solid mathematical foundations. We showed its utility in systems biology, where the nodal values can be perturbation amplitudes of protein activities or gene differential expressions, while the networks can be models of cellular signaling or expression regulation. Since the SST algorithm is based on general graph-theoretical considerations, it is scalable to arbitrary graph sizes and can potentially be used for performing quantitative analyses in any context involving signed graphs.

【 授权许可】

   
2014 Vasilyev et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

【 参考文献 】

• [1]Martin F, Thomson TM, Sewer A, Drubin DA, Mathis C, Weisensee D, Pratt D, Hoeng J, Peitsch MC: Assessment of network perturbation amplitudes by applying high-throughput data to causal biological networks. BMC Syst Biol 2012, 6:54.
• [2]Mitrea C, Taghavi Z, Bokanizad B, Hanoudi S, Tagett R, Donato M, Voichita C, Draghici S: Methods and approaches in the topology-based analysis of biological pathways. Front Physiol 2013, 4:278.
• [3]Barabasi AL, Oltvai ZN: Network biology: understanding the cell's functional organization. Nat Rev Genet 2004, 5(2):101-113.
• [4]Bader GD, Cary MP, Sander C: Pathguide: a pathway resource list. Nucleic Acids Res 2006, 34(Database issue):D504-D506.
• [5]Hoeng J, Deehan R, Pratt D, Martin F, Sewer A, Thomson TM, Drubin DA, Waters CA, de Graaf D, Peitsch MC: A network-based approach to quantifying the impact of biologically active substances. Drug Discov Today 2012, 17(9–10):413-418.
• [6]Westra JW, Schlage WK, Frushour BP, Gebel S, Catlett NL, Han W, Eddy SF, Hengstermann A, Matthews AL, Mathis C, Lichtner RB, Poussin C, Talikka M, Veljkovic E, Van Hooser AA, Wong B, Maria MJ, Peitsch MC, Deehan R, Hoeng J: Construction of a computable cell proliferation network focused on non-diseased lung cells. BMC Syst Biol 2011, 5:105.
• [7]Shoval O, Alon U: SnapShot: network motifs. Cell 2010, 143(2):326-e321.
• [8]Tarca AL, Draghici S, Khatri P, Hassan SS, Mittal P, Kim JS, Kim CJ, Kusanovic JP, Romero R: A novel signaling pathway impact analysis. Bioinformatics 2009, 25(1):75-82.
• [9]Kramer A, Green J, Pollard J Jr, Tugendreich S: Causal analysis approaches in ingenuity pathway analysis. Bioinformatics 2014, 30(4):523-530.
• [10]Schlage W, Westra J, Gebel S, Catlett N, Mathis C, Frushour B, Hengstermann A, Van Hooser A, Poussin C, Wong B, Lietz M, Park J, Drubin D, Veljkovic E, Peitsch MC, Hoeng J, Deehan R: A computable cellular stress network model for non-diseased pulmonary and cardiovascular tissue. BMC Syst Biol 2011, 5(1):168.
• [11]Gebel S, Lichtner RB, Frushour BP, Schlage WK, Hoang V, Talikka M, Hengstermann A, Mathis C, Veljkovic E, Peck M, Peitsch MC, Deehan R, Hoeng J, Westra JW: Construction of a computable network model for DNA Damage, autophagy, cell death, and senescence. Bioinform Biol Insights 2013, 7:1-21.
• [12]Westra JW, Schlage WK, Hengstermann A, Gebel S, Mathis C, Thomson T, Wong B, Hoang V, Veljkovic E, Peck M, Lichtner RB, Weisensee D, Talikka M, Deehan R, Hoeng J, Peitsch MC: A modular cell-type focused inflammatory process network model for non-diseased pulmonary tissue. Bioinform Biol Insights 2013, 7:167-192.
• [13]The Biological Expression Language (BEL) [ http://www.openbel.org/ webcite]
• [14]Spanning tree http://en.wikipedia.org/wiki/Spanning_tree webcite
• [15]Aldous DJ: The random walk construction of uniform spanning trees and uniform labelled trees. SIAM J Discret Math 1990, 3(4):450-465.
• [16]Thomson TM, Sewer A, Martin F, Belcastro V, Frushour BP, Gebel S, Park J, Schlage WK, Talikka M, Vasilyev DM, Westra JW, Hoeng J, Peitsch MC: Quantitative assessment of biological impact using transcriptomic data and mechanistic network models. Toxicol Appl Pharmacol 2013, 272(3):863-878.
• [17]Catlett NL, Bargnesi AJ, Ungerer S, Seagaran T, Ladd W, Elliston KO, Pratt D: Reverse causal reasoning: applying qualitative causal knowledge to the interpretation of high-throughput data. BMC Bioinformatics 2013, 14:340.
• [18]Liu ZG: Molecular mechanism of TNF signaling and beyond. Cell Res 2005, 15(1):24-27.
• [19]Gonzalez-Suarez I, Sewer A, Walker P, Mathis C, Ellis S, Woodhouse H, Guedj E, Dulize R, Marescotti D, Acali S, Martin F, Ivanov NV, Hoeng J, Peitsch MC: Systems biology approach for evaluating the biological impact of environmental toxicants in Vitro. Chem Res Toxicol 2014, 27(3):367-376.
• [20]Chindelevitch L, Loh PR, Enayetallah A, Berger B, Ziemek D: Assessing statistical significance in causal graphs. BMC Bioinformatics 2012, 13:35.
• [21]Chindelevitch L, Ziemek D, Enayetallah A, Randhawa R, Sidders B, Brockel C, Huang ES: Causal reasoning on biological networks: interpreting transcriptional changes. Bioinformatics 2012, 28(8):1114-1121.
• [22]Signed graph http://en.wikipedia.org/wiki/Signed_graph webcite
• [23]Harary F: On the notion of balance of a signed graph. Michigan Math J 1953, 2(2):143-146.
• [24]Facchetti G, Iacono G, Altafini C: Computing global structural balance in large-scale signed social networks. Proc Natl Acad Sci U S A 2011, 108(52):20953-20958.
• [25]Belcastro V, Poussin C, Gebel S, Mathis C, Schlage WK, Lichtner RB, Quadt-Humme S, Wagner S, Hoeng J, Peitsch MC: Systematic verification of upstream regulators of a computable cellular proliferation network model on non-diseased lung cells using a dedicated dataset. Bioinform Biol Insights 2013, 7:217-230.