Abstract
MOTIVATION: Inferring microbial interaction networks from microbiome data is a core task of computational ecology. An avenue of research to create reliable inference methods is based on a stylized view of microbiome data, starting from the assumption that the presences and absences of microbiomes, rather than the quantitative abundances, are informative about the underlying interaction network. With this starting point, inference algorithms can be based on the notion of attractors (asymptotic states) in Boolean networks. Boolean network framework offers a computationally efficient method to tackle this problem. However, often existing algorithms operating under a Boolean network assumption, fail to provide networks that can reproduce the complete set of initial attractors (abundance patterns). Therefore, there is a need for network inference algorithms capable of reproducing the initial stable states of the system. RESULTS: We study the change of attractors in Boolean threshold dynamics on signed undirected graphs under small changes in network architecture and show, how to leverage these relationships to enhance network inference algorithms. As an illustration of this algorithmic approach, we analyse microbial abundance patterns from stool samples of humans with inflammatory bowel disease (IBD), with colorectal cancer and from healthy individuals to study differences between the interaction networks of the three conditions. The method reveals strong diversity in IBD interaction networks. The networks are first partially deduced by an earlier inference method called ESABO, then we apply the new algorithm developed here, EDAME, to this result to generate a network that comes nearest to satisfying the original attractors. AVAILABILITY AND IMPLEMENTATION: Implementation code is freely available at https://github.com/Jojo6297/edame.git.