title: An algorithm for score aggregation over causal biological networks based on random walk sampling.
abstract: 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.
  
  
  RESULTS
  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.
authors.forename: Dmitry M
authors.initials: DM
authors.lastname: Vasilyev
authors.forename: Ty M
authors.initials: TM
authors.lastname: Thomson
authors.forename: Brian P
authors.initials: BP
authors.lastname: Frushour
authors.forename: Florian
authors.initials: F
authors.lastname: Martin
authors.affiliation: Philip Morris International R&D, Philip Morris Products S,A, Quai Jeanrenaud 5, 2000 Neuchâtel, Switzerland. Alain.Sewer@pmi.com.
authors.forename: Alain
authors.initials: A
authors.lastname: Sewer
mesh_terms: D000465:Algorithms; D049490:Systems Biology
references.citation: Bioinformatics. 2009 Jan 1;25(1):75-82
references.pmid: 18990722
references.citation: Nucleic Acids Res. 2006 Jan 1;34(Database issue):D504-6
references.pmid: 16381921
references.citation: Bioinformatics. 2014 Feb 15;30(4):523-30
references.pmid: 24336805
references.citation: Bioinform Biol Insights. 2013;7:97-117
references.pmid: 23515068
references.citation: BMC Bioinformatics. 2012 Feb 20;13:35
references.pmid: 22348444
references.citation: Cell Res. 2005 Jan;15(1):24-7
references.pmid: 15686622
references.citation: Proc Natl Acad Sci U S A. 2011 Dec 27;108(52):20953-8
references.pmid: 22167802
references.citation: BMC Bioinformatics. 2013 Nov 23;14:340
references.pmid: 24266983
references.citation: Toxicol Appl Pharmacol. 2013 Nov 1;272(3):863-78
references.pmid: 23933166
references.citation: BMC Syst Biol. 2011 Jul 02;5:105
references.pmid: 21722388
references.citation: Drug Discov Today. 2012 May;17(9-10):413-8
references.pmid: 22155224
references.citation: Nat Rev Genet. 2004 Feb;5(2):101-13
references.pmid: 14735121
references.citation: Chem Res Toxicol. 2014 Mar 17;27(3):367-76
references.pmid: 24428674
references.citation: Bioinform Biol Insights. 2013 Jul 23;7:217-30
references.pmid: 23926424
references.citation: Front Physiol. 2013 Oct 10;4:278
references.pmid: 24133454
references.citation: Bioinformatics. 2012 Apr 15;28(8):1114-21
references.pmid: 22355083
references.citation: Bioinform Biol Insights. 2013 Jun 20;7:167-92
references.pmid: 23843693
references.citation: BMC Syst Biol. 2012 May 31;6:54
references.pmid: 22651900
references.citation: Cell. 2010 Oct 15;143(2):326-e1
references.pmid: 20946989
references.citation: BMC Syst Biol. 2011 Oct 19;5:168
references.pmid: 22011616