title: Mapping ancestral genomes with massive gene loss: a matrix sandwich problem.
abstract: BACKGROUND
  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.
  
  
  BACKGROUND
  Upon request to the authors.
  
  
  BACKGROUND
  haris.gavranovic@gmail.com; eric.tannier@inria.fr.
authors.affiliation: Faculty of Natural Sciences, University of Sarajevo, Bosnia and Herzegovina. haris.gavranovic@gmail.com
authors.forename: Haris
authors.initials: H
authors.lastname: Gavranović
authors.forename: Cedric
authors.initials: C
authors.lastname: Chauve
authors.forename: Jérôme
authors.initials: J
authors.lastname: Salse
authors.forename: Eric
authors.initials: E
authors.lastname: Tannier
mesh_terms: D000818:Animals; D005075:Biological Evolution; D019143:Evolution, Molecular; D016678:Genome; D006801:Humans; D019684:Magnoliopsida / Q000235:genetics; D008322:Mammals / Q000235:genetics