Professor Pablo Moscato

A large number of problems in business and consumer analytics have input graphs or networks. These mathematical entities have a long standing tradition in discrete applied mathematics and computer science. In many cases, they are the most natural means to represent some type of relationships in data. Consequently, a large number of solution methods based on heuristics and exact algorithms exist for problems that have graphs and/or networks as part of their input. While the number of possible applications of these techniques is not limited to problems in business and customer analytics, we have chosen to present some of them in a survey that would allow newcomers to the field of data science to create some familiarity with the key questions that motivate the area. We have also provided a survey on recent applications and new algorithmic approaches for data analytics. In addition we discuss issues related to the computational complexity of some problems associated with them. Other chapters of this section complement the discussion in this chapter with specific examples of interest or that could motivate new novel research direction and application.

The aim of this chapter is to present combinatorial optimization models and techniques for the analysis of microarray datasets. The chapter illustrates the application of a novel objective function that guides the search for high-quality solutions for sequential ordering of expression profiles. The approach is unsupervised and a metaheuristic method (a memetic algorithm) is used to provide high-quality solutions. For the problem of selecting discriminative groups of genes, we used a supervised method that has provided good results in a variety of datasets. This chapter illustrates the application of these models in an Alzheimer's disease microarray dataset. © 2008 Humana Press, a part of Springer Science+Business Media, LLC.

Because of the number of different architectures, numerous settings of their hyper-parameters and disparity among their sizes, it is difficult to equitably compare various deep neural network (DNN) architectures for sentence classification. Evolutionary algorithms are emerging as a popular method for the automatic selection of architectures and hyperparameters for DNNs whose generalisation performance is heavily impacted by such settings. Most of the work in this area is done in the image domain, leaving text analysis, another prominent application domain of deep learning, largely absent. Besides, literature presents conflicting claims regarding the superiority of one DNN architecture over others in the context of sentence classification. To address this issue, we propose a genetic algorithm (GA) for optimising the architectural and hyperparameter settings in different DNN types for sentence classification. To enable the representation of the wide variety of architectures and hyperparameters utilised in DNNs, we employed a generalised and flexible encoding scheme in our GA. Our study involves optimising two convolutional and three recurrent architectures to ensure a fair and unbiased evaluation of their performance. Furthermore, we explore the effects of using F1 score versus accuracy as a performance metric during evolutionary optimisation of those architectures. Our results, using ten datasets, show that, in general, the architectures and hyperparameters evolved using the F1 score tended to outperform those evolved using accuracy and in the case of CNN and BiLSTM the results were significant in statistical measures. Of the five architectures considered, the GA-evolved gated recurrent unit (GRU) performed the strongest overall, achieving good generalisation performance while using relatively few trainable parameters, establishing GRU as the preferred architecture for the sentence classification task. The optimised architectures exhibited comparable performance with the state-of-the-art, given the large difference in trainable parameters.

Motivated by the celebrated paper of Hooker (J Heuristics 1(1): 33¿42, 1995) published in the first issue of this journal, and by the relative lack of progress of both approximation algorithms and fixed-parameter algorithms for the classical decision and optimization problems related to covering edges by vertices, we aimed at developing an approach centered in augmenting our intuition about what is indeed needed. We present a case study of a novel design methodology by which algorithm weaknesses will be identified by computer-based and fixed-parameter tractable algorithmic challenges on their performance. Comprehensive benchmarkings on all instances of small size then become an integral part of the design process. Subsequent analyses of cases where human intuition ¿fails¿, supported by computational testing, will then lead to the development of new methods by avoiding the traps of relying only on human perspicacity and ultimately will improve the quality of the results. Consequently, the computer-aided design process is seen as a tool to augment human intuition. It aims at accelerating and foster theory development in areas such as graph theory and combinatorial optimization since some safe reduction rules for pre-processing can be mathematically proved via theorems. This approach can also lead to the generation of new interesting heuristics. We test our ideas with a fundamental problem in graph theory that has attracted the attention of many researchers over decades, but for which seems it seems to be that a certain stagnation has occurred. The lessons learned are certainly beneficial, suggesting that we can bridge the increasing gap between theory and practice by a more concerted approach that would fuel human imagination from a data-driven discovery perspective.

