Scalable Convex Multiple Sequence Alignment via EntropyRegularized Dual Decomposition
[edit]
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:15141522, 2017.
Abstract
Multiple Sequence Alignment (MSA) is one of the fundamental tasks in biological sequence analysis that underlies applications such as phylogenetic trees, profiles, and structure prediction. The task, however, is NPhard, and the current practice resorts to heuristic and localsearch methods. Recently, a convex optimization approach for MSA was proposed based on the concept of atomic norm, which demonstrates significant improvement over existing methods in the quality of alignments. However, the convex program is challenging to solve due to the constraint given by the intersection of two atomicnorm balls, for which the existing algorithm can only handle sequences of length up to 50, with an iteration complexity subject to constants of unknown relation to the natural parameters of MSA. In this work, we propose an accelerated dual decomposition algorithm that exploits entropy regularization to induce closedform solutions for each atomicnormconstrained subproblem, giving a singleloop algorithm of iteration complexity linear to the problem size (total length of all sequences). The proposed algorithm gives significantly better alignments than existing methods on sequences of length up to hundreds, where the existing convex programming method fails to converge in one day.
Related Material


