An exact solution for the segment-to-segment multiple sequence alignment problem
An exact solution for the segment-to-segment multiple sequence alignment problem
复制标题
DOI：
10.1093/bioinformatics/15.3.203
复制
发表时间：
1999-03-01
期刊：
影响因子：
5.8
通讯作者：
Reinert, K
中科院分区：
文献类型：
--
作者：
Lenhof, HP;Morgenstern, B;Reinert, K
动机：在分子生物学中，序列比对是研究分子结构和功能以及物种进化的重要工具，在多重比对问题的片段到片段的变化中，输入可以被视为一组无间隙的片段对(对角线)。给定权重函数，为每条可能的对角线分配一个权重分数，目标是选择一组一致的最大权重的对角线。我们证明了段到段多重比对问题等价于最大迹问题的一种新形式：广义最大迹问题。因此，将该问题解决为最优，可以改进用于解决段到段多序列比对问题的先前的贪婪策略。我们证明了GMT可以表示为一个整数线性规划，然后利用多面体组合数学的方法求解该整数线性规划。结果：我们报告了我们首次使用这种新方法的计算经验，并表明该程序能够为真实世界的测试用例找到最优解。
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.