Pathgroups, a dynamic data structure for genome reconstruction problems.
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.
Zheng
Chunfang
C
Département d'informatique et de recherche opérationnelle, Université de Montréal, Canada. chunfang313@gmail.com
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D023061:Gene Order; D016681:Genome, Fungal; D010802:Phylogeny; D012441:Saccharomyces cerevisiae / Q000235:genetics; D015003:Yeasts / Q000235:genetics*