MOTIVATION: Ancestral genomes provide a better way to understand the structural evolution of genomes than the simple comparison of extant genomes. Most ancestral genome reconstruction methods rely on universal markers, that is, homologous families of DNA segments present in exactly one exemplar in every considered species. Complex histories of genes or other markers, undergoing duplications and losses, are rarely taken into account. It follows that some ancestors are inaccessible by these methods, such as the proto-monocotyledon whose evolution involved massive gene loss following a whole genome duplication. RESULTS: We propose a mapping approach based on the combinatorial notion of 'sandwich consecutive ones matrix', which explicitly takes gene losses into account. We introduce combinatorial optimization problems related to this concept, and propose a heuristic solver and a lower bound on the optimal solution. We use these results to propose a configuration for the proto-chromosomes of the monocot ancestor, and study the accuracy of this configuration. We also use our method to reconstruct the ancestral boreoeutherian genomes, which illustrates that the framework we propose is not specific to plant paleogenomics but is adapted to reconstruct any ancestral genome from extant genomes with heterogeneous marker content. AVAILABILITY: Upon request to the authors. CONTACT: [email protected]; [email protected].

In the past decade, a number of bioinformatics tools have been developed to perform comparative genomics studies in plants and animals. However, most of the publicly available and user friendly tools lack common standards for the identification of robust orthologous relationships between genomes leading non-specialists to often over interpret the results of large scale comparative sequence analyses. Recently, we have established a number of improved parameters and tools to define significant relationships between genomes as a basis to develop paleogenomics studies in grasses. Here, we describe our approaches and propose the development of community-based standards that can be used in comparative genomic studies to (i) identify robust sets of orthologous gene pairs, (ii) derive complete sets of chromosome to chromosome relationships within and between genomes and (iii) model common paleo-ancestor genome structures. The rice and sorghum genome sequences are used to exemplify step-by-step a methodology that should allow users to perform accurate comparative genome analyses in their favourite species. Finally, we describe two applications for accurate gene annotation and synteny-based cloning of agronomically important traits.