A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.

Functional analysis of String/CDC25 phosphatase in post-mitotic neurons

Cell cycle and differentiation are two highly coordinated processes during organ development. Recent studies have demonstrated that core cell cycle regulators also play cell cycle-independent functions in post-mitotic neurons, and are essential for the maintenance of neuronal homeostasis. CDC25 phosphatases are well-established CDK activators and their activity is mainly associated to proliferating tissues. The expression and activity of mammalian CDC25s has been reported in adult brains. However, their physiological relevance and the potential substrates in a non-proliferative context have never been addressed. string (stg) encodes the Drosophila CDC25 homolog. Previous studies from our group showed that stg is expressed in photoreceptors (PRs) and in lamina neurons, which are two differentiated cell types that compose the fly visual system. The aims of this work are to uncover the function of stg and to identify its potential neuronal substrates, using the Drosophila visual system as a model. To gain insight into the function of stg in a non-dividing context we used the GAL4/UAS system to promote downregulation of stg in PR-neurons, through the use of an RNAi transgene. The defects caused by stg loss-of-function were evaluated in the developing eye imaginal disc by immunofluorescence, and during adult stages by scanning electron microscopy. This genetic approach was combined with a specific proteomic method, two-dimensional difference gel electrophoresis (2D-DIGE), to identify the potential substrates in PR-cells. Our results showed that stg downregulation in PRs affects the well-patterned retina organization, inducing the loss of apical maintenance of PR-nuclei on the eye disc, and ommatidia disorganization. We also detected an abnormal accumulation of cytoskeletal proteins and a disruption of the axon structure. As a consequence, the projection of PR-axons into the lamina and medulla neuropils of the optic lobe was impaired. Upon stg downregulation, we also detected that PR-cells accumulate Cyclin B. Although the rough eye phenotype observed upon stg downregulation suggests neurodegeneration, we did not detect neuronal death during larval stages, suggesting that it likely occurs during pupal stages or during adulthood. By 2D-DIGE, we identified seven proteins which were differentially expressed upon stg downregulation, and are potential neuronal substrates of Stg. Altogether, our observations suggest that Stg phosphatase plays an essential role in the Drosophila visual system neurons, regulating several cell components and processes in order to ensure their homeostasis.