![\"\"](\"https:\/\/blogs.reed.edu\/compbio\/files\/2022\/08\/Screen-Shot-2022-08-11-at-4.47.53-PM-1024x348.png\")
The “induced” part of the definition means that given a subgraph that looks exactly like G29<\/sub>, a 5 node clique, we would not say that G15<\/sub>, the 5 node ring is also present. Given 5 connected nodes, there is only one 5 node graphlet present. The graphlet must contain all of the edges between the selected nodes.<\/p>\n\n\n\n So why graphlets? They are a way to investigate patterns and the higher order structure of the network. In between the very local level of two nodes being connected by an edge, which doesn’t tell us about any greater trends, but much less global than a statistic such as density, which misses much of the network-specific intricacies. <\/p>\n\n\n\n Markov Clustering essentially simulates a random walk. Given an edge list, MCL creates a transition matrix, where every column and row represent a node with the entry In the implementation of MCL, there is a parameter you can choose called the “inflation parameter” which controls how far those probabilities are exaggerated. A lower inflation parameter means less “inflation” and thus a coarser clustering and larger clusters, while a higher inflation parameter produces more, smaller clusters. Which inflation parameter to use is dependent on both the specific network and your goals.<\/p>\n\n\n So the main idea behind this project is to combine the two and see if any graphlet-based versions of MCL uncover anything insightful that normal MCL could not. To combine the two, for a given graphlet, all of the edges that did not participate in the given graphlet were deleted. MCL then performed clustering on the graph that remained. Thus we are left with 30 different clusterings of the same network. <\/p>\n\n\n\n Specifically, I have been focusing on a protein-protein interactome (ppi) with 21,559 proteins and 342,353 edges. This interactome contains genes associated with 519 diseases. Each of the 30 different versions of MCL produced different clusterings of these genes. I am currently trying to compare the results of the different higher-order graphlets to G0<\/sub>, which is normal MCL. <\/p>\n\n\n\n Here are a couple Venn diagrams comparing the “best” clusters from G0<\/sub> and G29<\/sub> for a couple diseases. “Best” means the cluster had the most disease genes in it. <\/p>\n\n\n We see that in these diseases, the best cluster of G29<\/sub> is much more enriched than the best cluster of G0<\/sub>. <\/p>\n\n\n\n I have also calculated the hypergeometric score for each of these best clusters across all of the diseases, which is the probability that given N<\/em> disease genes in a pool of M <\/em>total genes, that a cluster with m<\/em> genes would contain n<\/em> disease genes. Essentially, is the number of disease genes in that cluster significant? Or is it likely to happen just by chance.<\/p>\n\n\n\n A problem I am facing with these hypergeometric scores is how to compare the probabilities across different graphlets, and hopefully I’ll figure something out before my research ends next week.<\/p>\n","protected":false},"excerpt":{"rendered":" Hi! My name is Hannah Kuder, I’m a rising math-physics senior working in Anna Ritz’s lab this summer. My project has focused on implementing a graphlet-based version of the Markov Clustering (MCL) algorithm on various biological interactomes in order to compare those clusterings to normal MCL. In particular, whether any of the graphlets cluster disease … Continue reading “Clustering with Graphlets”<\/span><\/a><\/p>\n","protected":false},"author":2569,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-681","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/posts\/681","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/users\/2569"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/comments?post=681"}],"version-history":[{"count":11,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/posts\/681\/revisions"}],"predecessor-version":[{"id":703,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/posts\/681\/revisions\/703"}],"wp:attachment":[{"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/media?parent=681"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/categories?post=681"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.reed.edu\/compbio\/wp-json\/wp\/v2\/tags?post=681"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Markov Clustering<\/h3>\n\n\n\n
[i,j]<\/code> being the probability a transition from one node to the other could occur. MCL then cycles between two steps: expansion and inflation. <\/p>\n\n\n\n![\"\"](\"https:\/\/blogs.reed.edu\/compbio\/files\/2022\/08\/mcl_pic.png\")
Graphlet-Based MCL<\/h3>\n\n\n\n
![\"\"](\"https:\/\/blogs.reed.edu\/compbio\/files\/2022\/08\/venn_leukemia-1024x580.png\")
![\"\"](\"https:\/\/blogs.reed.edu\/compbio\/files\/2022\/08\/venn_heatstroke-1-973x1024.png\")
<\/figure><\/div>\n\n\n