A Constraint Logic Programming Approach to Predicting the Three-Dimensional Yeast Genome

Abstract

In order for all of a cell's genetic information to fit inside its nucleus, the chromosomes must undergo extensive folding and organization. Just like in origami where the same piece of paper folded in different ways allows the paper to take on different forms and potential functions, it is possible that different genomic organizations (or architectures) are related to various nuclear functions. Until recently, it has been impossible to comprehensively investigate this relationship due to the lack of high-resolution and high-throughput techniques for identifying genomic architectures. The recent development of a technique called Hi-C, which is a derivation of chromosome conformation capture, has made it possible to detect the complete set of interactions occurring within (intra-interactions) and between (inter-interactions) chromosomes in the nucleus. Many computational methods have been proposed that use these analytical results to infer the rough three-dimensional (3D) architecture of the genome. However, the genomic architecture also impacts additional types of nuclear interactions and techniques exist that are able to capture and measure these interactions. Unfortunately, it is difficult to incorporate these additional datasets into the existing tools. To overcome this, a novel application of constraint logic programming (CLP) was used to develop a new program for the prediction of the 3D genomic architecture. The unique representation used in this program lends itself well to the future incorporation of additional genomic datasets. This thesis investigates the most efficient way to date to represent and optimally solve the constraint satisfaction problem of the 3D genome. The developed program was used to predict a 3D logical model of the fission yeast genome and the results were visualized using Cytoscape. This model was then biologically validated through literature search which verified that the prediction was able to recapitulate key documented features of the yeast genome. Future work will utilize this tool as a computational framework and extend it to incorporate additional genomic datasets and information into the prediction and visualization of the 3D genomic architecture. The development of the CLP program described here is a step towards a better understanding of the elusive relationship between the 3D structure of the genome and various nuclear functions.