Bayesian networks are widely used to learn and reason about the dependence structure of discrete variables. However, they can only formally encode symmetric conditional independence, which is often too strict to hold in practice. Asymmetry-labeled DAGs have been recently proposed to extend the class of Bayesian networks by relaxing the symmetric assumption of independence and denoting the dependence between the variables of interest. Here, we introduce novel structural learning algorithms for this class of models, which, whilst efficient, allow for a straightforward interpretation of the underlying dependence structure. A comprehensive computational study highlights the efficiency of the algorithms. A real-world data application using data from the Fear of COVID-19 Scale collected in Italy showcases their use in practice.