Splitting a protein chain into domains, meaning the compact units that fold and evolve somewhat independently, is usually done in two stages. A neural network first scores how likely each pair of residues is to belong to the same domain. A second step then turns those scores into one partition, typically by greedy clustering. This proposal replaces the greedy second stage with an exact dynamic program that sums over every way of cutting the chain into domains and inter-domain linkers. The program returns two things: the single best segmentation, and a probability that each residue is a boundary. The scoring combines a structural term over residue pairs with an evolutionary term at the cut points, taken from homolog alignments.
Two questions motivate this, and both have practical stakes. First, greedy assembly has no foresight. Exact segmentation by dynamic programming avoids that weakness whenever the objective breaks into a sum over segments. Second, a single partition cannot express real ambiguity. Chainsaw reports that in 65% of evaluated cases its calls and UniDoc's are both defensible alternatives, yet each tool outputs one answer. A distribution over segmentations, rather than one partition, tells a curator, a homology search, or a comparative modeler where the cut is uncertain and by how much.
Core Claim
The co-membership objective that Chainsaw-style networks implicitly target can be rewritten exactly as a sum over segments, so it admits an exact O(N²) dynamic program and a partition function over segmentations. Let $P_{ij}$ be the predicted probability that residues $i$ and $j$ share a domain. A segmentation $\sigma$ assigns each residue either to a contiguous domain segment or to a linker state. Its log-likelihood is the sum, over residue pairs, of $\log P_{ij}$ if the two residues lie in the same segment and $\log(1-P_{ij})$ otherwise. Pairs touching a linker residue receive a neutral score.
The sum of $\log(1-P_{ij})$ over all pairs is the same for every segmentation, so it can be dropped. What remains is
$$ \text{score}(\sigma) = \sum_{s \in \sigma} \Big[ \sum_{i,j \in s} \log \frac{P_{ij}}{1-P_{ij}} \Big] + \sum_{b \in \partial\sigma} \beta\, e_b + \lambda\, |\text{linker}(\sigma)|, $$
where the first sum runs over domain segments $s$ and the inner sum is computed in O(1) from a 2D prefix-sum table. Here $\partial\sigma$ is the set of cut points, $e_b$ is an evolutionary boundary signal at position $b$, $\beta$ is its weight, and $\lambda$ is a per-residue linker cost.
The cross-segment interactions that normally break additivity, flagged as a core limitation of dynamic-programming segmentation, cancel exactly in this objective. They do not need to be approximated. Running the same recurrence with log-sum-exp in place of max gives the partition function $Z=\sum_\sigma \exp(\text{score}(\sigma)/T)$, where $T$ is a temperature. Forward-backward passes then give the posterior probability that each residue is a boundary or a linker.
Dotú et al. explicitly listed this partition function over segmentations as future work in RNA Structural Segmentation. That paper is where the method comes from: it supplies the exact segmentation dynamic program, with fitness that rewards contacts inside a segment and penalizes contacts across segments, and it demonstrates protein domain segmentation from Voronoi volumes. Our work differs from it in four ways. It adds evolutionary terms, which Dotú et al. never use. It adds explicit linker states, which addresses their observation that end-to-end partitioning forces disordered tails into domains. It computes posteriors rather than only optima. And it is benchmarked against modern learned domain parsers on CATH, the standard database of curated protein domain boundaries.
Research Program
We build the decoder in three layers and treat each as a separate claim.
The first layer is pure decoding. We take Chainsaw's released co-membership matrices as given and swap only the post-processing: greedy assembly versus exact MAP decoding, meaning the single highest-scoring segmentation. This isolates whether exact optimization matters on a fixed input.
The second layer adds structural-evolutionary integration at the cut points. The term $e_b$ combines two signals. One is DoBo's evidence that homolog alignments show long terminal gaps at domain boundaries, a footprint of gene fusion and fission (DoBo). The other is the dips in per-position conservation and predicted solvent accessibility typical of linkers. DoBo motivates this term but constrains how we use it. Its signal is absent for short proteins or proteins with few diverse homologs, so we use it as an additive prior that can be zero, never as a gate on which boundaries may be proposed.
We deliberately do not use mutual-information coupling as a primary term. HMMsato found its optimal weight to be only 0.1, against 0.72 for solvent accessibility, and its gains were inconsistent. That is a negative result we take seriously.
The third layer extends the decoder to discontinuous domains, in which one domain is inserted into the middle of another. Strictly contiguous dynamic programming cannot represent these, and Chainsaw's greedy method handles them natively. We add a nesting rule in which a domain may enclose one inserted domain. This raises the cost to O(N³), the same nesting structure that RNA secondary-structure dynamic programs use, and remains tractable for chains under about 1,500 residues.
We also run the decoder on a matrix computed directly from AlphaFold distances weighted by pLDDT (AlphaFold's per-residue confidence score) instead of Chainsaw's learned $P$. This tells us how much of the gain comes from the decoder and how much from the learned input.
The parameters $\beta$, $\lambda$, $T$, and minimum domain length are fit on a CATH training split. $T$ is calibrated so that posterior boundary probabilities match empirical frequencies on held-out data.
Baselines
The naive reference is to call every chain a single domain. Because many CATH chains are single-domain, this sets the floor that any boundary method must clear on multi-domain chains.
The strongest existing method is Chainsaw: a fully convolutional network over structure-derived features followed by greedy domain assembly. It reports 78% accuracy against CATH annotations, compared with 72% for UniDoc. It is the strongest competitor because our first experiment uses its own matrices. We will run Chainsaw's released model on the same CATH test chains and AlphaFold models, apply both decoders to identical outputs, and use Chainsaw's own accuracy definition. Beating it means a statistically significant gain in that accuracy on multi-domain chains, under a paired test across chains, with no loss on single-domain chains. Matching its accuracy while adding calibrated posteriors counts as a partial result, and we would report it as such.
DoBo represents point-wise boundary classification: a support vector machine over profile, structure, and gap features. Its results are 60% precision and 60% recall at break-even on multi-domain proteins, and 84.6% of true boundaries lying within 20 residues of an evolutionary signal, on the DOMpro set of 628 proteins. We will retrain a per-residue boundary classifier with the same features as our $e_b$ term, plus summary features from $P$. We then pick peaks with a tuned threshold, using the same training split and hyperparameter search budget as our decoder.
Two ablations isolate the key ingredients: the decoder without $e_b$, and the decoder without linker states. A third ablation compares MAP decoding against decoding that maximizes the expected number of correctly placed boundaries under the posterior.
Why not just…?
Why not just keep Chainsaw's greedy assembly, since it already scores 78%? This is a real threat. On a sharp matrix, greedy assembly may already find the optimum, and if so the first experiment will show no accuracy gain. We will measure how often greedy assembly lands below the exact optimum of the same objective. If that gap is rare, the contribution shrinks to the posteriors and the linker modeling, and we would claim only that.
Why not just read boundary probabilities off a per-residue classifier? Per-residue probabilities are not consistent with one another. They can place two high-probability cuts five residues apart, and they do not imply a distribution over the number of domains. The posteriors from our decoder come from one joint distribution over whole segmentations. The DoBo-style baseline above tests whether this coherence actually improves boundary accuracy within ±20 residues and calibration error. If the classifier's probabilities are equally calibrated, we will report that.
Why not just fold with AlphaFold and trust the structure? We do fold with AlphaFold. The question is how to decode its output under uncertainty. DPCstruct notes that noisy structures make domain calls inconsistent. The evolutionary prior is meant precisely for chains with low pLDDT between domains, and we test that on a stratified subset of such chains.
Proposed Experiments
We evaluate on CATH test chains following Chainsaw's protocol, on DoBo's DOMpro set of 628 proteins, and on AlphaFold models stratified by mean pLDDT in the region between domains.
The decisive checks are as follows. The first is the paired accuracy difference between exact and greedy decoding on identical Chainsaw matrices. The second is whether adding $e_b$ improves accuracy specifically in the low-pLDDT stratum, where the evolutionary signal should matter most. The third is calibration of the boundary posteriors, measured by expected calibration error. The fourth concerns the cases where Chainsaw and UniDoc disagree. If our posterior spreads mass across both alternatives exactly where those two tools disagree, and posterior entropy predicts errors better than Chainsaw's own confidence, the probabilistic output earns its place. The fifth is how often discontinuous domains are recovered, compared with Chainsaw. No reported result was found on Lacuna for exact dynamic-programming decoding of learned co-membership matrices, so all of these comparisons will be generated in this work.
References
- Chainsaw: protein domain segmentation with fully convolutional neural networks
- RNA Structural Segmentation
- DoBo: Protein domain boundary prediction by integrating evolutionary signals and machine learning
- Enhancing HMM-based protein profile-profile alignment with structural features and evolutionary coupling information
- Unsupervised Domain Classification of AlphaFold2-Predicted Protein Structures