Clusters in protein interaction networks can potentially help identify functional relationships among proteins. We study the clustering problem by modeling it as graph cut problems. Given an edge weighted graph, the goal is to partition the graph into a prescribed number of subsets obeying some capacity constraints, so as to maximize the total weight of the edges that are within a subset. Identification of a dense subset might shed some light on the biological function of all the proteins in the subset. We study integer programming formulations and exhibit large integrality gaps for various formulations. This is indicative of the difficulty in obtaining constant factor approximation algorithms using the primal-dual schema. We propose three approximation algorithms for the problem. We evaluate the algorithms on the database of interacting proteins and on randomly generated graphs. Our experiments show that the algorithms are fast and have good performance ratio in practice. / xiii, 71 leaves : ill. ; 29 cm.

Since diffusion models of social network are widely used in studying epidemiology, in this thesis, we apply diffusion models to study the contact immunity generated by attenuated vaccines.Oral polio vaccine (OPV) is a typical attenuated vaccine for polio that can produce contact immunity and therefore help protect more individuals than vaccinees. / To better capture the utilization of OPV’s contact immunity, we model the community as a social network, and formulate the task of maximizing the contact immunity effect as an optimization problem on graphs, which is to find a sequence of vertices to be “vaccinated” to maximize the total number of vertices “infected” by the attenuated virus. Furthermore, as immune defiicient patients may suffer from the live attenuated virus in the vaccine, we develop models in consideration of this restriction, and study related problems. / We present polynomial-time algorithms for these problems on trees, and show the intractability of problems on general graphs. / 社交網絡的擴散模型被廣泛運用于對流行病學的研究，在本文中，我們使用擴散模型對減毒活疫苗產生的接觸性免疫進行研究。口服脊髓灰質炎疫苗（OPV）是一種典型的減毒活疫苗，它可以在人群中產生接觸性免疫，使得更多未接種疫苗的人獲得免疫力。 / 爲了更好的刻畫OPV 產生的接觸性免疫，我們將社區模型化為社交網絡，從而將接觸性免疫效應最大化的任務轉化爲圖優化問題，即通過發現頂點的一個「接種」序列來最大化被減活病毒「感染」的頂點數量。此外，因爲減毒疫苗中的活病毒會使患有免疫缺陷的病人患病，我們考慮在此因素限制下的模型，并研究相關的問題。 / 我們給出這些問題在樹上的多項式時間算法，并證明其在一般圖上的複雜性。 / Ma, Chenglong. / Thesis M.Phil. Chinese University of Hong Kong 2015. / Includes bibliographical references (leaves 40-47). / Abstracts also in Chinese. / Title from PDF title page (viewed on 12, September, 2016). / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only.

Wang, Zexi. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 63-64). / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 0 --- Introduction --- p.1 / Chapter 1 --- The Design of the Experiments --- p.4 / Chapter 1.1 --- Flies and the Devices --- p.5 / Chapter 1.2 --- Parameter Settings and Interested Information --- p.8 / Chapter 2 --- Video Processing --- p.11 / Chapter 2.1 --- "Videos, Computer Vision and Image Processing" --- p.11 / Chapter 2.2 --- Details in Video Processing --- p.14 / Chapter 3 --- Data Analysis --- p.20 / Chapter 3.1 --- Background --- p.20 / Chapter 3.2 --- Outline of Data Analysis in Our Project --- p.22 / Chapter 4 --- Effect of the Medicine --- p.25 / Chapter 4.1 --- Hypothesis Testing --- p.26 / Chapter 4.2 --- Two-sample t Test --- p.28 / Chapter 5 --- Significance of the Two Factors --- p.32 / Chapter 5.1 --- Background of ANOVA --- p.33 / Chapter 5.2 --- The Model of ANOVA --- p.35 / Chapter 5.3 --- Two-way ANOVA in Our Data Analysis --- p.42 / Chapter 6 --- Regression Model --- p.45 / Chapter 6.1 --- Background of Regression Analysis --- p.47 / Chapter 6.2 --- Polynomial Regression Models --- p.52 / Chapter 6.2.1 --- Background --- p.52 / Chapter 6.2.2 --- R2 and adjusted R2 --- p.53 / Chapter 6.3 --- Model Verification --- p.58 / Chapter 6.4 --- A Simpler Model As the Other Choice --- p.59 / Chapter 6.5 --- Conclusions --- p.60 / Chapter 7 --- Further Studies --- p.61 / Bibliography --- p.62

