Exact Multiple Sequence Alignment by Synchronized Decision Diagrams
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 Multi-valued Decision Diagrams (MDD) representation of all pairwise sequence alignments (PSA). PSA MDDs are then synchronized using side constraints to model the MSA problem … Read more