USING THE PRIZE-COLLECTING STEINER SYSTEM TO DISSECT GENOMIC REGULATORY NETWORKS FROM HETEROGENEOUS DATA

Abstract

The genomic regulatory network (GRN) is a network composed of molecular species and their interactions. The modelling of GRNs helps us better understand many critical cellular mechanisms. However, current GRN approaches have obstacles to be widely applicable: they typically require fixed types of experimental data (e.g. mRNAs), or focus on simple GRN systems (e.g. only Protein-Protein interaction). The Prize-Collecting Steiner Tree (PCST) problem finds a connected subtree of a network in which a sum of costs for edges in the subtree and prizes for vertices not in the subtree is minimised. The Prize-Collecting Steiner Forest (PCSF) problem finds multiple subtrees under similar constraints. PCST and PCSF approaches have been used to infer GRNs, using experimental observations as prizes and lack of prior knowledge about interactions as costs. PCST/PCSF methods can, in principle, be applied to problems including heterogeneous data, but in practice have been limited to one or two predefined data types. In this thesis, we improve the PCSF system for more general inference of GRNs, develop an optimisation scheme to better separate oversized PCSFs, and describe an algorithm for merging overly fragmented PCSFs. We show that our PCSF system aids biological interpretation of GRNs inferred from genome-wide experiments.