Doctoral Dissertations

Date of Award

12-2025

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Computer Science

Major Professor

Michael A. Langston

Committee Members

Michael A. Langston, Margaret Staton, Michael W. Berry, David Icove

Abstract

Modern life sciences increasingly leverage graph-theoretic models to untangle complex biological relationships; however, existing algorithms often struggle with the scale and heterogeneity of life science data. This dissertation addresses these challenges by developing and applying advanced graph theory algorithms in key domains of the life sciences.

First, the dissertation introduces a novel link prediction algorithm, Triclique Augmentation, for multipartite biological networks, with a focus on disease-drug–protein interaction graphs. This algorithm integrates topological features with domain-specific information to infer new links in a tripartite network, facilitating drug repositioning discoveries. Its performance was evaluated using several widely adopted bioinformatics tools, all of which confirmed that the algorithm identifies biologically plausible associations. This method not only reduces the economic and temporal costs of pharmaceutical development, but also pioneers the use of multipartite graphs in bioinformatics—moving beyond traditional bipartite models to enhance prediction accuracy.

Second, the dissertation explores the structural properties of k–partite graphs, focusing on the enumeration of maximal k–partite cliques. To overcome limitations in existing algorithms, an improved method called MPCE is introduced, which enhances efficiency by eliminating non-viable candidates early in the search. Building on the Bron–Kerbosch algorithm, MPCE is designed for scalability and is validated on both synthetic and biological datasets.

Third, the dissertation presents the Power Gabriel Graph (PGG), a graph construction algorithm that extends the classical Gabriel Graph by incorporating a tunable power parameter. This enables flexible control over edge filtering and graph density. Unlike traditional global thresholding methods used in gene network construction, PGG uses local topological structure to make adaptive edge retention decisions—a rarely employed approach in this domain. Applied to gene expression data, PGG successfully constructs biologically meaningful co-expression networks. Theoretical properties of the resulting graphs are also formally established.

These contributions create a framework where advanced graph algorithms help make new discoveries in life sciences, showing how computer science and biology can benefit each other.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS