Exact Multiple Sequence Alignment by Synchronized Decision Diagrams

Amin Hosseininasab () and Willem-Jan van Hoeve ()
Additional contact information
Amin Hosseininasab: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Willem-Jan van Hoeve: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213

INFORMS Journal on Computing, 2021, vol. 33, issue 2, 721-738

Abstract: 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.

Keywords: multiple sequence alignment; multivalued decision diagrams; decision diagram filtering; optimistic filtering; logic-based Benders decomposition (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2019.0937 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:2:p:721-738

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().