...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>BMC Genomics >Explaining evolution via constrained persistent perfect phylogeny
【24h】

Explaining evolution via constrained persistent perfect phylogeny

机译：通过受约束的持续完美系统发育解释进化

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Background The perfect phylogeny is an often used model in phylogenetics since it provides an efficient basic procedure for representing the evolution of genomic binary characters in several frameworks, such as for example in haplotype inference. The model, which is conceptually the simplest, is based on the infinite sites assumption, that is no character can mutate more than once in the whole tree. A main open problem regarding the model is finding generalizations that retain the computational tractability of the original model but are more flexible in modeling biological data when the infinite site assumption is violated because of e.g. back mutations. A special case of back mutations that has been considered in the study of the evolution of protein domains (where a domain is acquired and then lost) is persistency, that is the fact that a character is allowed to return back to the ancestral state. In this model characters can be gained and lost at most once. In this paper we consider the computational problem of explaining binary data by the Persistent Perfect Phylogeny model (referred as PPP) and for this purpose we investigate the problem of reconstructing an evolution where some constraints are imposed on the paths of the tree. Results We define a natural generalization of the PPP problem obtained by requiring that for some pairs (character, species), neither the species nor any of its ancestors can have the character. In other words, some characters cannot be persistent for some species. This new problem is called Constrained PPP (CPPP). Based on a graph formulation of the CPPP problem, we are able to provide a polynomial time solution for the CPPP problem for matrices whose conflict graph has no edges. Using this result, we develop a parameterized algorithm for solving the CPPP problem where the parameter is the number of characters. Conclusions A preliminary experimental analysis shows that the constrained persistent perfect phylogeny model allows to explain efficiently data that do not conform with the classical perfect phylogeny model.
机译：背景技术完美的系统发育是系统发育学中经常使用的模型，因为它提供了一种有效的基本程序来表示基因组二进制特性在几个框架中的进化，例如在单倍型推断中。该模型从概念上讲是最简单的，它基于无限地点的假设，即在整个树中，任何字符都不能多次突变。关于模型的一个主要的开放问题是找到保留原始模型的计算可处理性的概括，但是当由于例如图3的无限位点假设而被违反时，在对生物学数据进行建模时更加灵活。背部突变。在研究蛋白质结构域的进化（其中一个结构域被获取然后丢失）的过程中已经考虑到的一种特殊的反向突变是持久性，即允许一个字符返回到祖先状态。在此模型中，角色最多只能获得和丢失一次。在本文中，我们考虑了通过持久完美系统发育模型（称为PPP）解释二进制数据的计算问题，并为此目的研究了在树的路径上施加一些约束的重建演化问题。结果我们定义了PPP问题的自然概括，方法是要求对于某些对（字符，物种），物种或其任何祖先都不具有该特征。换句话说，某些字符对于某些物种不能持久存在。这个新问题称为约束PPP（CPPP）。基于CPPP问题的图形表示，我们能够为冲突图没有边的矩阵提供CPPP问题的多项式时间解。使用此结果，我们开发了一种参数化算法来解决CPPP问题，其中参数是字符数。结论初步实验分析表明，受约束的持久完美系统发育模型可以有效地解释与经典完美系统发育模型不符的数据。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号