A Convex Atomic-Norm Approach to Multiple Sequence Alignment and Motif Discovery

By Ian En-Hsu Yen, Xin Lin, Jiong Zhang, Pradeep Ravikumar, Inderjit S. Dhillon. 2016

13 citations recorded by the source corpus.

Multiple Sequence Alignment and Motif Discovery, known as NP-hard problems, are two fundamental tasks in Bioinformatics. Existing approaches to these two problems are based on either local search methods such as Expectation Maximization (EM), Gibbs Sampling or greedy heuristic methods. In this work, we develop a convex relaxation approach to both problems based on the recent concept of atomic norm and develop a new algorithm, termed Greedy Direction Method of Multiplier, for solving the convex relaxation with two convex atomic constraints. Experiments show that our convex relaxation approach produces solutions of higher quality than those standard tools widely-used in Bioinformatics community on the Multiple Sequence Alignment and Motif Discovery problems.

Subfields: Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “In their work, Yen et al. (2016a,b); Huang et al. (2017) only provide a rate on both gaps (9) and (10) which is not suﬃcient to derive guarantees on either how close an iterate is to the optimal set or how small is the suboptimality of the closest feasible point.”
Dual Decomposed Learning with Factorwise Oracle for Structural SVM of Large Output Domain (2016, methodology): “This type of greedy Augmented Lagrangian Method was also analyzed previously under different context [23, 24, 22].”