Lovasz theta function, SVMs and Finding Dense Subgraphs

In this paper we establish that the Lovasz theta function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM-theta graphs, on which Lovasz theta function can be approximated well by a Support vector machine (SVM). We show that Erdos-Renyi random G(n, p) graphs are SVM-theta graphs for log(4)n/n <= p < 1. Even if we embed a large clique of size Theta(root np/1-p) in a G(n, p) graph the resultant graph still remains a SVM-theta graph. This immediately suggests an SVM based algorithm for recovering a large planted clique in random graphs. Associated with the theta function is the notion of orthogonal labellings. We introduce common orthogonal labellings which extends the idea of orthogonal labellings to multiple graphs. This allows us to propose a Multiple Kernel learning (MKL) based solution which is capable of identifying a large common dense subgraph in multiple graphs. Both in the planted clique case and common subgraph detection problem the proposed solutions beat the state of the art by an order of magnitude.

Substitution-Modulated Anticancer Activity of Half-Sandwich Ruthenium(II) Complexes with Heterocyclic Ancillary Ligands

Ten new organometallic half-sandwich ruthenium complexes with heterocyclic ligands have been synthesized (H1-H10). The substituents on the ancillary heterocyclic ligands were varied to understand the effect of substitution on anticancer activity. The crystallographic characterization of five complexes confirms that they adopt three-legged piano-stool structures and are stabilized by intramolecular hydrogen bonding. Complexes H2 and H3 also exhibit halogen bonding in the solid state. In aqueous media, the complexes form dinuclear ruthenium species. Complex H1 with a noncytotoxic heterocycle, 6-fluoro-2-mercaptobenzothiazole, and complex H11 with the unsubstituted 2-mercaptobenzothiazole are the most active against A2780 and KB cell lines. The substitution of the H atoms on the ancillary ligand with Cl or Br atoms leads to a decrease in the anticancer activity. With the exception of fluorine-substituted H5, the complexes with mercaptobenzoxazole (H6-H9) are inactive against all of the tested cell lines. Ruthenium complexes with mercaptonaphthimidazole (H10) and mercaptobenzimidazole (H13) do not show any anticancer activity. The active complexes show a biphasic melting curve when incubated with calf thymus (CT) DNA. These complexes only inhibit thioredoxin reductase (TrxR) enzyme activity to a small extent. The substitution of hydrogen atoms with fluorine atoms in the aromatic heterocyclic ligands on organometallic half-sandwich ruthenium complexes has the most beneficial effect on their anticancer activity.