Abstract: This study presents two enhanced learning algorithms used for discovering probabilistic graphical models based on the Bayesian Network (BN) structure. The two heuristic structure learning algorithms, namely Tabu Search (TS) and Simulated Annealing (SA), were empirically evaluated and compared regarding efficiency. These algorithms were applied to real-life data sets for the vertebral column. A data set containing values for six biomechanical features was used to classify patients into three categories, namely, Disk Hernia (DH), Spondylolisthesis (SL), and Normal (NO), and two categories, namely, Abnormal (AB) and NO. The results indicated that SA is a more effective algorithm than TS. However, the empirical results obtained using TS indicated that the TS algorithm is promising because of its relatively simple network structure.