Département d'informatique et de recherche opérationnelle, Université de Montréal, Canada.
Bioinformatics. 2010 Jul 1;26(13):1587-94. doi: 10.1093/bioinformatics/btq255. Epub 2010 May 18.
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.
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.
http://albuquerque.bioinformatics.uottawa.ca/pathgroup/Quartet.html
Supplementary data are available at Bioinformatics online.
祖先基因顺序重建问题，包括中位数问题、四分体构建、小系统发生、有指导的基因组减半和基因组等分，都是 NP 难问题。即使对于较小的实例，专门针对这些问题中的每一个问题的可用启发式方法在计算上也是非常昂贵的。
我们提出了一种数据结构，能够快速启发式地解决所有这些祖先基因组重建问题。基于自动生成的优先级系统的具有前瞻性的通用贪婪算法足以使用此数据结构解决所有问题。该算法的效率归因于运行时快速更新结构以及优先级方案的简单性。我们通过四分体构建的第一个快速算法来说明这一点，并将其应用于一组酵母基因组，以证实最近基于基因序列的系统发育。
http://albuquerque.bioinformatics.uottawa.ca/pathgroup/Quartet.html
补充数据可在生物信息学在线获得。
Zotero 插件