title: 3off2: A network reconstruction algorithm based on 2-point and 3-point information statistics.
abstract: BACKGROUND
  The reconstruction of reliable graphical models from observational data is important in bioinformatics and other computational fields applying network reconstruction methods to large, yet finite datasets. The main network reconstruction approaches are either based on Bayesian scores, which enable the ranking of alternative Bayesian networks, or rely on the identification of structural independencies, which correspond to missing edges in the underlying network. Bayesian inference methods typically require heuristic search strategies, such as hill-climbing algorithms, to sample the super-exponential space of possible networks. By contrast, constraint-based methods, such as the PC and IC algorithms, are expected to run in polynomial time on sparse underlying graphs, provided that a correct list of conditional independencies is available. Yet, in practice, conditional independencies need to be ascertained from the available observational data, based on adjustable statistical significance levels, and are not robust to sampling noise from finite datasets.
  
  
  RESULTS
  We propose a more robust approach to reconstruct graphical models from finite datasets. It combines constraint-based and Bayesian approaches to infer structural independencies based on the ranking of their most likely contributing nodes. In a nutshell, this local optimization scheme and corresponding 3off2 algorithm iteratively "take off" the most likely conditional 3-point information from the 2-point (mutual) information between each pair of nodes. Conditional independencies are thus derived by progressively collecting the most significant indirect contributions to all pairwise mutual information. The resulting network skeleton is then partially directed by orienting and propagating edge directions, based on the sign and magnitude of the conditional 3-point information of unshielded triples. The approach is shown to outperform both constraint-based and Bayesian inference methods on a range of benchmark networks. The 3off2 approach is then applied to the reconstruction of the hematopoiesis regulation network based on recent single cell expression data and is found to retrieve more experimentally ascertained regulations between transcription factors than with other available methods.
  
  
  CONCLUSIONS
  The novel information-theoretic approach and corresponding 3off2 algorithm combine constraint-based and Bayesian inference methods to reliably reconstruct graphical models, despite inherent sampling noise in finite datasets. In particular, experimentally verified interactions as well as novel predicted regulations are established on the hematopoiesis regulatory networks based on single cell expression data.
authors.affiliation: Institut Curie, PSL Research University, CNRS, UMR168, 26 rue d'Ulm, Paris, 75005, France.|Sorbonne Universités, UPMC Univ Paris 06, 4, Place Jussieu, Paris, 75005, France.
authors.forename: Séverine
authors.initials: S
authors.lastname: Affeldt
authors.affiliation: Institut Curie, PSL Research University, CNRS, UMR168, 26 rue d'Ulm, Paris, 75005, France.|Sorbonne Universités, UPMC Univ Paris 06, 4, Place Jussieu, Paris, 75005, France.
authors.forename: Louis
authors.initials: L
authors.lastname: Verny
authors.affiliation: Institut Curie, PSL Research University, CNRS, UMR168, 26 rue d'Ulm, Paris, 75005, France. herve.isambert@curie.fr.|Sorbonne Universités, UPMC Univ Paris 06, 4, Place Jussieu, Paris, 75005, France. herve.isambert@curie.fr.
authors.forename: Hervé
authors.initials: H
authors.lastname: Isambert
mesh_terms: D000465:Algorithms; D000818:Animals; D001499:Bayes Theorem; D019295:Computational Biology / Q000379:methods; D020869:Gene Expression Profiling; D053263:Gene Regulatory Networks; D006410:Hematopoiesis; D051379:Mice; D008957:Models, Genetic; D059010:Single-Cell Analysis
references.citation: Immunity. 2009 Oct 16;31(4):576-86
references.pmid: 19818654
references.citation: Mol Syst Biol. 2007;3:78
references.pmid: 17299415
references.citation: Stem Cells. 2013 May;31(5):882-94
references.pmid: 23378057
references.citation: BMC Bioinformatics. 2008 Oct 29;9:461
references.pmid: 18959772
references.citation: Nat Immunol. 2011 Feb;12(2):129-36
references.pmid: 21186366
references.citation: Science. 2005 Apr 22;308(5721):523-9
references.pmid: 15845847
references.citation: Cell. 2009 Apr 3;137(1):172-81
references.pmid: 19327819
references.citation: Blood. 2007 Mar 1;109(5):1908-16
references.pmid: 17053063
references.citation: Nat Cell Biol. 2013 Apr;15(4):363-72
references.pmid: 23524953
references.citation: EMBO J. 2002 Jun 17;21(12):3039-50
references.pmid: 12065417
references.citation: Oncogene. 2010 Oct 28;29(43):5796-808
references.pmid: 20676125
references.citation: Nat Immunol. 2012 Jul 08;13(8):761-9
references.pmid: 22772404
references.citation: PLoS One. 2013;8(1):e53666
references.pmid: 23308270
references.citation: BMC Bioinformatics. 2006 Mar 20;7 Suppl 1:S7
references.pmid: 16723010