We present an approach for regression problems that employs analytic continued fractions as a novel representation. Comparative computational results using a memetic algorithm are reported in this work. Our experiments included fifteen other different machine learning approaches including five genetic programming methods for symbolic regression and ten machine learning methods. The comparison on training and test generalization was performed using 94 datasets of the Penn State Machine Learning Benchmark. The statistical tests showed that the generalization results using analytic continued fractions provide a powerful and interesting new alternative in the quest for compact and interpretable mathematical models for artificial intelligence.

Background: Immunotherapy has recently been proposed as a promising treatment to stop breast cancer (BrCa) progression and metastasis. However, there has been limited success in the treatment of BrCa with immune checkpoint inhibitors. This implies that BrCa tumors have other mechanisms to escape immune surveillance. While the kynurenine pathway (KP) is known to be a key player mediating tumor immune evasion and while there are several studies on the roles of the KP in cancer, little is known about KP involvement in BrCa. Methods: To understand how KP is regulated in BrCa, we examined the KP profile in BrCa cell lines and clinical samples (n = 1997) that represent major subtypes of BrCa (luminal, HER2-enriched, and triple-negative (TN)). We carried out qPCR, western blot/immunohistochemistry, and ultra-high pressure liquid chromatography on these samples to quantify the KP enzyme gene, protein, and activity, respectively. Results: We revealed that the KP is highly dysregulated in the HER2-enriched and TN BrCa subtype. Gene, protein expression, and KP metabolomic profiling have shown that the downstream KP enzymes KMO and KYNU are highly upregulated in the HER2-enriched and TN BrCa subtypes, leading to increased production of the potent immunosuppressive metabolites anthranilic acid (AA) and 3-hydroxylanthranilic acid (3HAA). Conclusions: Our findings suggest that KMO and KYNU inhibitors may represent new promising therapeutic targets for BrCa. We also showed that KP metabolite profiling can be used as an accurate biomarker for BrCa subtyping, as we successfully discriminated TN BrCa from other BrCa subtypes.

Background: Like it happens in other tumours, glioma cells co-evolve in a microenvironment consisting of bona fide tumour cells as well as a range of parenchymal cells, which produces numerous signalling molecules. Recently, the results of an in silico experiment suggested that a combination therapy that would target multiple key cytokines at the same time may be more effective for suppressing the growth of a tumour. The in silico experiments also showed that the optimal combination therapy is very much dependent on a patient¿s molecular profile. Method: In this work, we employ evolutionary algorithms for designing optimal combination therapy tailored to the patient¿s tumour microenvironment. Experiments were performed using a state-of-the-art glioma microenvironment model, capable of imitating many characteristics of human glioma development, and many virtual patient profiles. Conclusions: Results show that the therapies designed by the presented memetic algorithm were very effective in impeding tumour growth and were tailored to the patient¿s personal tumour microenvironment.

Up to 50% of multiple sclerosis (MS) patients do not respond to interferon-beta (IFN-ß) treatment and determination of response requires lengthy clinical follow-up of up to 2 years. Response predictive genetic markers would significantly improve disease management. We aimed to identify IFN-ß treatment response genetic marker(s) by performing a two-stage genome-wide association study (GWAS). The GWAS was carried out using data from 151 Australian MS patients from the ANZgene/WTCCC2 MS susceptibility GWAS (responder (R)=51, intermediate responders=24 and non-responders (NR)=76). Of the single-nucleotide polymorphisms (SNP) that were validated in an independent group of 479 IFN-ß-treated MS patients from Australia, Spain and Italy (R=273 and NR=206), eight showed evidence of association with treatment response. Among the replicated associations, the strongest was observed for FHIT (Fragile Histidine Triad; combined P-value 6.74 × 106) and followed by variants in GAPVD1 (GTPase activating protein and VPS9 domains 1; combined P-value 5.83 × 10 5) and near ZNF697 (combined P-value 8.15 × 10 5).

The feature selection problem aims to choose a subset of a given set of features that best represents the whole in a particular aspect, preserving the original semantics of the variables on the given samples and classes. In 2004, a new approach to perform feature selection was proposed. It was based on a NP-complete combinatorial optimisation problem called ((Formula presented.))-k-feature set problem. Although effective for many practical cases, which made the approach an important feature selection tool, the only existing solution method, proposed on the original paper, was found not to work well for several instances. Our work aims to cover this gap found on the literature, quickly obtaining high quality solutions for the instances that existing approach can not solve. This work proposes a heuristic based on the greedy randomised adaptive search procedure and tabu search to address this problem; and benchmark instances to evaluate its performance. The computational results show that our method can obtain high quality solutions for both real and the proposed artificial instances and requires only a fraction of the computational resources required by the state of the art exact and heuristic approaches which use mixed integer programming models.

