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

Ian En-Hsu Yen, Xin Lin, Jiong Zhang, Pradeep Ravikumar, Inderjit S. DhillonICML 2016 · OpenReview

TL;DR

Researchers have developed a novel approach to tackle two of the most challenging problems in bioinformatics: Multiple Sequence Alignment (MSA) and Motif Discovery (MD). By treating these NP-hard discrete tasks as convex optimization problems using "atomic norms," their new algorithm (GDMM) consistently finds higher-quality alignments than industry-standard tools like Clustal-Omega and MEME.

The Challenge of Sequence Alignment

In bioinformatics, comparing multiple DNA or protein sequences is essential for understanding evolutionary relationships and identifying functional patterns (motifs). However, both Multiple Sequence Alignment and Motif Discovery are notoriously difficult, NP-hard problems.

Traditional tools usually rely on one of two approaches:

  1. Heuristics: Greedy "progressive" methods build an alignment step-by-step but cannot fix early mistakes.
  2. Local Search: Methods like Expectation Maximization (EM) or Gibbs Sampling often get stuck in "local optima"—finding a good solution, but missing the absolute best one.

The authors aim to move past these limitations by creating a convex relaxation. Essentially, they turn a jagged, "bumpy" search space into a smooth, bowl-shaped one where the global optimum is mathematically easier to find.

A Convex Approach to Bioinformatics

The core innovation of this paper is the use of Atomic Norms to redefine the alignment space.

  • The "Atoms": The researchers define "atoms" as the simplest valid structures of the problem—for example, a single valid alignment path between two sequences or a single consensus sequence.
  • Convex Hull: They define the feasible region as the "convex hull" (the smallest convex set containing all atoms) of these structures.
  • The Objective: The problem becomes finding a point that exists in the intersection of two convex hulls: one representing valid alignments for each sequence and another representing a shared consensus.
The alignment space represented as a 3D cube, illustrating the search for a consensus sequence.

To solve this, the authors introduce the Greedy Direction Method of Multiplier (GDMM). This algorithm combines the Augmented Lagrangian method with a variant of the Frank-Wolfe algorithm. To make the math computationally tractable, they adapted classic bioinformatics algorithms—like Smith-Waterman and Viterbi—to act as "Linear Minimization Oracles" (LMOs) that efficiently find the best "atom" to move toward in each iteration. Finally, a rounding scheme is used to pull the fractional convex solution back into a valid, discrete alignment.

Datasets and Key Insights

The authors evaluated their approach on both synthetic and realistic benchmarks:

  • Synthetic MSA: Generated using the TKF1 evolutionary model, which simulates DNA mutations over time.
  • Realistic MSA: Two specific datasets, sDicF and sHairpin, used to test the algorithm on biologically relevant structures.
  • Decipher MD: A synthetic task where sentences (like Caesar’s "Veni Vidi Vici") were encoded into binary strings to see if the algorithm could recover the original "motifs."

Unlike EM or Gibbs sampling, which are highly sensitive to their starting points, this convex approach looks at the global structure of the alignment space. In some high-mutation scenarios, the algorithm actually found alignments with better scores than the original ground-truth sequences used to generate the data, proving its efficiency at finding the mathematical optimum.

Key Results

The authors compared their tool, ConvexMSA, against five major solvers: Clustal-Omega, Kalign, T-COFFEE, MAFFT, and MUSCLE.

Performance comparison of ConvexMSA against standard solvers on synthetic and realistic datasets.
  • Superior Accuracy: ConvexMSA consistently achieved lower (better) Sum-of-Pairs and Star Alignment scores across all synthetic and realistic datasets. For example, on the "Syn03" dataset, ConvexMSA scored 1285, significantly outperforming the next best tool (T-COFFEE at 1492).
  • Motif Discovery: In the deciphering tasks, the authors' method (ConvexMD) achieved a perfect 100% matching rate, whereas the popular MEME tool hovered around 72-75%. ConvexMD even discovered unexpected perfect matching solutions that the researchers hadn't initially considered.

Limitations and Future Work

While highly accurate, the approach has limitations. The iterative nature of GDMM is computationally heavier and likely slower than simple greedy heuristics. Furthermore, representing the "ambient space" for very long sequences could become memory-intensive. Future work will focus on scaling the algorithm to handle hundreds or thousands of sequences—common in modern genomics—and extending the model to incorporate more complex biological gap penalties.

Summary updated

Abstract

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 m...
BibTeX
@inproceedings{yen2016convex,
  author = {Ian En-Hsu Yen and Xin Lin and Jiong Zhang and Pradeep Ravikumar and Inderjit S. Dhillon},
  title = {{A Convex Atomic-Norm Approach to Multiple Sequence Alignment and Motif Discovery}},
  booktitle = {International Conference on Machine Learning},
  year = {2016},
  url = {https://openreview.net/forum?id=H1WsShWdbr},
}
Figure