title: Comparative genomics meets topology: a novel view on genome median and halving problems.
abstract: BACKGROUND
  Genome median and genome halving are combinatorial optimization problems that aim at reconstruction of ancestral genomes by minimizing the number of evolutionary events between them and genomes of the extant species. While these problems have been widely studied in past decades, their solutions are often either not efficient or not biologically adequate. These shortcomings have been recently addressed by restricting the problems solution space.
  
  
  RESULTS
  We show that the restricted variants of genome median and halving problems are, in fact, closely related. We demonstrate that these problems have a neat topological interpretation in terms of embedded graphs and polygon gluings. We illustrate how such interpretation can lead to solutions to these problems in particular cases.
  
  
  CONCLUSIONS
  This study provides an unexpected link between comparative genomics and topology, and demonstrates advantages of solving genome median and halving problems within the topological framework.
authors.affiliation: The George Washington University, Washington, DC, USA. nikita_alexeev@gwu.edu.
authors.forename: Nikita
authors.initials: N
authors.lastname: Alexeev
authors.affiliation: The George Washington University, Washington, DC, USA.
authors.forename: Pavel
authors.initials: P
authors.lastname: Avdeyev
authors.affiliation: The George Washington University, Washington, DC, USA.
authors.forename: Max A
authors.initials: MA
authors.lastname: Alekseyev
mesh_terms: D016678:Genome; D023281:Genomics; D008957:Models, Genetic
keywords: Breakpoint graphs; Embedded graphs; Halving problem; Median problem