• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Approximation algorithms for constrained generalized tree alignment problem
【24h】

Approximation algorithms for constrained generalized tree alignment problem

机译：约束广义树对齐问题的近似算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In generalized tree alignment problem, we are given a set S of k biologically related sequences and we are interested in a minimum cost evolutionary tree for S. In many instances of this problem partial phylogenetic tree for S is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows: Constrained Generalized Tree Alignment Problem [S. Divakaran, Algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set S of k related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of S needs to satisfy, construct a minimum cost evolutionary tree for S. In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of 2 - 2/k.
机译：在广义树对齐问题中，我们给定了一个由k个生物学相关序列组成的集合S，并且我们对S的最小成本进化树感兴趣。在此问题的许多情况下，S的部分系统树是已知的。在这种情况下，我们想利用这些知识来限制我们考虑的树形拓扑结构，并构建生物学上相关的最小成本进化树。因此，我们提出了广义树对齐问题的以下自然归纳，即称为MAX-SNP Hard的问题，表述如下：约束广义树对齐问题[S. Divakaran，受约束的广义比对问题的算法和启发式方法，DIMACS技术报告2007-21，2007]：给定一组S个k相关序列，以及一个由节点不相交的系统树组成的系统树，这些树指定了拓扑约束，即S需要满足，为S构造一个最小代价的进化树。在本文中，我们提出了约束广义树对齐问题的常数逼近算法。对于广义树对齐问题（该问题的特殊情况），我们的算法提供了2-2 / k的有保证的误差范围。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号