A decomposition theory for phylogenetic networks and incompatible characters
A decomposition theory for phylogenetic networks and incompatible characters
复制标题
DOI：
10.1089/cmb.2006.0137
复制
发表时间：
2007-12-01
影响因子：
1.7
通讯作者：
Song, Yun S.
中科院分区：
文献类型：
--
作者：
Gusfield, Dan;Bansal, Vikas;Song, Yun S.
系统发育网络是超越树木的进化模型，纳入了非树状生物事件，例如重组（或更普遍的网状结构），这些事件发生在单个物种（减数分裂重组）或物种之间（由于横向基因转移和杂交物种形成而导致的网状结构）。核心算法问题是重建突变和非树状事件的合理历史，或者确定导出一组给定的二进制序列所需的此类事件的最小数量，允许每个位点一个突变。减数分裂重组、网状结构和反复突变可能导致输入位点对（或字符）之间的冲突或不兼容。之前，我们使用“冲突图”和“不兼容图”来计算所需重组节点的最小数量的下界，并有效地解决最小化问题的约束情况。这些结果揭示了这两个图的非平凡连接组件的结构和算法重要性。在本文中，我们更全面地发展了不相容图和冲突图的非平凡连通分量的结构重要性，证明了系统发育网络的一般分解定理（Gusfield 和 Bansal，2005）。分解定理仅取决于输入序列中的不兼容性，因此适用于多种类型的系统发育网络，以及导致成对不兼容性的任何生物现象。更一般地说，分解定理的证明揭示了当序列无法在完美的系统发育树上导出时，网络中存在的最大嵌入树结构。这以自然而重要的方式扩展了完美系统发育理论。该证明是建设性的，并导致多项式时间算法来找到唯一的底层最大树结构。接下来，我们检查并完全解决 Gusfield 和 Bansal (2005) 提出的主要开放问题：对于每个输入，是否真的必须有一个完全分解的系统发育网络，在输入的所有系统发育网络中最小化所使用的重组节点的数量。我们之前猜测答案是肯定的。在本文中，我们证明答案是否定的，既适用于仅允许单交叉重组的情况，也适用于允许无界多重交叉重组的情况。后一种情况还解决了最近在网状网络背景下提出的猜想（Huson 和 Klopper，2007）。尽管 Gusfield 和 Bansal (2005) 的猜想总体上被证伪，但我们证明了在几个自然特殊情况下该猜想的答案是肯定的，并建立了该猜想的反例必须具有的必要组合结构。我们还表明，在模拟数据中，该猜想的反例很少（对于单交叉重组的情况）。
Phylogenetic networks are models of evolution that go beyond trees, incorporating non-tree-like biological events such as recombination (or more generally reticulation), which occur either in a single species (meiotic recombination) or between species ( reticulation due to lateral gene transfer and hybrid speciation). The central algorithmic problems are to reconstruct a plausible history of mutations and non-tree-like events, or to determine the minimum number of such events needed to derive a given set of binary sequences, allowing one mutation per site. Meiotic recombination, reticulation and recurrent mutation can cause conflict or incompatibility between pairs of sites (or characters) of the input. Previously, we used '' conflict graphs '' and '' incompatibility graphs '' to compute lower bounds on the minimum number of recombination nodes needed, and to efficiently solve constrained cases of the minimization problem. Those results exposed the structural and algorithmic importance of the non-trivial connected components of those two graphs. In this paper, we more fully develop the structural importance of non-trivial connected components of the incompatibility and conflict graphs, proving a general decomposition theorem (Gusfield and Bansal, 2005) for phylogenetic networks. The decomposition theorem depends only on the incompatibilities in the input sequences, and hence applies to many types of phylogenetic networks, and to any biological phenomena that causes pairwise incompatibilities. More generally, the proof of the decomposition theorem exposes a maximal embedded tree structure that exists in the network when the sequences cannot be derived on a perfect phylogenetic tree. This extends the theory of perfect phylogeny in a natural and important way. The proof is constructive and leads to a polynomial-time algorithm to find the unique underlying maximal tree structure. We next examine and fully solve the major open question from Gusfield and Bansal ( 2005): Is it true that for every input there must be a fully decomposed phylogenetic network that minimizes the number of recombination nodes used, over all phylogenetic networks for the input. We previously conjectured that the answer is yes. In this paper, we show that the answer in is no, both for the case that only single-crossover recombination is allowed, and also for the case that unbounded multiple-crossover recombination is allowed. The latter case also resolves a conjecture recently stated in (Huson and Klopper, 2007) in the context of reticulation networks. Although the conjecture from Gusfield and Bansal (2005) is disproved in general, we show that the answer to the conjecture is yes in several natural special cases, and establish necessary combinatorial structure that counterexamples to the conjecture must posses. We also show that counterexamples to the conjecture are rare (for the case of single-crossover recombination) in simulated data.