Mathematical Programming Models for Influence Maximization on Social Networks

In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.

Integer Linear Programming for Sequence Problems: A general approach to reduce the problem size

Sequence problems belong to the most challenging interdisciplinary topics of the actuality. They are ubiquitous in science and daily life and occur, for example, in form of DNA sequences encoding all information of an organism, as a text (natural or formal) or in form of a computer program. Therefore, sequence problems occur in many variations in computational biology (drug development), coding theory, data compression, quantitative and computational linguistics (e.g. machine translation). In recent years appeared some proposals to formulate sequence problems like the closest string problem (CSP) and the farthest string problem (FSP) as an Integer Linear Programming Problem (ILPP). In the present talk we present a general novel approach to reduce the size of the ILPP by grouping isomorphous columns of the string matrix together. The approach is of practical use, since the solution of sequence problems is very time consuming, in particular when the sequences are long.

Constraint Programming-based Job Dispatching for Modern HPC Applications

A High-Performance Computing job dispatcher is a critical software that assigns the finite computing resources to submitted jobs. This resource assignment over time is known as the on-line job dispatching problem in HPC systems. The fact the problem is on-line means that solutions must be computed in real-time, and their required time cannot exceed some threshold to do not affect the normal system functioning. In addition, a job dispatcher must deal with a lot of uncertainty: submission times, the number of requested resources, and duration of jobs. Heuristic-based techniques have been broadly used in HPC systems, at the cost of achieving (sub-)optimal solutions in a short time. However, the scheduling and resource allocation components are separated, thus generates a decoupled decision that may cause a performance loss. Optimization-based techniques are less used for this problem, although they can significantly improve the performance of HPC systems at the expense of higher computation time. Nowadays, HPC systems are being used for modern applications, such as big data analytics and predictive model building, that employ, in general, many short jobs. However, this information is unknown at dispatching time, and job dispatchers need to process large numbers of them quickly while ensuring high Quality-of-Service (QoS) levels. Constraint Programming (CP) has been shown to be an effective approach to tackle job dispatching problems. However, state-of-the-art CP-based job dispatchers are unable to satisfy the challenges of on-line dispatching, such as generate dispatching decisions in a brief period and integrate current and past information of the housing system. Given the previous reasons, we propose CP-based dispatchers that are more suitable for HPC systems running modern applications, generating on-line dispatching decisions in a proper time and are able to make effective use of job duration predictions to improve QoS levels, especially for workloads dominated by short jobs.

High-resolution Transcript Profiling Of The Atypical Biotrophic Interaction Between Theobroma Cacao And The Fungal Pathogen Moniliophthora Perniciosa.

Witches' broom disease (WBD), caused by the hemibiotrophic fungus Moniliophthora perniciosa, is one of the most devastating diseases of Theobroma cacao, the chocolate tree. In contrast to other hemibiotrophic interactions, the WBD biotrophic stage lasts for months and is responsible for the most distinctive symptoms of the disease, which comprise drastic morphological changes in the infected shoots. Here, we used the dual RNA-seq approach to simultaneously assess the transcriptomes of cacao and M. perniciosa during their peculiar biotrophic interaction. Infection with M. perniciosa triggers massive metabolic reprogramming in the diseased tissues. Although apparently vigorous, the infected shoots are energetically expensive structures characterized by the induction of ineffective defense responses and by a clear carbon deprivation signature. Remarkably, the infection culminates in the establishment of a senescence process in the host, which signals the end of the WBD biotrophic stage. We analyzed the pathogen's transcriptome in unprecedented detail and thereby characterized the fungal nutritional and infection strategies during WBD and identified putative virulence effectors. Interestingly, M. perniciosa biotrophic mycelia develop as long-term parasites that orchestrate changes in plant metabolism to increase the availability of soluble nutrients before plant death. Collectively, our results provide unique insight into an intriguing tropical disease and advance our understanding of the development of (hemi)biotrophic plant-pathogen interactions.

Relationship between birthweight and arterial elasticity in childhood

