Abstract:
In most species, crossovers (COs) are essential for the accurate segregation of homologous chromosomes at the first meiotic division. Their number and location are tightly regulated. Here, we report a detailed, genome-wide characterization of the rate and localization of COs in Arabidopsis thaliana, in male and female meiosis. We observed dramatic differences between male and female meiosis which included: (i) genetic map length; 575 cM versus 332 cM respectively; (ii) CO distribution patterns: male CO rates were very high at both ends of each chromosome, whereas female CO rates were very low; (iii) correlations between CO rates and various chromosome features: female CO rates correlated strongly and negatively with GC content and gene density but positively with transposable elements (TEs) density, whereas male CO rates correlated positively with the CpG ratio. However, except for CpG, the correlations could be explained by the unequal repartition of these sequences along the Arabidopsis chromosome. For both male and female meiosis, the number of COs per chromosome correlates with chromosome size expressed either in base pairs or as synaptonemal complex length. Finally, we show that interference modulates the CO distribution both in male and female meiosis.

Abstract:
In many species, sex-related differences in crossover (CO) rates have been described at chromosomal and regional levels. In this study, we determined the CO distribution along the entire Arabidopsis thaliana Chromosome 4 (18 Mb) in male and female meiosis, using high density genetic maps built on large backcross populations (44 markers, >1,300 plants). We observed dramatic differences between male and female map lengths that were calculated as 88 cM and 52 cM, respectively. This difference is remarkably parallel to that between the total synaptonemal complex lengths measured in male and female meiocytes by immunolabeling of ZYP1 (a component of the synaptonemal complex). Moreover, CO landscapes were clearly different: in particular, at both ends of the map, male CO rates were higher (up to 4-fold the mean value), whereas female CO rates were equal or even below the chromosomal average. This unique material gave us the opportunity to perform a detailed analysis of CO interference on Chromosome 4 in male and female meiosis. The number of COs per chromosome and the distances between them clearly departs from randomness. Strikingly, the interference level (measured by coincidence) varied significantly along the chromosome in male meiosis and was correlated to the physical distance between COs. The significance of this finding on the relevance of current CO interference models is discussed.

Abstract:
The vast majority of meiotic recombination events (crossovers (COs) and non-crossovers (NCOs)) cluster in narrow hotspots surrounded by large regions devoid of recombinational activity. Here, using a new molecular approach in plants, called “pollen-typing”, we detected and characterized hundreds of CO and NCO molecules in two different hotspot regions in Arabidopsis thaliana. This analysis revealed that COs are concentrated in regions of a few kilobases where their rates reach up to 50 times the genome average. The hotspots themselves tend to cluster in regions less than 8 kilobases in size with overlapping CO distribution. Non-crossover (NCO) events also occurred in the two hotspots but at very different levels (local CO/NCO ratios of 1/1 and 30/1) and their track lengths were quite small (a few hundred base pairs). We also showed that the ZMM protein MSH4 plays a role in CO formation and somewhat unexpectedly we also found that it is involved in the generation of NCOs but with a different level of effect. Finally, factors acting in cis and in trans appear to shape the rate and distribution of COs at meiotic recombination hotspots.

Abstract:
We introduce and study a new optimization problem called Hyper Vertex Cover. This problem is a generalization of the standard vertex cover to hypergraphs: one seeks a configuration of particles with minimal density such that every hyperedge of the hypergraph contains at least one particle. It can also be used in important practical tasks, such as the Group Testing procedures where one wants to detect defective items in a large group by pool testing. Using a Statistical Mechanics approach based on the cavity method, we study the phase diagram of the HVC problem, in the case of random regualr hypergraphs. Depending on the values of the variables and tests degrees different situations can occur: The HVC problem can be either in a replica symmetric phase, or in a one-step replica symmetry breaking one. In these two cases, we give explicit results on the minimal density of particles, and the structure of the phase space. These problems are thus in some sense simpler than the original vertex cover problem, where the need for a full replica symmetry breaking has prevented the derivation of exact results so far. Finally, we show that decimation procedures based on the belief propagation and the survey propagation algorithms provide very efficient strategies to solve large individual instances of the hyper vertex cover problem.

Abstract:
We study the dynamical evolution of a system with a phase space consisting of configurations with random energies. The dynamics we use is of Glauber type. It allows for some dynamical evolution ang aging even at very low temperatures, through the search of configurations with lower energies.

Abstract:
We study the off equilibrium dynamics of a mean field disordered systems which can be interpreted both as a long range interaction spin glass and as a particle in a random potential. The statics of this problem is well known and exhibits a low temperature spin glass phase with continuous replica symmetry breaking. We study the equations of off equilibrium dynamics with analytical and numerical methods. In the spin glass phase, we find that the usual equilibrium dynamics (observed when the observation time is much smaller than the waiting time) coexists with an aging regime. In this aging regime, we propose a solution implying a hierarchy of crossovers between the observation time and the waiting time.

Abstract:
We study matchings on sparse random graphs by means of the cavity method. We first show how the method reproduces several known results about maximum and perfect matchings in regular and Erdos-Renyi random graphs. Our main new result is the computation of the entropy, i.e. the leading order of the logarithm of the number of solutions, of matchings with a given size. We derive both an algorithm to compute this entropy for an arbitrary graph with a girth that diverges in the large size limit, and an analytic result for the entropy in regular and Erdos-Renyi random graph ensembles.

Abstract:
We study the susceptibility propagation, a message-passing algorithm to compute correlation functions. It is applied to constraint satisfaction problems and its accuracy is examined. As a heuristic method to find a satisfying assignment, we propose susceptibility-guided decimation where correlations among the variables play an important role. We apply this novel decimation to locked occupation problems, a class of hard constraint satisfaction problems exhibited recently. It is shown that the present method performs better than the standard belief-guided decimation.

Abstract:
The random XORSAT problem deals with large random linear systems of Boolean variables. The difficulty of such problems is controlled by the ratio of number of equations to number of variables. It is known that in some range of values of this parameter, the space of solutions breaks into many disconnected clusters. Here we study precisely the corresponding geometrical organization. In particular, the distribution of distances between these clusters is computed by the cavity method. This allows to study the `x-satisfiability' threshold, the critical density of equations where there exist two solutions at a given distance.

Abstract:
We study the phase diagram and the algorithmic hardness of the random `locked' constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like satisfiability of boolean formulas or graph coloring. The special property of the locked problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked problems particularly appealing from the mathematical point of view. On the other hand we show empirically that the clustered phase of these problems is extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/hard transition (for currently known algorithms) in the locked problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really hard constraint satisfaction problems.