  Learning the structure of dependencies among multiple random variables is a
problem of considerable theoretical and practical interest. Within the context
of Bayesian Networks, a practical and surprisingly successful solution to this
learning problem is achieved by adopting score-functions optimisation schema,
augmented with multiple restarts to avoid local optima. Yet, the conditions
under which such strategies work well are poorly understood, and there are also
some intrinsic limitations to learning the directionality of the interaction
among the variables. Following an early intuition of Friedman and Koller, we
propose to decouple the learning problem into two steps: first, we identify a
partial ordering among input variables which constrains the structural learning
problem, and then propose an effective bootstrap-based algorithm to simulate
augmented data sets, and select the most important dependencies among the
variables. By using several synthetic data sets, we show that our algorithm
yields better recovery performance than the state of the art, increasing the
chances of identifying a globally-optimal solution to the learning problem, and
solving also well-known identifiability issues that affect the standard
approach. We use our new algorithm to infer statistical dependencies between
cancer driver somatic mutations detected by high-throughput genome sequencing
data of multiple colorectal cancer patients. In this way, we also show how the
proposed methods can shade new insights about cancer initiation, and
progression. Code: https://github.com/caravagn/Bootstrap-based-Learning
