标题： 一种用于重建层次1系统发生网络的实用算法 显示英文标题

标题： A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks

摘要： 最近，人们广泛关注于构建系统发生网络，以推广系统发生树，从而适应复杂的进化过程。 在这里，我们提出了一种高效且实用的算法，用于从三元组中重建层次-1系统发生网络——一种比系统发生树稍具一般性的网络类型。 我们的算法已作为程序LEV1ATHAN公开可用。 它结合了几种已知的系统发生树和网络重建理论算法的思想，以及两个新的子例程。 即，一个指数时间精确算法和一个贪心算法，这两者都具有独立的理论意义。 最重要的是，LEV1ATHAN在多项式时间内运行，并始终构建一个层次-1网络。 如果数据与系统发生树一致，则该算法会构建这样的树。 此外，如果输入的三元组集是密集的，并且还完全与某个层次-1网络一致，它将找到这样的网络。 通过广泛的模拟研究和一个生物数据集，探讨了LEV1ATHAN的潜力。 我们的结论之一是， LEV1ATHAN能够构建与大量输入三元组一致的网络，即使这些输入三元组受到低到中等水平的噪声影响。 显示英文摘要

摘要： 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 is 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.