3off2: A network reconstruction algorithm based on 2-point and 3-point information statistics - Institut Curie Accéder directement au contenu
Article Dans Une Revue BMC Bioinformatics Année : 2016

3off2: A network reconstruction algorithm based on 2-point and 3-point information statistics

Séverine Affeldt
Louis Verny
  • Fonction : Auteur
Hervé Isambert
Connectez-vous pour contacter l'auteur

Résumé

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.
Fichier principal
Vignette du fichier
art_10.1186_s12859-015-0856-x.pdf (1.16 Mo) Télécharger le fichier
Origine : Publication financée par une institution
Loading...

Dates et versions

hal-01260480 , version 1 (22-01-2016)

Licence

Paternité

Identifiants

Citer

Séverine Affeldt, Louis Verny, Hervé Isambert. 3off2: A network reconstruction algorithm based on 2-point and 3-point information statistics. BMC Bioinformatics, 2016, 17 (S2), pp.149-165. ⟨10.1186/s12859-015-0856-x⟩. ⟨hal-01260480⟩
127 Consultations
549 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More