Professor Regina Berretta

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.

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.

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.

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.