On the PATHGROUPS approach to rapid small phylogeny

BMC Bioinformatics

Research

David Sankoff¹  Chunfang Zheng² 

[1] Department of Mathematics and Statistics, University of Ottawa, Canada;Département d’informatique et de recherche opérationnelle, Université de Montréal, Canada;

关键词: Whole Genome Duplication;    Ancestral Genome;    Ancestral Node;    Genomic Distance;    Blue Edge;   

DOI  :  10.1186/1471-2105-12-S1-S4

来源: Springer

【 摘 要 】

We present a data structure enabling rapid heuristic solution to the ancestral genome reconstruction problem for given phylogenies under genomic rearrangement metrics. The efficiency of the greedy algorithm is due to fast updating of the structure during run time and a simple priority scheme for choosing the next step. Since accuracy deteriorates for sets of highly divergent genomes, we investigate strategies for improving accuracy and expanding the range of data sets where accurate reconstructions can be expected. This includes a more refined priority system, and a two-step look-ahead, as well as iterative local improvements based on a the median version of the problem, incorporating simulated annealing. We apply this to a set of yeast genomes to corroborate a recent gene sequence-based phylogeny.

【 授权许可】

CC BY   
© Zheng and Sankoff; licensee BioMed Central Ltd. 2011