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.

La génomique évolutive mitochondriale révèle des échanges génétiques et la ségrégation chez les Gloméromycètes

Les champignons mycorhiziens à arbuscules (CMA) sont des organismes microscopiques du sol qui jouent un rôle crucial dans les écosystèmes naturels et que l’on retrouve dans tous les habitats de la planète. Ils vivent en relation symbiotique avec la vaste majorité des plantes terrestres. Ils sont des biotrophes obligatoires, c'est-à-dire qu'ils ne peuvent croître qu'en présence d'une plante hôte. Cette symbiose permet entre autres à la plante d'acquérir des nutriments supplémentaires, en particulier du phosphore et du nitrate. Malgré le fait que cette symbiose apporte des services importants aux écosystèmes, la richesse des espèces, la structure des communautés, ainsi que la diversité fonctionnelle des CMA sont mal connues et l'approfondissement des connaissances dans ces domaines dépend d’outils de diagnostic moléculaire. Cependant, la présence de polymorphisme nucléaire intra-isolat combiné à un manque de données génomiques dans différents groupes phylogénétique de ces champignons complique le développement de marqueurs moléculaires et la détermination de l'affiliation évolutive à hauts niveaux de résolution (c.a.d. entre espèces génétiquement similaires et/ou isolats de la même espèce). . Pour ces raisons, il semble une bonne alternative d’utiliser un système génétique différent en ciblant le génome mitochondrial, qui a été démontré homogène au sein d'un même isolat de CMA. Cependant, étant donné le mode de vie particulier de ces organismes, une meilleure compréhension des processus évolutifs mitochondriaux est nécessaire afin de valoriser l'utilisation de tels marqueurs dans des études de diversité et en génétique des populations. En ce sens, mon projet de doctorat consistait à investiguerétudier: i) les vecteurs de divergences inter-isolats et -espèces génétiquement rapprochéesphylogénétiquement apparentées, ii) la plasticité des génomes mitochondriaux, iii) l'héritabilité mitochondriale et les mécanismes potentiels de ségrégation, ainsi que iv) la diversité mitochondriale intra-isolat in situ. À l'aide de la génomique mitochondriale comparative, en utilisant le séquençage nouvelle génération, on a démontré la présence de variation génétique substantielle inter-isolats et -espèces, engendrées par l'invasion d'éléments mobiles dans les génomes mitochondriaux des CMA, donnant lieu à une évolution moléculaire rapide des régions intergéniques. Cette variation permettait de développer des marqueurs spécifiques à des isolats de la même espèce. Ensuite, à l'aide d'une approche analytique par réseaux de gènes sur des éléments mobiles, on a été en mesure de démontrer des évènements de recombinaisons homologues entre des haplotypes mitochondriaux distincts, menant à des réarrangements génomiques. Cela a permis d'ouvrir les perspectives sur la dynamique mitochondriale et l'hétéroplasmie dans un même isolatsuggère une coexistence de différents haplotypes mitochondriaux dans les populations naturelles et que les cultures monosporales pourraient induirent une sous-estimation de la diversité allélique mitochondriale. Cette apparente contradiction avec l'homogénéité mitochondriale intra-isolat généralement observée, a amené à investiguer étudier les échanges génétiques à l'aide de croisements d'isolats génétiquement distincts. Malgré l'observation de quelques spores filles hétéroplasmiques, l'homoplasmie était le statut par défaut dans toutes les cultures monosporales, avec un biais en faveur de l'un des haplotypes parentaux. Ces résultats suggèrent que la ségrégation opère durant la formation de la spore et/ou le développement de la coloniedu mycélium. De plus, ils supportent la présence d'une machinerie protéique de ségrégation mitochondriale chez les CMAAMF, où l'ensemble des gènes impliqués dans ce mécanisme ont été retrouvé et sont orthologues aux autres champignons. Finalement, on est revenue aux sources avecon a étudié le polymorphisme mitochondrial intra-isolat à l'aide d'une approche conventionnelle de PCR en utilisant une Taq polymérase de haute fidélité, suivie de clonage et de séquençage Sanger, sur deux isolats de R. irregularis. Cela a permis l'observation d'hétéroplasmie in situ, ainsi que la co-expression de variantes de variantes de protéines'ARNm dans une souche in vitro. Les résultats suggèrent que d'autres études basées sur le séquençage nouvelle génération aurait potentiellement ignorée cette variation, offrant ainsi plusieurs nouveaux arguments permettant de considérer les CMA comme des organismes possédant une population de génomes mitochondriaux et nucléaires distincts.

