In its simplest form, sequence alignment is a path-finding problem. When comparing two strings, we look for a path through a two-dimensional grid where each step represents a match, a gap, or a substitution. For two sequences of length $n$, this is a textbook $O(n^2)$ dynamic programming exercise. However, as we move from simple pairs to multiple sequences or complex linguistic mappings, this grid expands into a high-dimensional hypercube.
This "curse of dimensionality" creates a combinatorial explosion. As Wang et al. observe, the Multiple Longest Common Subsequence (MLCS) problem scales at $O(n^d)$, where $d$ is the number of sequences. In natural language processing, Della Pietra et al. note that the number of possible permutations between words in different languages grows exponentially with sentence length. To make these problems solvable, researchers must find ways to prune this massive search space without losing the optimal alignment.
Structural Constraints as Search Space Pruning
One of the most effective ways to tame the search space is to impose structural constraints that forbid "illogical" alignments. In statistical machine translation, unrestricted word alignment allows any source word to map to any target position. Wu addressed this by introducing Stochastic Bracketing Transduction Grammars (SBTG), which restrict reorderings to a nested, hierarchical structure. By limiting the ways sequences can permute, the author reduced translation complexity from exponential to polynomial time.
Linguistic syntax provides another powerful pruning mechanism. Cherry and Lin demonstrated that by requiring alignments to follow dependency tree structures, they could significantly reduce the alignment error rate. Similarly, Kim et al. used Part-of-Speech (POS) tag sequences to prune the search space between English and Korean, languages with fundamentally different word orders. These constraints work because they allow the model to ignore billions of improbable connections that violate basic grammatical logic.
Dominant Points and Heuristic Search
In biological sequence alignment, where we often need to find commonalities across many long DNA or protein strings, the $O(n^d)$ wall is hit quickly. Rather than filling every cell in a massive $d$-dimensional matrix, researchers focus on "dominant points"—the specific coordinates where matches actually occur.
Wang et al. developed algorithms that jump between these dominant points, skipping the vast empty regions of the search grid. To scale even further, Wang et al. introduced MLCS-A*, which uses a heuristic based on pairwise alignments to guide the search toward the most promising areas of the hypercube. More recently, Yu et al. proposed a "branch and bound" strategy that prunes unnecessary paths during graph construction, creating a "mini-DAG" that drastically reduces memory requirements.
Decomposition and Approximation
When exact alignment remains too costly, the problem can be decomposed into simpler, lower-dimensional steps. In the context of non-autoregressive neural machine translation, Song et al. tackle the high-dimensional alignment matrix by breaking it into three manageable operations: duplication, permutation, and grouping. This decomposition allows parallel decoders to function efficiently without being overwhelmed by the structural complexity of the mapping.
For massive datasets, even the number of sequences itself becomes a dimension of the curse. Chen et al. point out that scaling unsupervised alignment to many languages results in quadratic complexity relative to the number of languages. To combat this, researchers often employ approximation and compression. Ganesh et al. proved that while exact multi-sequence alignment is hard, combining data compression with approximation algorithms can effectively cut the curse of dimensionality in half, enabling the processing of sequences that were previously computationally unreachable.
Key Foundational Work
Fertility Models for Statistical Natural Language Understanding (1997) — contributed 1 concept elements to this direction.
A Polynomial-Time Algorithm for Statistical Machine Translation (1996) — contributed 1 concept elements to this direction.