Cordue Paul, Linz Simone, Semple Charles
Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand,
Bull Math Biol. 2014 Oct;76(10):2664-79. doi: 10.1007/s11538-014-0032-x. Epub 2014 Sep 23.
In the last decade, the use of phylogenetic networks to analyze the evolution of species whose past is likely to include reticulation events, such as horizontal gene transfer or hybridization, has gained popularity among evolutionary biologists. Nevertheless, the evolution of a particular gene can generally be described without reticulation events and therefore be represented by a phylogenetic tree. While this is not in contrast to each other, it places emphasis on the necessity of algorithms that analyze and summarize the tree-like information that is contained in a phylogenetic network. We contribute to the toolbox of such algorithms by investigating the question of whether or not a phylogenetic network embeds a tree twice and give a quadratic-time algorithm to solve this problem for a class of networks that is more general than tree-child networks.
在过去十年中,系统发育网络被用于分析那些过去可能经历过网状进化事件(如水平基因转移或杂交)的物种的进化过程,这在进化生物学家中越来越受欢迎。然而,特定基因的进化通常可以在没有网状进化事件的情况下进行描述,因此可以用系统发育树来表示。虽然这两者并不相互矛盾,但它强调了分析和总结系统发育网络中包含的树状信息的算法的必要性。我们通过研究系统发育网络是否两次嵌入一棵树的问题,为这类算法的工具箱做出了贡献,并给出了一个二次时间算法来解决一类比树子网络更一般的网络的这个问题。