Bibliography: pages 192-195 / The avoidability, or unavoidability of patterns in words over finite alphabets has been studied extensively. The word α over a finite set A is said to be unavoidable for an infinite set B+ of nonempty words over a finite set B if, for all but finitely many elements w of B+, there exists a semigroup morphism φ ∶ A+ → B+ such that φ(α) is a factor of w. In this treatise, we start by presenting a historical background of results that are related to unavoidability. We present and discuss the most important theorems surrounding unavoidability in detail. We present various complexity-related properties of unavoidable words. For words that are unavoidable, we provide a constructive upper bound to the lengths of words that avoid them. In particular, for a pattern α of length n over an alphabet of size r, we give a concrete function N(n, r) such that no word of length N(n, r) over the alphabet of size r avoids α. A natural subsequent question is how many unavoidable words there are. We show that the fraction of words that are unavoidable drops exponentially fast in the length of the word. This allows us to calculate an upper bound on the number of unavoidable patterns for any given finite alphabet. Subsequently, we investigate computational aspects of unavoidable words. In particular, we exhibit concrete algorithms for determining whether a word is unavoidable. We also prove results on the computational complexity of the problem of determining whether a given word is unavoidable. Specifically, the NP-completeness of the aforementioned problem is established. / Decision Sciences / D. Phil. (Operations Research)

Indiana University-Purdue University Indianapolis (IUPUI) / In systems biology study, biological networks were used to gain insights into biological systems. While the traditional approach to studying biological networks is based on the identification of interactions among genes or the identification of a gene set ranking according to differentially expressed gene lists, little is known about interactions between higher order biological systems, a network of gene sets. Several types of gene set network have been proposed including co-membership, linkage, and co-enrichment human gene set networks. However, to our knowledge, none of them contains directionality information. Therefore, in this study we proposed a method to construct a regulatory gene set network, a directed network, which reveals novel relationships among gene sets. A regulatory gene set network was constructed by using publicly available gene regulation data. A directed edge in regulatory gene set networks represents a regulatory relationship from one gene set to the other gene set. A regulatory gene set network was compared with another type of gene set network to show that the regulatory network provides additional information. In order to show that a regulatory gene set network is useful for understand the underlying mechanism of a disease, an Alzheimer's disease (AD) regulatory gene set network was constructed. In addition, we developed Pathway and Annotated Gene-set Electronic Repository (PAGER), an online systems biology tool for constructing and visualizing gene and gene set networks from multiple gene set collections. PAGER is available at http://discern.uits.iu.edu:8340/PAGER/. Global regulatory and global co-membership gene set networks were pre-computed. PAGER contains 166,489 gene sets, 92,108,741 co-membership edges, 697,221,810 regulatory edges, 44,188 genes, 651,586 unique gene regulations, and 650,160 unique gene interactions. PAGER provided several unique features including constructing regulatory gene set networks, generating expanded gene set networks, and constructing gene networks within a gene set. However, tissue specific or disease specific information was not considered in the disease specific network constructing process, so it might not have high accuracy of presenting the high level relationship among gene sets in the disease context. Therefore, our framework can be improved by collecting higher resolution data, such as tissue specific and disease specific gene regulations and gene sets. In addition, experimental gene expression data can be applied to add more information to the gene set network. For the current version of PAGER, the size of gene and gene set networks are limited to 100 nodes due to browser memory constraint. Our future plans is integrating internal gene or proteins interactions inside pathways in order to support future systems biology study.

Indiana University-Purdue University Indianapolis (IUPUI) / Intrinsically disordered proteins are proteins characterized by lack of stable tertiary structures under physiological conditions. Evidence shows that disordered proteins are not only highly involved in protein interactions, but also have the capability to associate with more than one partner. Short disordered protein fragments, called “molecular recognition features” (MoRFs), were hypothesized to facilitate the binding diversity of highly-connected proteins termed “hubs”. MoRFs often couple folding with binding while forming interaction complexes. Two protein disorder mechanisms were proposed to facilitate multiple partner binding and enable hub proteins to bind to multiple partners: 1. One region of disorder could bind to many different partners (one-to-many binding), so the hub protein itself uses disorder for multiple partner binding; and 2. Many different regions of disorder could bind to a single partner (many-to-one binding), so the hub protein is structured but binds to many disordered partners via interaction with disorder. Thousands of MoRF-partner protein complexes were collected from Protein Data Bank in this study, including 321 one-to-many binding examples and 514 many-to-one binding examples. The conformational flexibility of MoRFs was observed at atomic resolution to help the MoRFs to adapt themselves to various binding surfaces of partners or to enable different MoRFs with non-identical sequences to associate with one specific binding pocket. Strikingly, in one-to-many binding, post-translational modification, alternative splicing and partner topology were revealed to play key roles for partner selection of these fuzzy complexes. On the other hand, three distinct binding profiles were identified in the collected many-to-one dataset: similar, intersecting and independent. For the similar binding profile, the distinct MoRFs interact with almost identical binding sites on the same partner. The MoRFs can also interact with a partially the same but partially different binding site, giving the intersecting binding profile. Finally, the MoRFs can interact with completely different binding sites, thus giving the independent binding profile. In conclusion, we suggest that protein disorder with post-translational modifications and alternative splicing are all working together to rewire the protein interaction networks.

