On the PATHGROUPS approach to rapid small phylogeny.
On the PATHGROUPS approach to rapid small phylogeny.
复制标题
关于快速小系统发育的养子群方法。
DOI：
10.1186/1471-2105-12-s1-s4
复制
发表时间：
2011-02-15
影响因子：
3
通讯作者：
Sankoff D
中科院分区：
文献类型：
--
作者：
Zheng C;Sankoff D
我们提出了一种数据结构，能够在基因组重排指标下快速启发式解决给定系统发育的祖先基因组重建问题。贪心算法的效率在于在运行时结构的快速更新和选择下一步的简单优先级方案。由于高度分化的基因组集的准确性会下降，因此我们研究了提高准确性和扩大数据集范围的策略，在这些策略中可以预期准确的重建。这包括一个更精细的优先级系统，一个两步前瞻性，以及基于问题的中位数版本的迭代局部改进，结合模拟退火。我们将此应用于一组酵母基因组，以证实最近基于基因序列的系统发育。
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.