Fragment assembly methods represent the state of the art in computational protein structure prediction. However, one limitation of these methods, particularly for larger protein structures, is inadequate conformational sampling. This thesis describes studies aimed at uncovering potential causes of ineffective sampling, and the development of methods to try and address these problems.To identify behaviours that might lead to poor conformational sampling, we developed measures to study fragment-based sampling trajectories. Applying these measures to the Rosetta Abinitio and EdaFold methods showed similarities and differences in the ways that these methods make predictions, and pointed to common limitations. In both protocols, structural features such as alpha-helices were more frequently altered during the search, as compared with regions such as loops. Analyses of the fragment libraries used by these methods showed that fragments covering loop regions were less likely to possess native-like structural features, and this likely exacerbated the problems of inadequate sampling in these regions. Inadequate loop sampling leads to poor fold-level exploration within individual runs of methods such as Rosetta, and this necessitates the use of many independent runs.Guided by these findings, we developed new heuristic-based search algorithms. These algorithms were designed to facilitate the exploration of multiple energy basins within runs. Over many runs, the enhanced exploration in our protocols produced decoy sets with larger fractions of native-like solutions as compared to runs of Rosetta. Experiments with different fragment sets indicated that our methods could better translate increased fragment set quality into improvements in predictive accuracy distributions. These improvements depend most strongly on the ability of search algorithms to reliably generate native-like structures using a fragment set. In contrast, inadequate retention of native-like decoys when associated with unfavourable score values appears to be less of an issue.This thesis shows that targeted developments in conformational sampling strategies can improve the accuracy and reliability of predictions. With effective conformational sampling methods, developments in methods for fragment set construction and other areas may more reliably enhance predictive ability.