Multiple Sclerosis (MS) is a chronic inflammatory demyelinating disease of the central nervous system. The risk of developing MS is strongly influenced by genetic predisposition, and over 100 loci have been established as associated with susceptibility. However, the biologically relevant variants underlying disease risk have not been defined for the vast majority of these loci, limiting the power of these genetic studies to define new avenues of research for the development of MS therapeutics. It is therefore crucial that candidate MS susceptibility loci are carefully investigated to identify the biological mechanism linking genetic polymorphism at a given gene to the increased chance of developing MS. MERTK has been established as an MS susceptibility gene and is part of a family of receptor tyrosine kinases known to be involved in the pathogenesis of demyelinating disease. In this study we have refined the association of MERTK with MS risk to independent signals from both common and low frequency variants. One of the associated variants was also found to be linked with increased expression of MERTK in monocytes and higher expression of MERTK was associated with either increased or decreased risk of developing MS, dependent upon HLA-DRB1*15:01 status. This discordant association potentially extended beyond MS susceptibility to alterations in disease course in established MS. This study provides clear evidence that distinct polymorphisms within MERTK are associated with MS susceptibility, one of which has the potential to alter MERTK transcription, which in turn can alter both susceptibility and disease course in MS patients.

In spite of the fact that many simplified model variants of protein structure prediction have been widely studied in the past years, few attention has been given to discrete models with side chains, for which there is no specific benchmark. In this paper, we propose an integer programming model for the 3D-HP side chain protein structure prediction problem. The model accounts for the energy resulting from all types of interactions, between pairs of backbone elements, hydrophilic side chains and hydrophobic side chains. Three sets of instances, modified from the literature, were used in the experiments, and the maximum number of non-local hydrophobic contact was found using the ILOG CPLEX optimization package. We offer the optimal solution found for several instances of the benchmark. It is expected that the mathematical model allow further studies of the protein structure prediction with side chains and may, for some cases, provide new optimal values or new bounds that would rekindle the interest to this fascinating problem domain.

Classification of datasets with imbalanced sample distributions has always been a challenge. In general, a popular approach for enhancing classification performance is the construction of an ensemble of classifiers. However, the performance of an ensemble is dependent on the choice of constituent base classifiers. Therefore, we propose a genetic algorithm-based search method for finding the optimum combination from a pool of base classifiers to form a heterogeneous ensemble. The algorithm, called GA-EoC, utilises 10 fold-cross validation on training data for evaluating the quality of each candidate ensembles. In order to combine the base classifiers decision into ensemble's output, we used the simple and widely used majority voting approach. The proposed algorithm, along with the random sub-sampling approach to balance the class distribution, has been used for classifying class-imbalanced datasets. Additionally, if a feature set was not available, we used the (a, ß) - k Feature Set method to select a better subset of features for classification. We have tested GA-EoC with three benchmarking datasets from the UCI-Machine Learning repository, one Alzheimer's disease dataset and a subset of the PubFig database of Columbia University. In general, the performance of the proposed method on the chosen datasets is robust and better than that of the constituent base classifiers and many other well-known ensembles. Based on our empirical study we claim that a genetic algorithm is a superior and reliable approach to heterogeneous ensemble construction and we expect that the proposed GA-EoC would perform consistently in other cases.

Human genetic and animal studies have implicated the costimulatory molecule CD40 in the development of multiple sclerosis (MS). We investigated the cell specific gene and protein expression variation controlled by the CD40 genetic variant(s) associated with MS, i.e. the T-allele at rs1883832. Previously we had shown that the risk allele is expressed at a lower level in whole blood, especially in people with MS. Here, we have defined the immune cell subsets responsible for genotype and disease effects on CD40 expression at the mRNA and protein level. In cell subsets in which CD40 is most highly expressed, B lymphocytes and dendritic cells, the MS-associated risk variant is associated with reduced CD40 cell-surface protein expression. In monocytes and dendritic cells, the risk allele additionally reduces the ratio of expression of full-length versus truncated CD40 mRNA, the latter encoding secreted CD40. We additionally show that MS patients, regardless of genotype, express significantly lower levels of CD40 cell-surface protein compared to unaffected controls in B lymphocytes. Thus, both genotype-dependent and independent down-regulation of cell-surface CD40 is a feature of MS. Lower expression of a co-stimulator of T cell activation, CD40, is therefore associated with increased MS risk despite the same CD40 variant being associated with reduced risk of other inflammatory autoimmune diseases. Our results highlight the complexity and likely individuality of autoimmune pathogenesis, and could be consistent with antiviral and/or immunoregulatory functions of CD40 playing an important role in protection from MS.

