Département d'informatique et de recherche opérationnelle, Université de Montréal, Canada.
BMC Bioinformatics. 2011 Feb 15;12 Suppl 1(Suppl 1):S4. doi: 10.1186/1471-2105-12-S1-S4.
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.
我们提出了一种数据结构，能够在基因组重排测度下给定的系统发生树上快速启发式地解决祖先基因组重建问题。贪婪算法的效率得益于运行时结构的快速更新和选择下一步的简单优先级方案。由于对于高度分化的基因组集，准确性会降低，因此我们研究了提高准确性和扩展可以预期准确重建的数据集范围的策略。这包括更精细的优先级系统、两步前瞻以及基于问题中位数版本的迭代局部改进，同时结合模拟退火。我们将其应用于一组酵母基因组，以证实最近基于基因序列的系统发生树。
