Virginia Tech\'s Computational Bioinformatics and Bio-imaging Laboratory (CBIL) is exploring integrative network analysis techniques to identify subnetworks or genetic pathways that contribute to various cancers. Chen et. al. developed a bagging Markov random field (BMRF)-based approach which examines gene expression data with prior biological information to reliably identify significant genes and proteins. Using random resampling with replacement (bootstrapping or bagging) is essential to confident results but is computationally demanding as multiple iterations of the network identification (by simulated annealing) is required. The MATLAB implementation is computationally demanding, employs limited concurrency, and thus time prohibitive. Using strong software development discipline we optimize BMRF using algorithmic, compiler, and concurrency techniques (including Nvidia GPUs) to alleviate the wall clock time needed for analysis of large-scale genomic data. Particularly, we decompose the BMRF algorithm into functional blocks, implement the algorithm in C/C++ and further explore the C/C++ implementation with concurrency optimization. Experiments are conducted with simulation and real data to demonstrate that a significant speedup of BMRF can be achieved by exploiting concurrency opportunities. We believe that the experience gained by this research shall help pave the way for us to develop computationally efficient algorithms leveraging concurrency, enabling researchers to efficiently analyze larger-scale data sets essential for furthering cancer research. / Master of Science

A comprehensive approach is conducted to better utilize dynamic traffic assignment (DTA) in transportation planning by investigating its role in: (1) high-order functions, (2) project evaluation, and (3) traffic assignment. A method is proposed to integrate DTA and the four-step planning model such that traffic assignment is conducted at the subnetwork level while the feedback process occurs at the regional level. By allowing interaction between the subnetwork and regional area, the method is shown to be more beneficial than previous integration structures. Additionally, DTA is applied to a case study involving the proposed urban rail system in Austin, TX. The case study showcases the benefits and capabilities of DTA when analyzing traffic impacts caused by transit rail facilities. Multiple equilibria are shown to arise in simulation-based DTA models due to simplified fundamental diagrams. Piecewise linear diagrams are introduced to eliminate unlikely equilibria. Game theory is also applied to DTA; it is shown that an equilibrium solution is guaranteed to exist for general networks in mixed strategies, and unrealistic equilibria are reduced using the trembling hand refinement. / text

Dynamic traffic assignment (DTA) can be used to model impacts of network modification scenarios, including traffic control plans (TCPs), on traffic flow. However, using DTA for modeling construction project impacts is limited by the computational time required to simulate entire roadway networks. DTA modeling of a portion of the larger network surrounding these work zones can decrease the overall run time. However, impacts are likely to extend beyond typical boundaries, and determining the proper extents to be analyzed is necessary. Therefore, a methodology for selecting an adequate portion to analyze using DTA, along with provision for properly analyzing the resultant subnetwork, is necessary to determine the magnitude of construction impacts. The primary objectives of this research center on evaluating subnetwork sizes to determine the appropriate extents required to analyze network modifications and developing a strategy to account for impacts extending beyond the subnetwork boundary. The first objective is accomplished through an in-depth review of subnetwork sizes relative to multiple impact scenarios. Three statistical measures are implemented to evaluate the adequacy of a chosen subnetwork relative to the derived impact scenarios based on an assessment of boundary demand. Ultimately, the root mean squared error is used successfully to provide a series of recommended subnetwork sizes associated with an array of possible impact scenarios. These recommendations are validated, and application of the proposed methodology demonstrated, using five scenarios selected from real-world network modifications observed in the field. When a subnetwork is not large enough and impacts to inbound trips pass beyond the boundary, there is a change in flow at this location that can be represented by a change in the demand assigned to the subnetwork at each entry point. As such, two strategies for adjusting the demand at subnetwork boundaries are implemented and evaluated. This includes use of results from static traffic assignment (STA) models to identify where flow changes occur, and implementation of a logit formulation to estimate demand adjustments based on differences in internal travel times between base and impact scenario models. Based on preliminary results, the logit method was selected for large-scale implementation and testing. In the end, an inconsistent performance of the logit method for full implementation highlights the limitations of the methodology as applied for this study. However, the results suggest that a refined strategy that builds on the foundation established could work more effectively and produce valuable subnetwork demand estimates in the future. This research is used to provide recommendations for selecting and analyzing subnetworks using DTA for an array of common impact scenarios involving network modifications. The tradeoffs between improved efficiency and reduced accuracy associated with using subnetworks are thoroughly demonstrated. It is shown that a considerable amount of computational time and space, as well as effort on the part of an analyst, can be saved. A number of limitations associated with subnetworks are also identified and discussed. The proposed methodology is implemented and evaluated using several software programs and as a result, a number of useful tools and software scripts are developed as part of the research. Ultimately, the valuable experience gained from performing an extensive review of subnetwork analysis using DTA can be used as a basis from which to develop future research initiatives. / text