Indiana University-Purdue University Indianapolis (IUPUI) / Carbon nanomaterials are widely produced and used in industry, medicine and scientific research. To examine the impact of exposure to nanoparticles on human health, the human airway epithelial cell line, Calu-3, was used to evaluate changes in the cellular proteome that could account for alterations in cellular function of airway epithelia after 24 h exposure to 10 μg/mL and 100 ng/mL of two common carbon nanoparticles, singleand multi-wall carbon nanotubes (SWCNT, MWCNT). After exposure to the nanoparticles, label-free quantitative mass spectrometry (LFQMS) was used to study differential protein expression. Ingenuity Pathway Analysis (IPA) was used to conduct a bioinformatics analysis of proteins identified by LFQMS. Interestingly, after exposure to a high concentration (10 μg/mL; 0.4 μg/cm2) of MWCNT or SWCNT, only 8 and 13 proteins, respectively, exhibited changes in abundance. In contrast, the abundance of hundreds of proteins was altered in response to a low concentration (100 ng/mL; 4 ng/cm2) of either CNT. Of the 281 and 282 proteins that were significantly altered in response to MWCNT or SWCNT, respectively, 231 proteins were the same. Bioinformatic analyses found that the proteins common to both kinds of nanotubes are associated with the cellular functions of cell death and survival, cell-to-cell signaling and interaction, cellular assembly and organization, cellular growth and proliferation, infectious disease, molecular transport and protein synthesis. The decrease in expression of the majority proteins suggests a general stress response to protect cells. The STRING database was used to analyze the various functional protein networks. Interestingly, some proteins like cadherin 1 (CDH1), signal transducer and activator of transcription 1 (STAT1), junction plakoglobin (JUP), and apoptosis-associated speck-like protein containing a CARD (PYCARD), appear in several functional categories and tend to be in the center of the networks. This central positioning suggests they may play important roles in multiple cellular functions and activities that are altered in response to carbon nanotube exposure. To examine the effect of nanotubes on the plasma membrane, we investigated the interaction of short purified MWCNT with model lipid membranes using a planar bilayer workstation. Bilayer lipid membranes were synthesized using neutral 1, 2-diphytanoylsn-glycero-3-phosphocholine (DPhPC) in 1 M KCl. The ion channel model protein, Gramicidin A (gA), was incorporated into the bilayers and used to measure the effect of MWCNT on ion transport. The opening and closing of ion channels, amplitude of current, and open probability and lifetime of ion channels were measured and analyzed by Clampfit. The presence of an intermediate concentration of MWCNT (2 μg/ml) could be related to a statistically significant decrease of the open probability and lifetime of gA channels. The proteomic studies revealed changes in response to CNT exposure. An analysis of the changes using multiple databases revealed alterations in pathways, which were consistent with the physiological changes that were observed in cultured cells exposed to very low concentrations of CNT. The physiological changes included the break down of the barrier function and the inhibition of the mucocillary clearance, both of which could increase the risk of CNT’s toxicity to human health. The biophysical studies indicate MWCNTs have an effect on single channel kinetics of Gramicidin A model cation channel. These changes are consistent with the inhibitory effect of nanoparticles on hormone stimulated transepithelial ion flux, but additional experiments will be necessary to substantiate this correlation.

Indiana University-Purdue University Indianapolis (IUPUI) / A foreign concept to most twenty-first century individuals, a saddletree provides support and acts as the framework to saddles, giving saddlers a base on which to add cushioning, stretch leather, and create beautiful or functional saddles. Saddletree factories were an integral part of Madison, Indiana’s late nineteenth-century economy. As one of the Ohio River town’s leading industries, saddletree shops employed approximately 125 men during 1879, Madison’s peak saddletree production year, and made Madison a national center of saddletree production. However, the industry faded into oblivion as the beginning of the twentieth century, leaving the men drawn to these shops in the 1870s and 1880s to find new opportunities. While past historians contributed to the fields of industrial and economic history by studying large industries engaged in mass production in major urban areas, Madison’s saddletree workers represent a view of nineteenth-century specialized production. This thesis examines the saddletree industry’s place in Madison during the late nineteenth century and the lives of saddletree workers during and after the industry’s peak. My findings, based off extensive digital research and tools utilized in earlier social mobility studies, create a nuanced view of Madison’s relationship to the saddletree industry, saddletree makers, and what the industry’s collapse meant to saddletree factory employees.