...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >A polyhedral approach to sequence alignment problems
【24h】

A polyhedral approach to sequence alignment problems

机译：解决序列比对问题的多面体方法

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

摘要

We study two new problems in sequence alignment both from a practical and a theoretical view, using tools from combinatorial optimization to develop branch-and-cut algorithms. The generalized maximum trace formulation captures several forms of multiple sequence alignment problems in a common framework, among them the original formulation of maximum trace. The RNA sequence alignment problem captures the comparison of RNA molecules on the basis of their primary sequence and their secondary structure. Both problems have a characterization in terms of graphs which we reformulate in terms of integer linear programming. We then study the polytopes (or convex hulls of all feasible solutions) associated with the integer linear program for both problems. For each polytope we derive several classes of facet-defining inequalities and show that for some of these classes the corresponding separation problem can be solved in polynomial time. This leads to a polynomial-time algorithm for pairwise sequence alignment that is not based on dynamic programming. Moreover, for multiple sequences the branch-and-cut algorithms for both sequence alignment problems are able to solve to optimality instances that are beyond the range of present dynamic programming approaches. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 41]
机译：我们使用组合优化工具开发分支剪切算法，从实践和理论两个角度研究序列比对中的两个新问题。广义最大迹线公式在通用框架中捕获了多种形式的多序列比对问题，其中包括最大迹线的原始公式。 RNA序列比对问题根据其一级序列和二级结构捕获了RNA分子的比较。这两个问题都具有图形的特征​​，我们根据整数线性规划重新制定了图形。然后，我们针对这两个问题研究与整数线性程序关联的多面体（或所有可行解的凸包）。对于每个多面体，我们推导出了几类定义方面的不等式，并表明对于其中的某些类，可以在多项式时间内解决相应的分离问题。这导致不基于动态编程的用于成对序列比对的多项式时间算法。此外，对于多个序列，两个序列比对问题的分支剪切算法都能够解决超出当前动态编程方法范围的最优实例。 （C）2000 Elsevier Science B.V.保留所有权利。 [参考：41]

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号