Automatic Inference of Graph Models for Complex Networks with Genetic Programming

Complex networks can arise naturally and spontaneously from all things that act as a part of a larger system. From the patterns of socialization between people to the way biological systems organize themselves, complex networks are ubiquitous, but are currently poorly understood. A number of algorithms, designed by humans, have been proposed to describe the organizational behaviour of real-world networks. Consequently, breakthroughs in genetics, medicine, epidemiology, neuroscience, telecommunications and the social sciences have recently resulted. The algorithms, called graph models, represent significant human effort. Deriving accurate graph models is non-trivial, time-intensive, challenging and may only yield useful results for very specific phenomena. An automated approach can greatly reduce the human effort required and if effective, provide a valuable tool for understanding the large decentralized systems of interrelated things around us. To the best of the author's knowledge this thesis proposes the first method for the automatic inference of graph models for complex networks with varied properties, with and without community structure. Furthermore, to the best of the author's knowledge it is the first application of genetic programming for the automatic inference of graph models. The system and methodology was tested against benchmark data, and was shown to be capable of reproducing close approximations to well-known algorithms designed by humans. Furthermore, when used to infer a model for real biological data the resulting model was more representative than models currently used in the literature.

Object-Oriented Genetic Programming for the Automatic Inference of Graph Models for Complex Networks

Complex networks are systems of entities that are interconnected through meaningful relationships. The result of the relations between entities forms a structure that has a statistical complexity that is not formed by random chance. In the study of complex networks, many graph models have been proposed to model the behaviours observed. However, constructing graph models manually is tedious and problematic. Many of the models proposed in the literature have been cited as having inaccuracies with respect to the complex networks they represent. However, recently, an approach that automates the inference of graph models was proposed by Bailey [10] The proposed methodology employs genetic programming (GP) to produce graph models that approximate various properties of an exemplary graph of a targeted complex network. However, there is a great deal already known about complex networks, in general, and often specific knowledge is held about the network being modelled. The knowledge, albeit incomplete, is important in constructing a graph model. However it is difficult to incorporate such knowledge using existing GP techniques. Thus, this thesis proposes a novel GP system which can incorporate incomplete expert knowledge that assists in the evolution of a graph model. Inspired by existing graph models, an abstract graph model was developed to serve as an embryo for inferring graph models of some complex networks. The GP system and abstract model were used to reproduce well-known graph models. The results indicated that the system was able to evolve models that produced networks that had structural similarities to the networks generated by the respective target models.

Heuristics for the Critical Node Detection Problem in Large Complex Networks

Complex networks have recently attracted a significant amount of research attention due to their ability to model real world phenomena. One important problem often encountered is to limit diffusive processes spread over the network, for example mitigating pandemic disease or computer virus spread. A number of problem formulations have been proposed that aim to solve such problems based on desired network characteristics, such as maintaining the largest network component after node removal. The recently formulated critical node detection problem aims to remove a small subset of vertices from the network such that the residual network has minimum pairwise connectivity. Unfortunately, the problem is NP-hard and also the number of constraints is cubic in number of vertices, making very large scale problems impossible to solve with traditional mathematical programming techniques. Even many approximation algorithm strategies such as dynamic programming, evolutionary algorithms, etc. all are unusable for networks that contain thousands to millions of vertices. A computationally efficient and simple approach is required in such circumstances, but none currently exist. In this thesis, such an algorithm is proposed. The methodology is based on a depth-first search traversal of the network, and a specially designed ranking function that considers information local to each vertex. Due to the variety of network structures, a number of characteristics must be taken into consideration and combined into a single rank that measures the utility of removing each vertex. Since removing a vertex in sequential fashion impacts the network structure, an efficient post-processing algorithm is also proposed to quickly re-rank vertices. Experiments on a range of common complex network models with varying number of vertices are considered, in addition to real world networks. The proposed algorithm, DFSH, is shown to be highly competitive and often outperforms existing strategies such as Google PageRank for minimizing pairwise connectivity.

Network Similarity Measures and Automatic Construction of Graph Models using Genetic Programming

