Département d'informatique, Université du Québec à Montréal, C.P. 8888, Succ. Centre-ville, Montréal, Québec, Canada.
Syst Biol. 2010 Mar;59(2):195-211. doi: 10.1093/sysbio/syp103. Epub 2010 Jan 21.
Horizontal gene transfer (HGT) is one of the main mechanisms driving the evolution of microorganisms. Its accurate identification is one of the major challenges posed by reticulate evolution. In this article, we describe a new polynomial-time algorithm for inferring HGT events and compare 3 existing and 1 new tree comparison indices in the context of HGT identification. The proposed algorithm can rely on different optimization criteria, including least squares (LS), Robinson and Foulds (RF) distance, quartet distance (QD), and bipartition dissimilarity (BD), when searching for an optimal scenario of subtree prune and regraft (SPR) moves needed to transform the given species tree into the given gene tree. As the simulation results suggest, the algorithmic strategy based on BD, introduced in this article, generally provides better results than those based on LS, RF, and QD. The BD-based algorithm also proved to be more accurate and faster than a well-known polynomial time heuristic RIATA-HGT. Moreover, the HGT recovery results yielded by BD were generally equivalent to those provided by the exponential-time algorithm LatTrans, but a clear gain in running time was obtained using the new algorithm. Finally, a statistical framework for assessing the reliability of obtained HGTs by bootstrap analysis is also presented.
水平基因转移（HGT）是驱动微生物进化的主要机制之一。其准确识别是网状进化带来的主要挑战之一。在本文中，我们描述了一种新的多项式时间算法，用于推断 HGT 事件，并在 HGT 识别的背景下比较了 3 种现有和 1 种新的树比较指标。所提出的算法可以依赖不同的优化标准，包括最小二乘法（LS）、罗宾逊和福尔兹（RF）距离、四分体距离（QD）和二分歧差异（BD），在搜索将给定的种系树转换为给定基因树所需的最优子树修剪和重新连接（SPR）移动场景时。正如模拟结果所表明的，本文中引入的基于 BD 的算法策略通常比基于 LS、RF 和 QD 的策略提供更好的结果。基于 BD 的算法也被证明比著名的多项式时间启发式算法 RIATA-HGT 更准确和更快。此外，BD 算法的 HGT 恢复结果通常与使用新算法获得的指数时间算法 LatTrans 提供的结果相当，但运行时间明显缩短。最后，还提出了一种基于 bootstrap 分析的统计框架，用于评估获得的 HGT 的可靠性。
