A novel clustering approach and prediction of optimal number of clusters: global optimum search with enhanced positioning

Cluster analysis of genome-wide expression data from DNA microarray hybridization studies is a useful tool for identifying biologically relevant gene groupings (DeRisi et al. 1997; Weiler et al. 1997). It is hence important to apply a rigorous yet intuitive clustering algorithm to uncover these genomic relationships. In this study, we describe a novel clustering algorithm framework based on a variant of the Generalized Benders Decomposition, denoted as the Global Optimum Search (Floudas et al. 1989; Floudas 1995), which includes a procedure to determine the optimal number of clusters to be used. The approach involves a pre-clustering of data points to define an initial number of clusters and the iterative solution of a Linear Programming problem (the primal problem) and a Mixed-Integer Linear Programming problem (the master problem), that are derived from a Mixed Integer Nonlinear Programming problem formulation. Badly placed data points are removed to form new clusters, thus ensuring tight groupings amongst the data points and incrementing the number of clusters until the optimum number is reached. We apply the proposed clustering algorithm to experimental DNA microarray data centered on the Ras signaling pathway in the yeast Saccharomyces cerevisiae and compare the results to that obtained with some commonly used clustering algorithms. Our algorithm compares favorably against these algorithms in the aspects of intra-cluster similarity and inter-cluster dissimilarity, often considered two key tenets of clustering. Furthermore, our algorithm can predict the optimal number of clusters, and the biological coherence of the predicted clusters is analyzed through gene ontology.     

Extended Linial Hyperplane Arrangements for Root Systems and a Conjecture of Postnikov and Stanley

A hyperplane arrangement is said to satisfy the Riemann hypothesis if all roots of its characteristic polynomial have the same real part. This property was conjectured by Postnikov and Stanley for certain families of arrangements which are defined for any irreducible root system and was proved for the root system A _{n – 1}. The proof is based on an explicit formula [1, 2, 11] for the characteristic polynomial, which is of independent combinatorial significance. Here our previous derivation of this formula is simplified and extended to similar formulae for all but the exceptional root systems. The conjecture follows in these cases.     

Performance of convex underestimators in a branch-and-bound framework

The efficient determination of tight lower bounds in a branch-and-bound algorithm is crucial for the global optimization of models spanning numerous applications and fields. The global optimization method \(\alpha \)-branch-and-bound (\(\alpha \)BB, Adjiman et al. in Comput Chem Eng 22(9):1159–1179, 1998b, Comput Chem Eng 22(9):1137–1158, 1998a; Adjiman and Floudas in J Global Optim 9(1):23–40, 1996; Androulakis et al. J Global Optim 7(4):337–363, 1995; Floudas in Deterministic Global Optimization: Theory, Methods and Applications, vol. 37. Springer, Berlin, 2000; Maranas and Floudas in J Chem Phys 97(10):7667–7678, 1992, J Chem Phys 100(2):1247–1261, 1994a, J Global Optim 4(2):135–170, 1994), guarantees a global optimum with \(\epsilon \)-convergence for any \(\mathcal {C}^2\)-continuous function within a finite number of iterations via fathoming nodes of a branch-and-bound tree. We explored the performance of the \(\alpha \)BB method and a number of competing methods designed to provide tight, convex underestimators, including the piecewise (Meyer and Floudas in J Global Optim 32(2):221–258, 2005), generalized (Akrotirianakis and Floudas in J Global Optim 30(4):367–390, 2004a, J Global Optim 29(3):249–264, 2004b), and nondiagonal (Skjäl et al. in J Optim Theory Appl 154(2):462–490, 2012) \(\alpha \)BB methods, the Brauer and Rohn+E (Skjäl et al. in J Global Optim 58(3):411–427, 2014) \(\alpha \)BB methods, and the moment method (Lasserre and Thanh in J Global Optim 56(1):1–25, 2013). Using a test suite of 40 multivariate, box-constrained, nonconvex functions, the methods were compared based on the tightness of generated underestimators and the efficiency of convergence of a branch-and-bound global optimization algorithm.     

Integrated computational and experimental approach for lead optimization and design of compstatin variants with improved activity

A novel structure-activity-based combinatorial computational optimization methodology for the design of peptides that are candidates to become therapeutics is presented. This methodology has been successfully applied in the design of a 7-fold more active analogue, among other active analogues, in the case of the complement inhibitor compstatin. The main steps of the approach involve the availability of NMR-derived structural templates, combinatorial selection of sequences based on optimization of parametrized pairwise residue interaction potentials, prediction of fold stabilities using deterministic global optimization, and experimental validation with immunological activity measurements. This work is direct evidence that an integrated experimental and theoretical approach can make the engineering of compounds with enhanced immunological properties possible.