There is a considerable debate about the potential influence of fetal programming on cardiovascular diseases in adulthood. In the present prospective epidemiological cohort study, the relationship between birthweight and arterial elasticity in 472 children between 5 and 8 years of age was assessed. LAEI (large artery elasticity index), SAEI (small artery elasticity index) and BP (blood pressure) were assessed using the HDI/PulseWave CR-2000 CardioVascular Profiling System. Blood concentrations of glucose, total cholesterol and its fractions [LDL (low-density lipoprotein)-cholesterol and HDL (high-density lipoprotein)-cholesterol] and triacylglycerols (triglycerides) were determined by automated enzymatic methods. Insulin was assessed by a chemiluminescent method, insulin resistance by HOMA (homoeostasis model assessment) and CRP (C-reactive protein) by immunonephelometry. Two linear regression models were applied to investigate the relationship between the outcomes, LAEI and SAEI, and the following variables: birthweight, gestational age, glucose, LDL-cholesterol, HDL-cholesterol, triacylglycerols, insulin, CRP, HOMA, age, gender, waist circumference, per capita income, SBP (systolic BP) and DBP (diastolic BP). LAEI was positively associated with birthweight (P=0.036), waist circumference (P<0.001) and age (P<0.001), and negatively associated with CRP (P=0.024) and SBP (P<0.001). SAEI was positively associated with birthweight (P=0.04), waist circumference (P=0.001) and age (P<0.001), and negatively associated with DBP (P<0.001). Arterial elasticity was decreased in apparently healthy children who had lower birthweights, indicating an earlier atherogenetic susceptibility to cardiovascular diseases in adolescence and adult life. Possible explanations for the results include changes in angiogenesis during critical phases of intrauterine life caused by periods of fetal growth inhibition and local haemodynamic anomalies

The relationship between cortisol concentrations in pregnancy and systemic vascular resistance in childhood

Objective. To assess the relationship between cortisol concentrations in the last trimester of pregnancy and systemic vascular resistance — SVR in childhood. Materials and methods. This study is part of a cohort involving 130 Brazilian pregnant women and their children, ages 5 to 7 years. Maternal cortisol was determined in saliva by an enzyme immunoassay utilizing the mean concentration of 9 samples of saliva (3 in each different day), collected at the same time, early in the morning. SVR was assessed by the HDI/PulseWave CR-2000 Cardiovascular Profiling System®. Socioeconomic and demographic characteristics and life style factors were determined by a questionnaire. The nutritional status of the women and children was assessed by the body mass index — BMI. The association between maternal cortisol and SVR in childhood was calculated by multivariate linear regression analysis. Results.There were statistically significant associations between maternal cortisol and SVR (p = 0.043) and BMI-z score of the children (p = 0.027), controlling for maternal BMI, birth weight, age, and gender of the children. Conclusion. As far as we know this is the first study in the literature assessing the association between cortisol concentrations in pregnancy and SVR in childhood. Overall, the data suggest that exposure to excess glucocorticoid in the prenatal period is associated to vascular complications in childhood, predisposing to cardiovascular diseases in later life

Architecture for machining process and production monitoring based in open computer numerical control

This paper proposes an architecture for machining process and production monitoring to be applied in machine tools with open Computer numerical control (CNC). A brief description of the advantages of using open CNC for machining process and production monitoring is presented with an emphasis on the CNC architecture using a personal computer (PC)-based human-machine interface. The proposed architecture uses the CNC data and sensors to gather information about the machining process and production. It allows the development of different levels of monitoring systems with mininium investment, minimum need for sensor installation, and low intrusiveness to the process. Successful examples of the utilization of this architecture in a laboratory environment are briefly described. As a Conclusion, it is shown that a wide range of monitoring solutions can be implemented in production processes using the proposed architecture.

Dynamical models for computer viruses propagation

Nowadays, digital computer systems and networks are the main engineering tools, being used in planning, design, operation, and control of all sizes of building, transportation, machinery, business, and life maintaining devices. Consequently, computer viruses became one of the most important sources of uncertainty, contributing to decrease the reliability of vital activities. A lot of antivirus programs have been developed, but they are limited to detecting and removing infections, based on previous knowledge of the virus code. In spite of having good adaptation capability, these programs work just as vaccines against diseases and are not able to prevent new infections based on the network state. Here, a trial on modeling computer viruses propagation dynamics relates it to other notable events occurring in the network permitting to establish preventive policies in the network management. Data from three different viruses are collected in the Internet and two different identification techniques, autoregressive and Fourier analyses, are applied showing that it is possible to forecast the dynamics of a new virus propagation by using the data collected from other viruses that formerly infected the network. Copyright (c) 2008 J. R. C. Piqueira and F. B. Cesar. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Transcriptional profiling reveals the expression of novel genes in response to various stimuli in the human dermatophyte Trichophyton rubrum

