序列(生物学)
解算器
水准点(测量)
启发式
算法
数学优化
成对比较
数学
整数规划
计算机科学
代表(政治)
国家(计算机科学)
人工智能
遗传学
生物
政治
法学
地理
政治学
大地测量学
作者
Amin Hosseininasab,Willem‐Jan van Hoeve
标识
DOI:10.1287/ijoc.2019.0937
摘要
This paper develops an exact solution algorithm for the multiple sequence alignment (MSA) problem. In the first step, we design a dynamic programming model and use it to construct a novel multivalued decision diagram (MDD) representation of all pairwise sequence alignments (PSA). PSA MDDs are then synchronized using side constraints to model the MSA problem as a mixed-integer program (MIP), for the first time, in polynomial space complexity. Two bound-based filtering procedures are developed to reduce the size of the MDDs, and the resulting MIP is solved using logic-based Benders decomposition. For a more effective algorithm, we develop a two-phase solution approach. In the first phase, we use optimistic filtering to quickly obtain a near-optimal bound, which we then use for exact filtering in the second phase to prove or obtain an optimal solution. Numerical results on benchmark instances show that our algorithm solves several instances to optimality for the first time, and, in case optimality cannot be proven, considerably improves upon a state-of-the-art heuristic MSA solver. Comparison with an existing state-of-the-art exact MSA algorithm shows that our approach is more time efficient and yields significantly smaller optimality gaps.
科研通智能强力驱动
Strongly Powered by AbleSci AI