首页> 外文期刊>Bioinformatics >An exact solution for the segment-to-segment multiple sequence alignment problem.
【24h】

An exact solution for the segment-to-segment multiple sequence alignment problem.

机译:段对段多序列比对问题的精确解决方案。

获取原文
获取原文并翻译 | 示例
       

摘要

MOTIVATION: In molecular biology, sequence alignment is a crucial tool in studying the structure and function of molecules, as well as the evolution of species. In the segment-to-segment variation of the multiple alignment problem, the input can be seen as a set of non-gapped segment pairs (diagonals). Given a weight function that assigns a weight score to every possible diagonal, the goal is to choose a consistent set of diagonals of maximum weight. We show that the segment-to-segment multiple alignment problem is equivalent to a novel formulation of the Maximum Trace problem: the Generalized Maximum Trace (GMT) problem. Solving this problem to optimality, therefore, may improve upon the previous greedy strategies that are used for solving the segment-to-segment multiple sequence alignment problem. We show that the GMT can be stated in terms of an integer linear program and then solve the integer linear program using methods from polyhedral combinatorics. This leads to a branch-and-cut algorithm for segment-to-segment multiple sequence alignment. RESULTS: We report on our first computational experiences with this novel method and show that the program is able to find optimal solutions for real-world test examples.
机译:动机:在分子生物学中,序列比对是研究分子的结构和功能以及物种进化的重要工具。在多重对齐问题的段到段变化中,输入可以看作是一组无间隙的段对(对角线)。给定一个为每个可能的对角线分配权重得分的权重函数,目标是选择最大权重的一致对角线集。我们表明,段到段的多重对齐问题等效于最大迹线问题的一种新形式:广义最大迹线(GMT)问题。因此,将该问题解决为最佳状态可以改进先前用于解决段对段多序列比对问题的贪婪策略。我们证明了GMT可以用整数线性程序来表示,然后使用多面体组合方法求解整数线性程序。这导致了用于片段到片段的多序列比对的分支切割算法。结果:我们报告了使用这种新颖方法的首次计算经验,并表明该程序能够为实际测试示例找到最佳解决方案。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号