School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK.
IEEE/ACM Trans Comput Biol Bioinform. 2011 May-Jun;8(3):635-49. doi: 10.1109/TCBB.2010.17.
Recently, much attention has been devoted to the construction of phylogenetic networks which generalize phylogenetic trees in order to accommodate complex evolutionary processes. Here, we present an efficient, practical algorithm for reconstructing level-1 phylogenetic networks--a type of network slightly more general than a phylogenetic tree--from triplets. Our algorithm has been made publicly available as the program LEV1ATHAN. It combines ideas from several known theoretical algorithms for phylogenetic tree and network reconstruction with two novel subroutines. Namely, an exponential-time exact and a greedy algorithm both of which are of independent theoretical interest. Most importantly, LEV1ATHAN runs in polynomial time and always constructs a level-1 network. If the data are consistent with a phylogenetic tree, then the algorithm constructs such a tree. Moreover, if the input triplet set is dense and, in addition, is fully consistent with some level-1 network, it will find such a network. The potential of LEV1ATHAN is explored by means of an extensive simulation study and a biological data set. One of our conclusions is that LEV1ATHAN is able to construct networks consistent with a high percentage of input triplets, even when these input triplets are affected by a low to moderate level of noise.
最近，人们越来越关注构建能够概括系统发生树以适应复杂进化过程的系统发生网络。在这里，我们提出了一种从三重奏中重建一级系统发生网络（一种比系统发生树略通用的网络）的有效实用算法。我们的算法已作为程序 LEV1ATHAN 公开提供。它结合了几种已知的系统发生树和网络重建理论算法的思想，并使用了两个新颖的子程序。即，一种指数时间精确算法和一种贪婪算法，它们都具有独立的理论意义。最重要的是，LEV1ATHAN 运行时间为多项式级，并且总是构建一级网络。如果数据与系统发生树一致，则算法将构建这样的树。此外，如果输入的三重奏集密集，并且完全与某个一级网络一致，则它将找到这样的网络。通过广泛的模拟研究和生物数据集来探索 LEV1ATHAN 的潜力。我们的结论之一是，即使输入的三重奏受到低到中等水平的噪声影响，LEV1ATHAN 也能够构建与高比例输入三重奏一致的网络。