Objective To study the influence of adjuvant androgen suppression and bisphosphonates on incident vertebral and non-spinal fracture rates and bone mineral density (BMD) in men with locally advanced prostate cancer. Patients and Methods Between 2003 and 2007, 1071 men with locally advanced prostate cancer were randomly allocated, using a 2 × 2 trial design, to 6 months i.m. leuprorelin (androgen suppression [AS]) before radiotherapy alone ± 12 months additional leuprorelin ± 18 months zoledronic acid (ZdA), commencing at randomization. The main endpoint was incident thoraco-lumbar vertebral fractures, which were assessed radiographically at randomization and at 3 years, then reassessed by centralized review. Subsidiary endpoints included incident non-spinal fractures, which were documented throughout follow-up, and BMD, which was measured in 222 subjects at baseline, 2 years and 4 years. Results Incident vertebral fractures at 3 years were observed in 132 subjects. Their occurrence was not increased by 18 months' AS, nor reduced by ZdA. Incident non-spinal fractures occurred in 72 subjects and were significantly related to AS duration but not to ZdA. Osteopenia and osteoporosis prevalence rates at baseline were 23.4 and 1.4%, respectively, at the hip. Treatment for 6 and 18 months with AS caused significant reductions in hip BMD at 2 and 4 years (P < 0.01) and ZdA prevented these losses at both time points. Conclusion In an AS-naïve population, 18 months of ZdA treatment prevented the sustained BMD losses caused by 18 months of AS treatment; however, the study power was insufficient to show that AS duration or ZdA influenced vertebral fracture rates. © 2013 The Authors. BJU International © 2013 BJU International.

'Neuroinflammation' has become a widely applied term in the basic and clinical neurosciences but there is no generally accepted neuropathological tissue correlate. Inflammation, which is characterized by the presence of perivascular infiltrates of cells of the adaptive immune system, is indeed seen in the central nervous system (CNS) under certain conditions. Authors who refer to microglial activation as neuroinflammation confuse this issue because autoimmune neuroinflammation serves as a synonym for multiple sclerosis, the prototypical inflammatory disease of the CNS. We have asked the question whether a data-driven, unbiased in silico approach may help to clarify the nomenclatorial confusion. Specifically, we have examined whether unsupervised analysis of microarray data obtained from human cerebral cortex of Alzheimer's, Parkinson's and schizophrenia patients would reveal a degree of relatedness between these diseases and recognized inflammatory conditions including multiple sclerosis. Our results using two different data analysis methods provide strong evidence against this hypothesis demonstrating that very different sets of genes are involved. Consequently, the designations inflammation and neuroinflammation are not interchangeable. They represent different categories not only at the histophenotypic but also at the transcriptomic level. Therefore, non-autoimmune neuroinflammation remains a term in need of definition. © 2014 Springer-Verlag Berlin Heidelberg.

Schizophrenia is an idiopathic mental disorder with a heritable component and a substantial public health impact. We conducted a multi-stage genome-wide association study (GWAS) for schizophrenia beginning with a Swedish national sample (5,001 cases and 6,243 controls) followed by meta-Analysis with previous schizophrenia GWAS (8,832 cases and 12,067 controls) and finally by replication of SNPs in 168 genomic regions in independent samples (7,413 cases, 19,762 controls and 581 parent-offspring trios). We identified 22 loci associated at genome-wide significance; 13 of these are new, and 1 was previously implicated in bipolar disorder. Examination of candidate genes at these loci suggests the involvement of neuronal calcium signaling. We estimate that 8,300 independent, mostly common SNPs (95% credible interval of 6,300-10,200 SNPs) contribute to risk for schizophrenia and that these collectively account for at least 32% of the variance in liability. Common genetic variation has an important role in the etiology of schizophrenia, and larger studies will allow more detailed understanding of this disorder. © 2013 Nature America, Inc. All rights reserved.

