• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国卫生研究院文献>Algorithms for Molecular Biology : AMB >Incompatible quartets triplets and characters
【2h】

Incompatible quartets triplets and characters

机译：四重奏三重奏和角色不兼容

代理获取
本网站仅为用户提供外文OA文献查询和代理获取服务，本网站没有原文。下单后我们将采用程序或人工为您竭诚获取高质量的原文，但由于OA文献来源多样且变更频繁，仍可能出现获取不到、文献不完整或与标题不符等情况，如果获取不到我们将提供退款服务。请知悉。
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study a long standing conjecture on the necessary and sufficient conditions for the compatibility of multi-state characters: There exists a function f(r) such that, for any set C of r-state characters, C is compatible if and only if every subset of f(r) characters of C is compatible. We show that for every r≥2, there exists an incompatible set C of Ω(r2)r-state characters such that every proper subset of C is compatible. This improves the previous lower bound of f(r)≥r given by Meacham (1983), and f(4)≥5 given by Habib and To (2011). For the case when r=3, Lam, Gusfield and Sridhar (2011) recently showed that f(3)=3. We give an independent proof of this result and completely characterize the sets of pairwise compatible 3-state characters by a single forbidden intersection pattern.Our lower bound on f(r) is proven via a result on quartet compatibility that may be of independent interest: For every n≥4, there exists an incompatible set Q of Ω(n2) quartets over n labels such that every proper subset of Q is compatible. We show that such a set of quartets can have size at most 3 when n=5, and at most O(n3) for arbitrary n. We contrast our results on quartets with the case of rooted triplets: For every n≥3, if R is an incompatible set of more than n−1 triplets over n labels, then some proper subset of R is incompatible. We show this bound is tight by exhibiting, for every n≥3, a set of n−1 triplets over n taxa such that R is incompatible, but every proper subset of R is compatible.
机译：我们研究了关于多状态字符兼容的必要和充分条件的一个长期推测：存在一个函数f（r），对于任何一组R状态字符C，当且仅当每个C的f（r）个字符的子集是兼容的。我们表明，对于每个r≥2，存在一个不兼容的Ω（r 2 ）r状态字符集C，因此C的每个适当子集都是兼容的。这改善了Meacham（1983）给出的f（r）≥ r 的先前下界，以及Habib和To（2011）给出的 f （4）≥5的先前下界。对于 r = 3的情况，Lam，Gusfield和Sridhar（2011）最近表明 f （3）= 3。我们对此结果给出独立的证明，并通过单个禁止的交集模式完全描述成对兼容的三态字符集。 f （ r ）的下界是通过四元组兼容性的结果得到证明，该结果可能具有独立的意义：对于每个 n ≥4，存在一个不兼容的 Q 集合，其中Ω（ n 标签上的 n 2 ）四重奏，这样 Q 的每个适当子集都是兼容的。我们证明，当 n = 5时，这样的一组四重奏的大小最多为3，而 O （ n 3最多为4 ）表示任意 n 。我们将四重奏的结果与有根三重奏的情况进行对比：对于每个 n ≥3，如果 R 是大于 n 的不兼容集-1个三元组在 n 标签上，则 R 的某些适当子集不兼容。通过对每个 n ≥3展示一组 n -1个三元组在 n 上的类，使得 n − > R 不兼容，但是 R 的每个适当子集都是兼容的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
代理获取

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号