Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Publication
- Publication Type
Articles 1 - 6 of 6
Full-Text Articles in Physical Sciences and Mathematics
Parallel Adaptive Algorithms For Sampling Large Scale Networks, Kanimathi Duraisamy
Parallel Adaptive Algorithms For Sampling Large Scale Networks, Kanimathi Duraisamy
Student Work
The study of real-world systems, represented as networks, has important application in many disciplines including social sciences [1], bioinformatics [2] and software engineering [3]. These networks are extremely large, and analyzing them is very expensive. Our research work involves developing parallel graph sampling methods for efficient analysis of gene correlation networks. Our sampling algorithms maintain important structural and informational properties of large unstructured networks. We focus on preserving the relative importance, based on combinatorial metrics, rather than the exact measures. We use a special subgraph technique, based on finding triangles called maximal chordal subgraphs, which maintains the highly connected portions …
A Novel Multithreaded Algorithm For Extracting Maximal Chordal Subgraphs, Mahantesh Halappanavar, John Feo, Kathryn Dempsey Cooper, Hesham Ali, Sanjukta Bhowmick
A Novel Multithreaded Algorithm For Extracting Maximal Chordal Subgraphs, Mahantesh Halappanavar, John Feo, Kathryn Dempsey Cooper, Hesham Ali, Sanjukta Bhowmick
Interdisciplinary Informatics Faculty Proceedings & Presentations
Chordal graphs are triangulated graphs where any cycle larger than three is bisected by a chord. Many combinatorial optimization problems such as computing the size of the maximum clique and the chromatic number are NP-hard on general graphs but have polynomial time solutions on chordal graphs. In this paper, we present a novel multithreaded algorithm to extract a maximal chordal sub graph from a general graph. We develop an iterative approach where each thread can asynchronously update a subset of edges that are dynamically assigned to it per iteration and implement our algorithm on two different multithreaded architectures - Cray …
On The Design Of Advanced Filters For Biological Networks Using Graph Theoretic Properties, Kathryn Dempsey Cooper, Tzu-Yi Chen, Sanjukta Bhowmick, Hesham Ali
On The Design Of Advanced Filters For Biological Networks Using Graph Theoretic Properties, Kathryn Dempsey Cooper, Tzu-Yi Chen, Sanjukta Bhowmick, Hesham Ali
Interdisciplinary Informatics Faculty Proceedings & Presentations
Network modeling of biological systems is a powerful tool for analysis of high-throughput datasets by computational systems biologists. Integration of networks to form a heterogeneous model requires that each network be as noise-free as possible while still containing relevant biological information. In earlier work, we have shown that the graph theoretic properties of gene correlation networks can be used to highlight and maintain important structures such as high degree nodes, clusters, and critical links between sparse network branches while reducing noise. In this paper, we propose the design of advanced network filters using structurally related graph theoretic properties. While spanning …
The Development Of Parallel Adaptive Sampling Algorithms For Analyzing Biological Networks, Kathryn Dempsey Cooper, Kanimathi Duraisamy, Sanjukta Bhowmick, Hesham Ali
The Development Of Parallel Adaptive Sampling Algorithms For Analyzing Biological Networks, Kathryn Dempsey Cooper, Kanimathi Duraisamy, Sanjukta Bhowmick, Hesham Ali
Interdisciplinary Informatics Faculty Proceedings & Presentations
The availability of biological data in massive scales continues to represent unlimited opportunities as well as great challenges in bioinformatics research. Developing innovative data mining techniques and efficient parallel computational methods to implement them will be crucial in extracting useful knowledge from this raw unprocessed data, such as in discovering significant cellular subsystems from gene correlation networks. In this paper, we present a scalable combinatorial sampling technique, based on identifying maximum chordal subgraphs, that reduces noise from biological correlation networks, thereby making it possible to find biologically relevant clusters from the filtered network. We show how selecting the appropriate filter …
A Noise Reducing Sampling Approach For Uncovering Critical Properties In Large Scale Biological Networks, Karthik Duraisamy, Kathryn Dempsey Cooper, Hesham Ali, Sanjukta Bhowmick
A Noise Reducing Sampling Approach For Uncovering Critical Properties In Large Scale Biological Networks, Karthik Duraisamy, Kathryn Dempsey Cooper, Hesham Ali, Sanjukta Bhowmick
Interdisciplinary Informatics Faculty Proceedings & Presentations
A correlation network is a graph-based representation of relationships among genes or gene products, such as proteins. The advent of high-throughput bioinformatics has resulted in the generation of volumes of data that require sophisticated in silico models, such as the correlation network, for in-depth analysis. Each element in our network represents expression levels of multiple samples of one gene and an edge connecting two nodes reflects the correlation level between the two corresponding genes in the network according to the Pearson correlation coefficient. Biological networks made in this manner are generally found to adhere to a scale-free structural nature, that …
A Parallel Graph Sampling Algorithm For Analyzing Gene Correlation Networks, Kathryn Dempsey Cooper, Kanimathi Duraisamy, Hesham Ali, Sanjukta Bhowmick
A Parallel Graph Sampling Algorithm For Analyzing Gene Correlation Networks, Kathryn Dempsey Cooper, Kanimathi Duraisamy, Hesham Ali, Sanjukta Bhowmick
Interdisciplinary Informatics Faculty Publications
Effcient analysis of complex networks is often a challenging task due to its large size and the noise inherent in the system. One popular method of overcoming this problem is through graph sampling, that is extracting a representative subgraph from the larger network. The accuracy of the sample is validated by comparing the combinatorial properties of the subgraph and the original network. However, there has been little study in comparing networks based on the applications that they represent. Furthermore, sampling methods are generally applied agnostically, without mapping to the requirements of the underlying analysis. In this paper,we introduce a parallel …