Item Details

abstract

Graph algorithms have been widely applied to science and engineering problems, but the practical applications of graph algorithms to every-growing, large data sets requires significant computational time, motivating the need for efficient, parallel solutions on modern computing architectures. Here, we develop a novel GPU-optimized parallel algorithm for measuring the betweenness centrality of edges of a graph that is over 1000x faster than the CPU implementation of the algorithm in the NetworkX software package for 1,000-5,000 nodes. Inspired by biochemical mutagenesis experiments, we also introduce a new approach to measure how the betweenness centrality changes with the perturbation of a graph. As a direct application, we performed MD simulations of several protein-RNA complex, where we abstracted the residues and their interactions as nodes and edges, respectively, to characterize the molecular interaction network. We then systematically compare the change in the betweenness upon the deletion of the residue, akin to mutagenesis experiments performed in the laboratory, to create a predictor for mutagenesis experiments. Finally, we compared communal detection results to previously determined protein domains, finding a high correlation between residue-residue interactome communities and larger protein domains.

subject

Betweenness

GPU

Graph Theory

Parallel

Perturbation

contributor

Stevens, Cody Alexander (author)

Cho, Samuel S (committee chair)

Torgersen, Todd (committee member)

Turkett, William H (committee member)

date

2015-06-23T08:36:02Z (accessioned)

2015-06-23T08:36:02Z (available)

2015 (issued)

degree

Computer Science (discipline)

identifier

http://hdl.handle.net/10339/57193 (uri)

language

en (iso)

publisher

Wake Forest University

title

GPU-Optimized Graph Theory Analysis of Allosteric Protein Signaling Networks

type

Thesis