Using complex networks concepts to assess approaches for citations in scientific papers

The number of citations received by authors in scientific journals has become a major parameter to assess individual researchers and the journals themselves through the impact factor. A fair assessment therefore requires that the criteria for selecting references in a given manuscript should be unbiased with regard to the authors or journals cited. In this paper, we assess approaches for citations considering two recommendations for authors to follow while preparing a manuscript: (i) consider similarity of contents with the topics investigated, lest related work should be reproduced or ignored; (ii) perform a systematic search over the network of citations including seminal or very related papers. We use formalisms of complex networks for two datasets of papers from the arXiv and the Web of Science repositories to show that neither of these two criteria is fulfilled in practice. By representing the texts as complex networks we estimated a similarity index between pieces of texts and found that the list of references did not contain the most similar papers in the dataset. This was quantified by calculating a consistency index, whose maximum value is one if the references in a given paper are the most similar in the dataset. For the areas of "complex networks" and "graphenes", the consistency index was only 0.11-0.23 and 0.10-0.25, respectively. To simulate a systematic search in the citation network, we employed a traditional random walk search (i.e. diffusion) and a random walk whose probabilities of transition are proportional to the number of the ingoing edges of the neighbours. The frequency of visits to the nodes (papers) in the network had a very small correlation with either the actual list of references in the papers or with the number of downloads from the arXiv repository. Therefore, apparently the authors and users of the repository did not follow the criterion related to a systematic search over the network of citations. Based on these results, we propose an approach that we believe is fairer for evaluating and complementing citations of a given author, effectively leading to a virtual scientometry.

"Thematically Analysing Social Network Content During Disasters Through the Lens of the Disaster Management Lifecycle" & "Investigating Similarity Between Privacy Policies of Social Networking Sites as a Precursor for Standardization"

Abstract 1: Social Networks such as Twitter are often used for disseminating and collecting information during natural disasters. The potential for its use in Disaster Management has been acknowledged. However, more nuanced understanding of the communications that take place on social networks are required to more effectively integrate this information into the processes within disaster management. The type and value of information shared should be assessed, determining the benefits and issues, with credibility and reliability as known concerns. Mapping the tweets in relation to the modelled stages of a disaster can be a useful evaluation for determining the benefits/drawbacks of using data from social networks, such as Twitter, in disaster management.A thematic analysis of tweets’ content, language and tone during the UK Storms and Floods 2013/14 was conducted. Manual scripting was used to determine the official sequence of events, and classify the stages of the disaster into the phases of the Disaster Management Lifecycle, to produce a timeline. Twenty- five topics discussed on Twitter emerged, and three key types of tweets, based on the language and tone, were identified. The timeline represents the events of the disaster, according to the Met Office reports, classed into B. Faulkner’s Disaster Management Lifecycle framework. Context is provided when observing the analysed tweets against the timeline. This illustrates a potential basis and benefit for mapping tweets into the Disaster Management Lifecycle phases. Comparing the number of tweets submitted in each month with the timeline, suggests users tweet more as an event heightens and persists. Furthermore, users generally express greater emotion and urgency in their tweets.This paper concludes that the thematic analysis of content on social networks, such as Twitter, can be useful in gaining additional perspectives for disaster management. It demonstrates that mapping tweets into the phases of a Disaster Management Lifecycle model can have benefits in the recovery phase, not just in the response phase, to potentially improve future policies and activities. Abstract2: The current execution of privacy policies, as a mode of communicating information to users, is unsatisfactory. Social networking sites (SNS) exemplify this issue, attracting growing concerns regarding their use of personal data and its effect on user privacy. This demonstrates the need for more informative policies. However, SNS lack the incentives required to improve policies, which is exacerbated by the difficulties of creating a policy that is both concise and compliant. Standardization addresses many of these issues, providing benefits for users and SNS, although it is only possible if policies share attributes which can be standardized. This investigation used thematic analysis and cross- document structure theory, to assess the similarity of attributes between the privacy policies (as available in August 2014), of the six most frequently visited SNS globally. Using the Jaccard similarity coefficient, two types of attribute were measured; the clauses used by SNS and the coverage of forty recommendations made by the UK Information Commissioner’s Office. Analysis showed that whilst similarity in the clauses used was low, similarity in the recommendations covered was high, indicating that SNS use different clauses, but to convey similar information. The analysis also showed that low similarity in the clauses was largely due to differences in semantics, elaboration and functionality between SNS. Therefore, this paper proposes that the policies of SNS already share attributes, indicating the feasibility of standardization and five recommendations are made to begin facilitating this, based on the findings of the investigation.