We conducted an association study across the human leukocyte antigen (HLA) complex to identify loci associated with multiple sclerosis (MS). Comparing 1927 SNPs in 1618 MS cases and 3413 controls of European ancestry, we identified seven SNPs that were independently associated with MS conditional on the others (each P=4×10-6). All associations were significant in an independent replication cohort of 2212 cases and 2251 controls (P=0:001) and were highly significant in the combined dataset (P=6 × 10-8). The associated SNPs included proxies for HLA-DRB1*15:01 and HLA-DRB1*03:01, and SNPs in moderate linkage disequilibrium (LD) with HLA-A*02:01, HLA-DRB1*04:01 and HLA-DRB1*13:03. We also found a strong association with rs9277535 in the class II gene HLA-DPB1 (discovery set P = 9 × 10-9, replication set P = 7 × 10-4, combined P=2 × 10-10). HLA-DPB1 is located centromeric of the more commonly typed class II genes HLA-DRB1, -DQA1 and -DQB1. It is separated from these genes by a recombination hotspot, and the association is not affected by conditioning on genotypes at DRB1, DQA1 and DQB1. Hence rs9277535 represents an independent MS-susceptibility locus of genome-wide significance. It is correlated with the HLA-DPB1*03:01 allele, which has been implicated previously in MS in smaller studies. Further genotyping in large datasets is required to confirm and resolve this association. © 2010 Field et al.

This paper addresses several issues related to the approximate solution of the Single Machine Scheduling problem with sequence-dependent setup times using metaheuristic methods. Instances with known optimal solution are solved using a memetic algorithm and a multiple start approach. A fitness landscape analysis is also conducted on a subset of instances to understand the behavior of the two approaches during the optimization process. We also present a novel way to create instances with known optimal solutions from the optimally solved asymmetric travelling salesman problem (ATSP) instances. Finally we argue for the test set of instances to be used in future works as a convenient performance benchmark.

We show how, by a constructive process, we can generate arbitrarily large instances of the Traveling Salesman Problem (TSP) using standard fractals such as those of Peano, Koch, or Sierpinski. We show that optimal solutions for these TSPs can be known a priori, and thus, they provide us with new nontrivial TSP instances offering the possibility of testing heuristics well beyond the scope of testbed instances which have been solved by exact numerical methods. Furthermore, instances may be constructed with different features, for example, with different fractal dimensions. To four of these fractal TSPs we apply three standard constructive heuristics, namely Multiple Fragment, Nearest Neighbor, and Farthest Insertion from Convex-Hull, which have efficient general-purpose implementations. The ability of different algorithms to solve these different fractal TSPs gives us significant insight into the nature of TSP heuristics in a way which is complementary to approaches such as worst-case or average-case analysis. © 1998 INFORMS.

The Quadratic Assignment Problem (QAP) is a well-studied, NP-Hard combinatorial optimization problem with practical applications in timetabling, scheduling, logistics, circuit design and data visualisation, to name a few. In this paper a Memetic Algorithm is described, which utilises a ternary tree structure for its population and uses a Tabu Search as its local improvement strategy. The Tabu Search is also run in parallel, significantly reducing the running time of the algorithm. The ternary tree not only stores the individuals within the population, but the inherent structure within this tree also determines parent selection for crossover. A small number of rules, which include fitness and diversity-based rules, govern whether a newly produced solution remains within the population, or whether it is discarded. These key features are tested against a basic Memetic Algorithm using the instances from the QAP library, QAPLIB, and have shown to significantly improve the performance in terms of both time and solution quality. The best version of the Memetic Algorithm is shown to perform competitively with some of the state-of-the-art algorithms for the QAP from the literature, with grid-based and real-life instances shown to be solved very efficiently and effectively by the presented algorithms.

In this work, we incorporate new edges from a paracliqueidentification approach to the output of theMST-kNN graph partitioning method. We present a statistical analysis of the results on a dataset originated from a computational linguistic study of 84 Indo-European languages. We also present results from a computational stylistic study of 168 plays of the Shakespearean era. For the latter, results of the Kruskal- Wallis test 1 (observed vs. all permutations) showed a p-value of a 1.62E- 11 and a Wilcoxon test a p-value of 8.1E-12. Overall, our results clearly show in both cases that the modified approach provides statistically more significant results than the use of the MST-kNN alone, thus providing a highly-scalable alternative and statistically sound approach for data clustering.

We consider the problem of estimating the evolutionary history of a collection of organisms in terms of a phylogenetic tree. This is a hard combinatorial optimization problem for which different EA approaches are proposed and evaluated. Using two problem instances of different sizes, it is shown that an EA that directly encodes trees and uses ad-hoc operators performs better than several decoder-based EAs, but does not scale well with the problem size. A greedy-decoder EA provides the overall best results, achieving near 100%-success at a lower computational cost than the remaining approaches.