Background: Cutaneous mycoses are common human infections among healthy and immunocompromised hosts, and the anthropophilic fungus Trichophyton rubrum is the most prevalent microorganism isolated from such clinical cases worldwide. The aim of this study was to determine the transcriptional profile of T. rubrum exposed to various stimuli in order to obtain insights into the responses of this pathogen to different environmental challenges. Therefore, we generated an expressed sequence tag (EST) collection by constructing one cDNA library and nine suppression subtractive hybridization libraries. Results: The 1388 unigenes identified in this study were functionally classified based on the Munich Information Center for Protein Sequences (MIPS) categories. The identified proteins were involved in transcriptional regulation, cellular defense and stress, protein degradation, signaling, transport, and secretion, among other functions. Analysis of these unigenes revealed 575 T. rubrum sequences that had not been previously deposited in public databases. Conclusion: In this study, we identified novel T. rubrum genes that will be useful for ORF prediction in genome sequencing and facilitating functional genome analysis. Annotation of these expressed genes revealed metabolic adaptations of T. rubrum to carbon sources, ambient pH shifts, and various antifungal drugs used in medical practice. Furthermore, challenging T. rubrum with cytotoxic drugs and ambient pH shifts extended our understanding of the molecular events possibly involved in the infectious process and resistance to antifungal drugs.

Differential gene expression profiling in mucus glands of honey bee (Apis mellifera) drones during sexual maturation

The mating sign that each drone leaves when mating with a queen essentially consists of mucus gland proteins. We employed a Representational Difference Analysis (RDA) methodology to identify genes that are differentially expressed in mucus glands during sexual maturation of drones. The RDA library for mucus glands of newly emerged drones was more complex than that of 8 day-old drones, with matches to 20 predicted genes. Another 26 reads matched to the Apis genome but not to any predicted gene. Since these ESTs were located within ORFs they may represent novel honey bee genes, possibly fast evolving mucus gland proteins. In the RDA library for mucus glands of 8 day-old drones, most reads corresponded to a capsid protein of deformed wing virus, indicating high viral loads in these glands. The expression of two genes encoding venom allergens, acid phosphatase-1 and hyaluronidase, in drone mucus glands argues for their homology with the female venom glands, both associated with the reproductive system.

A score system for quality evaluation of RNA sequence tags: an improvement for gene expression profiling

Background: High-throughput molecular approaches for gene expression profiling, such as Serial Analysis of Gene Expression (SAGE), Massively Parallel Signature Sequencing (MPSS) or Sequencing-by-Synthesis (SBS) represent powerful techniques that provide global transcription profiles of different cell types through sequencing of short fragments of transcripts, denominated sequence tags. These techniques have improved our understanding about the relationships between these expression profiles and cellular phenotypes. Despite this, more reliable datasets are still necessary. In this work, we present a web-based tool named S3T: Score System for Sequence Tags, to index sequenced tags in accordance with their reliability. This is made through a series of evaluations based on a defined rule set. S3T allows the identification/selection of tags, considered more reliable for further gene expression analysis. Results: This methodology was applied to a public SAGE dataset. In order to compare data before and after filtering, a hierarchical clustering analysis was performed in samples from the same type of tissue, in distinct biological conditions, using these two datasets. Our results provide evidences suggesting that it is possible to find more congruous clusters after using S3T scoring system. Conclusion: These results substantiate the proposed application to generate more reliable data. This is a significant contribution for determination of global gene expression profiles. The library analysis with S3T is freely available at http://gdm.fmrp.usp.br/s3t/.S3T source code and datasets can also be downloaded from the aforementioned website.

Var transcription profiling of Plasmodium falciparum 3D7: assignment of cytoadherent phenotypes to dominant transcripts

Background: Cytoadherence of Plasmodium falciparum-infected red blood cells is mediated by var gene-encoded P. falciparum erythrocyte membrane protein-1 and host receptor preference depends in most cases on which of the 50-60 var genes per genome is expressed. Enrichment of phenotypically homogenous parasites by panning on receptor expressing cells is fundamental for the identification of the corresponding var transcript. Methods: P. falciparum 3D7 parasites were panned on several transfected CHO-cell lines and their var transcripts analysed by i) reverse transcription/PCR/cloning/sequencing using a universal DBL alpha specific oligonucleotide pair and ii) by reverse transcription followed by quantitative PCR using 57 different oligonucleotide pairs. Results: Each cytoadherence selected parasite line also adhered to untransfected CHO-745 cells and upregulation of the var gene PFD995/PFD1000c was consistently associated with cytoadherence to all but one CHO cell line. In addition, parasites panned on different CHO cell lines revealed candidate var genes which reproducibly associated to the respective cytoadherent phenotype. The transcription profile obtained by RT-PCR/cloning/sequencing differed significantly from that of RT-quantitative PCR. Conclusion: Transfected CHO cell lines are of limited use for the creation of monophenotypic cytoadherent parasite lines. Nevertheless, 3D7 parasites can be reproducibly selected for the transcription of different determined var genes without genetic manipulation. Most importantly, var transcription analysis by RT-PCR/cloning/sequencing may lead to erroneous interpretation of var transcription profiles.