AtPIN: Arabidopsis thaliana Protein Interaction Network

Background: Protein-protein interactions (PPIs) constitute one of the most crucial conditions to sustain life in living organisms. To study PPI in Arabidopsis thaliana we have developed AtPIN, a database and web interface for searching and building interaction networks based on publicly available protein-protein interaction datasets. Description: All interactions were divided into experimentally demonstrated or predicted. The PPIs in the AtPIN database present a cellular compartment classification (C(3)) which divides the PPI into 4 classes according to its interaction evidence and subcellular localization. It has been shown in the literature that a pair of genuine interacting proteins are generally expected to have a common cellular role and proteins that have common interaction partners have a high chance of sharing a common function. In AtPIN, due to its integrative profile, the reliability index for a reported PPI can be postulated in terms of the proportion of interaction partners that two proteins have in common. For this, we implement the Functional Similarity Weight (FSW) calculation for all first level interactions present in AtPIN database. In order to identify target proteins of cytosolic glutamyl-tRNA synthetase (Cyt-gluRS) (AT5G26710) we combined two approaches, AtPIN search and yeast two-hybrid screening. Interestingly, the proteins glutamine synthetase (AT5G35630), a disease resistance protein (AT3G50950) and a zinc finger protein (AT5G24930), which has been predicted as target proteins for Cyt-gluRS by AtPIN, were also detected in the experimental screening. Conclusions: AtPIN is a friendly and easy-to-use tool that aggregates information on Arabidopsis thaliana PPIs, ontology, and sub-cellular localization, and might be a useful and reliable strategy to map protein-protein interactions in Arabidopsis. AtPIN can be accessed at http://bioinfo.esalq.usp.br/atpin.

Inter-subband redundancy prediction using neural network for video coding

High performance video codec is mandatory for multimedia applications such as video-on-demand and video conferencing. Recent research has proposed numerous video coding techniques to meet the requirement in bandwidth, delay, loss and Quality-of-Service (QoS). In this paper, we present our investigations on inter-subband self-similarity within the wavelet-decomposed video frames using neural networks, and study the performance of applying the spatial network model to all video frames over time. The goal of our proposed method is to restore the highest perceptual quality for video transmitted over a highly congested network. Our contributions in this paper are: (1) A new coding model with neural network based, inter-subband redundancy (ISR) prediction for video coding using wavelet (2) The performance of 1D and 2D ISR prediction, including multiple levels of wavelet decompositions. Our result shows a short-term quality enhancement may be obtained using both 1D and 2D ISR prediction.

Evolution of the gene regulatory network controlling flower dorsoventral asymmetry

Tese de Doutoramento em Biologia de Plantas.

Quantifying network properties in multi-electrode recordings: spatiotemporal characterization and inter-trial variation of evoked gamma oscillations in mouse somatosensory cortex in vitro.

Linking the structural connectivity of brain circuits to their cooperative dynamics and emergent functions is a central aim of neuroscience research. Graph theory has recently been applied to study the structure-function relationship of networks, where dynamical similarity of different nodes has been turned into a "static" functional connection. However, the capability of the brain to adapt, learn and process external stimuli requires a constant dynamical functional rewiring between circuitries and cell assemblies. Hence, we must capture the changes of network functional connectivity over time. Multi-electrode array data present a unique challenge within this framework. We study the dynamics of gamma oscillations in acute slices of the somatosensory cortex from juvenile mice recorded by planar multi-electrode arrays. Bursts of gamma oscillatory activity lasting a few hundred milliseconds could be initiated only by brief trains of electrical stimulations applied at the deepest cortical layers and simultaneously delivered at multiple locations. Local field potentials were used to study the spatio-temporal properties and the instantaneous synchronization profile of the gamma oscillatory activity, combined with current source density (CSD) analysis. Pair-wise differences in the oscillation phase were used to determine the presence of instantaneous synchronization between the different sites of the circuitry during the oscillatory period. Despite variation in the duration of the oscillatory response over successive trials, they showed a constant average power, suggesting that the rate of expenditure of energy during the gamma bursts is consistent across repeated stimulations. Within each gamma burst, the functional connectivity map reflected the columnar organization of the neocortex. Over successive trials, an apparently random rearrangement of the functional connectivity was observed, with a more stable columnar than horizontal organization. This work reveals new features of evoked gamma oscillations in developing cortex.

Toxoplasma gondii: further studies on the subpellicular network