The focus of this dissertation is a methodology to select an appropriate subnetwork from a large urban transportation network that experiences changes to a small fraction of the whole network. Subnetwork selection techniques are most effective when using a regional dynamic traffic assignment model. The level of detail included in the regional model relieves the user of manually coding subnetwork components because they can be extracted from the full model. This method will reduce the resources necessary for an agency to complete an analysis through time and cost savings. Dynamic traffic assignment also has the powerful capability of determining rerouting due to network changes. However, the major limitation of these new dynamic models is the computational demand of the algorithms, which inhibit use of full regional models for comparing multiple scenarios. By examining a smaller window of the network, where impacts are expected to occur, the burden of computer power and time can be overcome. These methods will contribute to the accuracy of dynamic transportation systems analysis, increase the tractability of these advanced traffic models, and help implement new modeling techniques previously limited by network size. The following describes how to best understand the effects of reducing a network to a subarea and how this technique may be implemented in practice. / text

Finding reliable gene markers for accurate disease classification is very challenging due to a number of reasons, including the small sample size of typical clinical data, high noise in gene expression measurements, and the heterogeneity across patients. In fact, gene markers identified in independent studies often do not coincide with each other, suggesting that many of the predicted markers may have no biological significance and may be simply artifacts of the analyzed dataset. To nd more reliable and reproducible diagnostic markers, several studies proposed to analyze the gene expression data at the level of groups of functionally related genes, such as pathways. Given a set of known pathways, these methods estimate the activity level of each pathway by summarizing the expression values of its member genes and using the pathway activities for classification. One practical problem of the pathway-based approach is the limited coverage of genes by currently known pathways. As a result, potentially important genes that play critical roles in cancer development may be excluded. In this thesis, we first propose a probabilistic model to infer pathway/subnetwork activities. After that, we developed a novel method for identifying reliable subnetwork markers in a human protein-protein interaction (PPI) network based on probabilistic inference of subnetwork activities. We tested the proposed methods based on two independent breast cancer datasets. The proposed method can efficiently find reliable subnetwork markers that outperform the gene-based and pathway-based markers in terms of discriminative power, reproducibility and classification performance. The identified subnetwork markers are highly enriched in common GO terms, and they can more accurately classify breast cancer metastasis compared to markers found by a previous method.

The presented thesis is focused on a set of problems related to managerial decision-making concerning networks (particularly transportation networks), respectively - if we put it more precisely - the thesis focuses on the support of this decision-making by means of quantitative methods. A set of problems related to nets and decision-making concerning their individual parts or elements represents a very complex sphere which has been a subject of research for a number of decades. Out of this sphere, the thesis formulates and elaborates in great detail two problems, which - from the point of view of their practical significance - are important for the decision-making of managers of carriers, or the public sphere, and which have not been published in this form yet. The main point is the problem of how to find a subnet with a limited prolongation of routes between important pairs of vertices. Another problem is a design of a bus route in an area with a low demand. For each of these problems, the thesis offers an exact combinatorial solution method, furthermore a method based on integer linear programming, and - last but not least - also, of course, heuristic methods of solution. All these methods have been tested on a set of networks, which has been created for this purpose in a pseudo-random way in the frame of this thesis. The testing has been focused primarily on the comparison of the results provided by heuristic methods, which are of great importance - with regard to a great computational difficulty of exact methods - for feasible tasks on a larger scale. The tests have proved that the proposed heuristic methods are practically applicable and show results whicheven represent the optimal solution in a number of cases, or are only slightly distant from the optimal solution.

No description available.

Indiana University-Purdue University Indianapolis (IUPUI) / Biological systems behave differently under different conditions. Advances in sequencing technology over the last decade have led to the generation of enormous amounts of condition-specific data. However, these measurements often fail to identify low abundance genes/proteins that can be biologically crucial. In this work, a novel text-mining system was first developed to extract condition-specific proteins from the biomedical literature. The literature-derived data was then combined with proteomics data to construct condition-specific protein interaction networks. Further, an innovative condition-specific differential analysis approach was designed to identify key differences, in the form of subnetworks, between any two given biological systems. The framework developed here was implemented to understand the differences between limb regeneration-competent Ambystoma mexicanum and –deficient Xenopus laevis. This study provides an exhaustive systems level analysis to compare regeneration competent and deficient subnetworks to show how different molecular entities inter-connect with each other and are rewired during the formation of an accumulation blastema in regenerating axolotl limbs. This study also demonstrates the importance of literature-derived knowledge, specific to limb regeneration, to augment the systems biology analysis. Our findings show that although the proteins might be common between the two given biological conditions, they can have a high dissimilarity based on their biological and topological properties in the subnetwork. The knowledge gained from the distinguishing features of limb regeneration in amphibians can be used in future to chemically induce regeneration in mammalian systems. The approach developed in this dissertation is scalable and adaptable to understand differential subnetworks between any two biological systems. This methodology will not only facilitate the understanding of biological processes and molecular functions which govern a given system but also provide novel intuitions about the pathophysiology of diseases/conditions.