title: Pathgroups, a dynamic data structure for genome reconstruction problems.
abstract: BACKGROUND
  Ancestral gene order reconstruction problems, including the median problem, quartet construction, small phylogeny, guided genome halving and genome aliquoting, are NP hard. Available heuristics dedicated to each of these problems are computationally costly for even small instances.
  
  
  RESULTS
  We present a data structure enabling rapid heuristic solution to all these ancestral genome reconstruction problems. A generic greedy algorithm with look-ahead based on an automatically generated priority system suffices for all the problems using this data structure. The efficiency of the algorithm is due to fast updating of the structure during run time and to the simplicity of the priority scheme. We illustrate with the first rapid algorithm for quartet construction and apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny.
  
  
  BACKGROUND
  http://albuquerque.bioinformatics.uottawa.ca/pathgroup/Quartet.html
  
  
  BACKGROUND
  chunfang313@gmail.com
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Département d'informatique et de recherche opérationnelle, Université de Montréal, Canada. chunfang313@gmail.com
authors.forename: Chunfang
authors.initials: C
authors.lastname: Zheng
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D023061:Gene Order; D016681:Genome, Fungal; D010802:Phylogeny; D012441:Saccharomyces cerevisiae / Q000235:genetics; D015003:Yeasts / Q000235:genetics*