The association of the pellicle with cytoskeletal elements in Toxoplasma gondii allows this parasite to maintain its mechanical integrity and makes possible its gliding motility and cell invasion. The inner membrane complex (IMC) resembles the flattened membrane sacs observed in free-living protozoa and these sacs have been found to associate with cytoskeletal proteins such as articulins. We used immunofluorescence microscopy to characterise the presence and distribution of plateins, a sub-family of articulins, in T. gondii tachyzoites. A dispersed labelling of the whole protozoan body was observed. Electron microscopy of detergent-extracted cells revealed the presence of a network of 10 nm filaments distributed throughout the parasite. These filaments were labelled with anti-platein antibodies. Screening the sequenced T. gondii genome, we obtained the sequence of an IMC predicted protein with 25% identity and 42% similarity to the platein isoform alpha 1 present in Euplotes aediculatus, but with 42% identity and 55% similarity to that found in Euglena gracilis, suggesting strong resemblance to articulins.

Self-similarity of complex networks and hidden metric spaces

We demonstrate that the self-similarity of some scale-free networks with respect to a simple degree-thresholding renormalization scheme finds a natural interpretation in the assumption that network nodes exist in hidden metric spaces. Clustering, i.e., cycles of length three, plays a crucial role in this framework as a topological reflection of the triangle inequality in the hidden geometry. We prove that a class of hidden variable models with underlying metric spaces are able to accurately reproduce the self-similarity properties that we measured in the real networks. Our findings indicate that hidden geometries underlying these real networks are a plausible explanation for their observed topologies and, in particular, for their self-similarity with respect to the degree-based renormalization.

The electricity distribution network in Saint-Petersburg area and benchmark between Saint-Petersburg and City of Stockholm related distribution companies' performance

The main objective of the Thesis is the description of the electricity distribution networks in Saint-Petersburg area and Stockholm as well. Main similarity and differences in the construction and technicalperformance are presented in the study. Present and future development and investment into the electricity distribution network of OJSC Lenenergo are viewed. The Thesis presents the overview of the power industry reform in Russia. The current state of the electricity distribution sector is described. The study views the participation of the foreign investor "Fortum Power and Heat Oy" inthe development and management of the OJSC Lenenergo. Benchmark comparison of the prices and tangible assets of the main electricity distribution companies in Saint-Petersburg and Stockholm areas is done.

Comparison of classification ability of hyperball algorithms to neural network and k-nearest neighbour algorithms

The main focus of this thesis is to evaluate and compare Hyperbalilearning algorithm (HBL) to other learning algorithms. In this work HBL is compared to feed forward artificial neural networks using back propagation learning, K-nearest neighbor and 103 algorithms. In order to evaluate the similarity of these algorithms, we carried out three experiments using nine benchmark data sets from UCI machine learning repository. The first experiment compares HBL to other algorithms when sample size of dataset is changing. The second experiment compares HBL to other algorithms when dimensionality of data changes. The last experiment compares HBL to other algorithms according to the level of agreement to data target values. Our observations in general showed, considering classification accuracy as a measure, HBL is performing as good as most ANn variants. Additionally, we also deduced that HBL.:s classification accuracy outperforms 103's and K-nearest neighbour's for the selected data sets.

Shape classification using complex network and Multi-scale Fractal Dimension

Shape provides one of the most relevant information about an object. This makes shape one of the most important visual attributes used to characterize objects. This paper introduces a novel approach for shape characterization, which combines modeling shape into a complex network and the analysis of its complexity in a dynamic evolution context. Descriptors computed through this approach show to be efficient in shape characterization, incorporating many characteristics, such as scale and rotation invariant. Experiments using two different shape databases (an artificial shapes database and a leaf shape database) are presented in order to evaluate the method. and its results are compared to traditional shape analysis methods found in literature. (C) 2009 Published by Elsevier B.V.

Transient stability analysis of electrical power systems using a neural network based on fuzzy ARTMAP

This work presents a methodology to analyze transient stability for electric energy systems using artificial neural networks based on fuzzy ARTMAP architecture. This architecture seeks exploring similarity with computational concepts on fuzzy set theory and ART (Adaptive Resonance Theory) neural network. The ART architectures show plasticity and stability characteristics, which are essential qualities to provide the training and to execute the analysis. Therefore, it is used a very fast training, when compared to the conventional backpropagation algorithm formulation. Consequently, the analysis becomes more competitive, compared to the principal methods found in the specialized literature. Results considering a system composed of 45 buses, 72 transmission lines and 10 synchronous machines are presented. © 2003 IEEE.

An improved interolog mapping-based computational prediction of protein protein interactions with increased network coverage

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)