A complex network is an abstract representation of an intricate system of interrelated elements where the patterns of connection hold significant meaning. One particular complex network is a social network whereby the vertices represent people and edges denote their daily interactions. Understanding social network dynamics can be vital to the mitigation of disease spread as these networks model the interactions, and thus avenues of spread, between individuals. To better understand complex networks, algorithms which generate graphs exhibiting observed properties of real-world networks, known as graph models, are often constructed. While various efforts to aid with the construction of graph models have been proposed using statistical and probabilistic methods, genetic programming (GP) has only recently been considered. However, determining that a graph model of a complex network accurately describes the target network(s) is not a trivial task as the graph models are often stochastic in nature and the notion of similarity is dependent upon the expected behavior of the network. This thesis examines a number of well-known network properties to determine which measures best allowed networks generated by different graph models, and thus the models themselves, to be distinguished. A proposed meta-analysis procedure was used to demonstrate how these network measures interact when used together as classifiers to determine network, and thus model, (dis)similarity. The analytical results form the basis of the fitness evaluation for a GP system used to automatically construct graph models for complex networks. The GP-based automatic inference system was used to reproduce existing, well-known graph models as well as a real-world network. Results indicated that the automatically inferred models exemplified functional similarity when compared to their respective target networks. This approach also showed promise when used to infer a model for a mammalian brain network.

Disease-Gene Association Using a Genetic Algorithm

Understanding the relationship between genetic diseases and the genes associated with them is an important problem regarding human health. The vast amount of data created from a large number of high-throughput experiments performed in the last few years has resulted in an unprecedented growth in computational methods to tackle the disease gene association problem. Nowadays, it is clear that a genetic disease is not a consequence of a defect in a single gene. Instead, the disease phenotype is a reflection of various genetic components interacting in a complex network. In fact, genetic diseases, like any other phenotype, occur as a result of various genes working in sync with each other in a single or several biological module(s). Using a genetic algorithm, our method tries to evolve communities containing the set of potential disease genes likely to be involved in a given genetic disease. Having a set of known disease genes, we first obtain a protein-protein interaction (PPI) network containing all the known disease genes. All the other genes inside the procured PPI network are then considered as candidate disease genes as they lie in the vicinity of the known disease genes in the network. Our method attempts to find communities of potential disease genes strongly working with one another and with the set of known disease genes. As a proof of concept, we tested our approach on 16 breast cancer genes and 15 Parkinson's Disease genes. We obtained comparable or better results than CIPHER, ENDEAVOUR and GPEC, three of the most reliable and frequently used disease-gene ranking frameworks.

Disease-Gene Association Using Genetic Programming

As a result of mutation in genes, which is a simple change in our DNA, we will have undesirable phenotypes which are known as genetic diseases or disorders. These small changes, which happen frequently, can have extreme results. Understanding and identifying these changes and associating these mutated genes with genetic diseases can play an important role in our health, by making us able to find better diagnosis and therapeutic strategies for these genetic diseases. As a result of years of experiments, there is a vast amount of data regarding human genome and different genetic diseases that they still need to be processed properly to extract useful information. This work is an effort to analyze some useful datasets and to apply different techniques to associate genes with genetic diseases. Two genetic diseases were studied here: Parkinson’s disease and breast cancer. Using genetic programming, we analyzed the complex network around known disease genes of the aforementioned diseases, and based on that we generated a ranking for genes, based on their relevance to these diseases. In order to generate these rankings, centrality measures of all nodes in the complex network surrounding the known disease genes of the given genetic disease were calculated. Using genetic programming, all the nodes were assigned scores based on the similarity of their centrality measures to those of the known disease genes. Obtained results showed that this method is successful at finding these patterns in centrality measures and the highly ranked genes are worthy as good candidate disease genes for being studied. Using standard benchmark tests, we tested our approach against ENDEAVOUR and CIPHER - two well known disease gene ranking frameworks - and we obtained comparable results.

Magnetic and high pressure studies in the YPd5B3C3 system

The macroscopic properties of the superconducting phase in the multiphase compound YPd5B3 C.3 have been investigated. The onset of superconductivity was observed at 22.6 K, zero resistance at 21.2 K, the lower critical field Hel at 5 K was determined to be Hel (5) rv 310 Gauss and the compound was found to be an extreme type-II superconductor with the upper critical field in excess of 55000 Gauss at 15 K. From the upper and lower critical field values obtained, several important parameters of the superconducting state were determined at T = 15 K. The Ginzburg-Landau paramater was determined to be ~ > 9 corresponding to a coherence length ~ rv 80A and magnetic penetration depth of 800A. In addition measurements of the superconducting transition temperature Te(P) under purely hydrostatically applied pressure have been carried out. Te(P) of YPd5B3 C.3 decreases linearly with dTe/dP rv -8.814 X 10-5 J

Nuclear magnetic resonance studies of boron trihalide complexes of 1,1-BIS (dimethylamino) ethylene and related bases

