Maddy Vinal Abstract

Maddy Vinal (UNC math Undergrad)

Title: Hitting Probability Metric for the Analysis of Gene Expression Data on Directed Graphs

Abstract: Metrics intended for undirected graphs, such as the shortest path distance and generalized effective resistance, are often used in the analysis of directed graphs. As a result, they often overlook crucial underlying information encoded in the graph’s directionality. Following up on [1], this project aims to leverage the differences between the dynamics of random walks on these two very different types of graphs. To this end, we developed a Python implementation [2] of a new type of metric, intended for strongly connected, directed graphs, known as the Hitting Probability Metric. We compared our metric to the generalized effective resistance metric in two simple synthetic graphs: one undirected, the other directed. While the results for the undirected graph did not significantly differ between the two metrics, the synthetic directed graph’s results did vary significantly. The Hitting Probability metric produced from this network better captured the underlying topology of the graph than the generalized effective resistance. In ongoing work, the Hitting Probability Metric will also be applied to a gene network used in [3], analyzing different sarcoma types. Even though the gene network is directed, the prior study used the shortest path metric on an undirected version of the network. This project will compare the results of this prior study with those generated by the new metric, and investigate whether the Hitting Probabilities metric is more effective than the shortest path or generalized effective resistance metrics. Effectiveness will be measured by how well the Hitting Probability Metric clusters cancer subtypes versus the shortest path and effective resistance metrics, using a small dataset of patient gene expression levels of the associated gene network.