Precoloring Extension of Co-Meyniel Graphs

The pre-coloring extension problem consists, given a graph G and a set of nodes to which some colors are already assigned, in finding a coloring of G with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that “PrExt perfect” graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (“co-Artemis” graphs, which are “co-perfectly contractile” graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs. C.N.R.S. Final version received: January, 2007     

Staring at the Naked Goddess: Unraveling the Structure and Reactivity of Artemis Endonuclease Interacting with a DNA Double Strand

Artemis is an endonuclease responsible for breaking hairpin DNA strands during immune system adaptation and maturation as well as the processing of potentially toxic DNA lesions. Thus, Artemis may be an important target in the development of anticancer therapy, both for the sensitization of radiotherapy and for immunotherapy. Despite its importance, its structure has been resolved only recently, and important questions concerning the arrangement of its active center, the interaction with the DNA substrate, and the catalytic mechanism remain unanswered. In this contribution, by performing extensive molecular dynamic simulations, both classically and at the hybrid quantum mechanics/molecular mechanics level, we evidenced the stable interaction modes of Artemis with a model DNA strand. We also analyzed the catalytic cycle providing the free energy profile and key transition states for the DNA cleavage reaction.