Boron tribalide complexes of 1,1-bis(dimethylamino)ethylene (DME) , t etramethylurea (TMU), tetramethylguanidine (TMG) , and pentamethylguanidine (PMG) and also mixed boron t r ihalide adducts of DME have been investigated by 1H and 19F NMR spectroscopy. Both nitrogen and the C-Q-H carbon of DME are possible donor a toms to boron trihal ides but complexation has been found to occur only at carbon of DME. The initial adduct acts as a Bronsted acid and gives up a proton to free DME in solut ion. A side reaction in the DME-BF, system gives rise to trace amounts of a complex aSSigned as (DME)2BF2+. (DME)2BF2+ is produced in much larger quantities in t he DME-BF3-BC13 and DME-BF,-BBr, systems by reaction of free DME with DME:BF2X (X = Cl, Br). Restricted r otation about the C-N bonds of TMUlBC13 and n1U:BBr3 has been observed at low temperatures. This complements previous work in this system and confirms oxygen donation of TMU to boron trihalides . Restricted rotation at low temperatures also has been observed in DMEboron trihalide systems

Competing demands for a complex system : photosystem II repair, photoprotection and quantum yield

Photosynthesis in general is a key biological process on Earth and Photo system II (PSII) is an important component of this process. PSII is the only enzyme capable of oxidizing water and is largely responsible for the primordial build-up and present maintenance of the oxygen in the atmosphere. This thesis endeavoured to understand the link between structure and function in PSII with special focus on primary photochemistry, repair/photodamage and spectral characteristics. The deletion of the PsbU subunit ofPSII in cyanobacteria caused a decoupling of the Phycobilisomes (PBS) from PSII, likely as a result of increased rates of PSII photodamage with the PBS decoupling acting as a measure to protect PSII from further damage. Isolated fractions of spinach thylakoid membranes were utilized to characterize the heterogeneity present in the various compartments of the thylakoid membrane. It was found that the pooled PSIILHCII pigment populations were connected in the grana stack and there was also a progressive decrease in the reaction rates of primary photochemistry and antennae size of PSII as the sample origin moved from grana to stroma. The results were consistent with PSII complexes becoming damaged in the grana and being sent to the stroma for repair. The dramatic quenching of variable fluorescence and overall fluorescent yield of PSII in desiccated lichens was also studied in order to investigate the mechanism by which the quenching operated. It was determined that the source of the quenching was a novel long wavelength emitting external quencher. Point mutations to amino acids acting as ligands to chromophores of interest in PSII were utilized in cyanobacteria to determine the role of specific chromophores in energy transfer and primary photochemistry. These results indicated that the Hl14 ligated chlorophyll acts as the 'trap' chlorophyll in CP47 at low temperature and that the Q130E mutation imparts considerable changes to PSII electron transfer kinetics, essentially protecting the complex via increased non-radiative charge Photosynthesis in general is a key biological process on Earth and Photo system II (PSII) is an important component of this process. PSII is the only enzyme capable of oxidizing water and is largely responsible for the primordial build-up and present maintenance of the oxygen in the atmosphere. This thesis endeavoured to understand the link between structure and function in PSII with special focus on primary photochemistry, repair/photodamage and spectral characteristics. The deletion of the PsbU subunit ofPSII in cyanobacteria caused a decoupling of the Phycobilisomes (PBS) from PSII, likely as a result of increased rates of PSII photodamage with the PBS decoupling acting as a measure to protect PSII from further damage. Isolated fractions of spinach thylakoid membranes were utilized to characterize the heterogeneity present in the various compartments of the thylakoid membrane. It was found that the pooled PSIILHCII pigment populations were connected in the grana stack and there was also a progressive decrease in the reaction rates of primary photochemistry and antennae size of PSII as the sample origin moved from grana to stroma. The results were consistent with PSII complexes becoming damaged in the grana and being sent to the stroma for repair. The dramatic quenching of variable fluorescence and overall fluorescent yield of PSII in desiccated lichens was also studied in order to investigate the mechanism by which the quenching operated. It was determined that the source of the quenching was a novel long wavelength emitting external quencher. Point mutations to amino acids acting as ligands to chromophores of interest in PSII were utilized in cyanobacteria to determine the role of specific chromophores in energy transfer and primary photochemistry. These results indicated that the Hl14 ligated chlorophyll acts as the 'trap' chlorophyll in CP47 at low temperature and that the Q130E mutation imparts considerable changes to PSII electron transfer kinetics, essentially protecting the complex via increased non-radiative charge.