Local Alignment Kernels for Predicting Progression-Free Survival from Treatment Histories

Many cancer patients have a long, irregular record of clinical events before their outcome is measured: diagnoses, metastasis sites, lines of chemotherapy or endocrine therapy, switches, and recurrences. Two patients can share the clinically decisive part of that story, such as "liver metastasis, then a taxane, then an early switch," while differing everywhere else and in record length. We propose to predict progression-free survival (PFS), the time until the disease measurably worsens or the patient dies, by finding past patients whose treatment histories contain locally similar stretches and pooling their observed outcomes into an individualized survival curve.

The similarity measure is the local alignment kernel. Like the Smith-Waterman algorithm, it compares two sequences by matching substretches with gaps allowed. Unlike Smith-Waterman, it sums over every possible local alignment rather than keeping only the best one. The pooling step is Beran's conditional Kaplan-Meier estimator, which builds a survival curve from neighbours weighted by similarity. We learn the alignment's scoring parameters end to end from survival likelihood. The claim to test is that on sparse, short, variable-length clinical event sequences, this combination predicts PFS at least as well as tensorized recurrent networks with a fixed log-normal survival head. It should also give non-parametric, calibrated curves and an explanation of each prediction that a clinician can inspect: "these aligned stretches of these past patients."

Where this sits

The local alignment kernel was developed for biological sequences. Salomon and Flower argue that summing over all local alignments keeps suboptimal alignments that carry signal, and they use it for MHC class II peptide binding. Liu et al. combine it with profile representations for remote homology detection, and Katrenko and Adriaans use it for relation extraction in text. These papers supply the mechanism. None of them applies it to time-to-event outcomes or to non-molecular event sequences. Two known weaknesses of these kernels constrain the design. They are sensitive to the decay and gap parameters, which can produce "diagonal dominance," where each sequence looks similar only to itself. Exact computation also scales quadratically in the number of samples, which motivated Tabei et al. to build space-efficient feature maps.

On the survival side, Deep Kernel Survival Analysis learns a neural embedding whose distances define the weights of Beran's estimator. It trains with a leave-one-out survival likelihood and adds conformal prediction intervals. Survival Kernets compress the training set into exemplar clusters to make this scale. Both papers supply the estimator and the training recipe. Both work only on fixed-width tabular vectors and on overall mortality, not PFS. Benchmarking PFS Ratio uses a kernel-smoothed Kaplan-Meier estimator to handle informative censoring in the intra-patient ratio PFS2/PFS1, but its kernel smooths scalar times and uses no covariates.

The closest existing work is Yang et al.. It models PFS in metastatic breast cancer from 196 sequential event types plus 118 static features in the PRAEGNANT network. It uses tensor-train recurrent networks whose weight matrices are factorized to about 1% of the usual parameters, feeding a log-normal accelerated failure time (AFT) head. Our proposal changes both halves of that design:

  • the recurrent encoder is replaced by an alignment kernel that compares histories directly;
  • the parametric head is replaced by a non-parametric neighbour-based estimator.

Core Claim

Treatment histories are short (PRAEGNANT averages 7.54 events per patient, per Yang et al.), gapped, and differ mostly in local motifs. For data of this kind, a learned local alignment kernel inside Beran's estimator is the appropriate inductive bias. Concretely:

  • it should match or beat TT-LSTM with an AFT head on PFS error;
  • it should clearly beat it on calibration;
  • its advantage should disappear when event order is destroyed, which shows that local order is what the model is using.

For two event sequences $x$ and $y$, the kernel is

$$K_\theta(x,y)=\sum_{\pi\in\Pi(x,y)}\exp\big(\beta\, s_\theta(x,y,\pi)\big),$$

where:

  • $\Pi(x,y)$ is the set of all local alignments;
  • $s_\theta$ is an alignment's score, made of substitution scores between aligned event codes minus gap costs;
  • $\beta>0$ is an inverse temperature;
  • $\theta$ collects the learnable substitution and gap parameters.

The predicted survival curve for a new patient $x$ is Beran's estimator

$$\hat S(t\mid x)=\prod_{i:\,t_i\le t,\ \delta_i=1}\Big(1-\frac{w_i(x)}{\sum_{j:\,t_j\ge t_i} w_j(x)}\Big),$$

where:

  • $t_i$ is training patient $i$'s observed PFS time;
  • $\delta_i$ is $1$ if progression or death was observed and $0$ if the patient was censored;
  • $w_i(x)$ is a normalized similarity weight derived from $K_\theta$.

Research Program

Making the kernel usable on clinical codes. Clinical codes have no BLOSUM-style substitution matrix. We give each code a low-dimensional embedding and score a substitution as the inner product of two embeddings. The embeddings are initialized from co-occurrence statistics and then learned.

Beran's estimator needs only nonnegative weights, not a positive semi-definite kernel. That frees us to fight diagonal dominance directly. We set

$$w_i(x)=\exp\!\big(\tau\,[\log K(x,x_i)-\tfrac12\log K(x,x)-\tfrac12\log K(x_i,x_i)]\big),$$

where $\tau>0$ is a learned temperature. This is a self-normalized log-kernel, so it compares sequences of very different lengths on one scale.

Gaps that reflect elapsed time. Gaps are charged by elapsed calendar time rather than by the number of skipped events. Two identical drug switches six weeks apart and six years apart should not count as equally aligned.

Training. The dynamic program is a sum of products, so it is differentiable. We train $\theta$, $\beta$, and $\tau$ with the leave-one-out survival likelihood of Deep Kernel Survival Analysis. Static features enter through a product with a standard tabular kernel.

Cost. With about 4,357 patients and sequences of roughly 8 events, all pairwise alignments amount to roughly $10^9$ cell updates per epoch, which is cheap on a GPU. Kernel netting from Survival Kernets is held in reserve for larger registries.

Explanations. For each prediction we report the highest-weight neighbours and the posterior probability of each aligned event pair. Clinicians can check these against known treatment patterns.

Baselines

Naive reference. A population Kaplan-Meier curve that ignores every covariate, together with its median as a point prediction. Any model that cannot beat this on integrated Brier score has learned nothing.

Strongest existing method: TT-LSTM with a log-normal AFT head from Yang et al.. It is the only cited model built for exactly this data and endpoint. That paper reports, on PRAEGNANT, a median absolute error in PFS prediction of:

  • 132.9 days for TT-LSTM;
  • 136.8 days for an embedding-enhanced LSTM;
  • 159.5 days for a plain LSTM.

We will reimplement TT-LSTM and rerun it on our own splits rather than compare against the published figure across protocols. It gets the same static features, the same train/validation/test splits, and the same hyperparameter-search budget, measured in trials and GPU-hours. Beating it means two things on held-out data. First, lower median absolute error under its own protocol, with the 132.9-day figure as a sanity anchor for our reimplementation. Second, a significantly better integrated Brier score and calibration slope, tested by a paired bootstrap over patients.

Strongest kernel-survival competitor. Neural Kernel Survival from Deep Kernel Survival Analysis, run on bag-of-codes count vectors plus static features. It shares our estimator and training loss and differs only in being blind to order. No reported result was found on Lacuna for neural kernel survival on PFS or on PRAEGNANT.

Ablations that isolate the key ingredients. Four variants each remove one ingredient:

  • replacing the sum over alignments with the single best Smith-Waterman alignment;
  • replacing time-scaled gaps with count-based gaps;
  • freezing substitution scores at identity (a match scores 1 and anything else 0);
  • applying the full model to sequences whose event order has been randomly permuted within each patient.

Why not just…?

Why not just run Cox regression or a random survival forest on bag-of-codes counts? This is a real threat. With histories this short, which events occurred may matter far more than their order. The order-permutation ablation and the bag-of-codes neural kernel survival baseline settle it directly. If the permuted model performs as well as the full one, the honest conclusion is that alignment adds nothing for this endpoint. We would then report that rather than argue around it.

Why not just keep the LSTM and attach a non-parametric head? An LSTM embedding fed into Beran's estimator is a fair hybrid, and we include it as an additional baseline. The alignment kernel's case rests on small-data behaviour and inspectability, not on raw capacity. Yang et al. needed tensor factorization precisely because recurrent input layers blow up on 196 sparse codes. We will compare learning curves at 10%, 25%, 50%, and 100% of the training data.

Why not just use edit distance or dynamic time warping as the similarity? These are global, single-best alignments. They force the start and end of two histories to correspond and discard near-optimal matches, which is the weakness Salomon and Flower highlight. The sum-versus-max ablation and an edit-distance-weighted Beran baseline test whether that argument holds for clinical events.

Why not just fit TT-LSTM with a more flexible parametric distribution? A mixture-of-Weibull head would partly answer the misspecification critique. We include it so that any calibration gain cannot be attributed simply to replacing a log-normal distribution.

Proposed Experiments

Synthetic benchmark. Before touching clinical data, we generate event sequences from a 200-code vocabulary with planted gapped motifs. Each motif shifts a Weibull hazard, and censoring is set at 10–40%. This covers the censoring regime where Benchmarking PFS Ratio found naive estimators diverging. The benchmark is a decisive test of whether the learned kernel recovers the motifs. The aligned-pair posteriors among the top neighbours should concentrate on planted motif positions. The model should also beat bag-of-codes only when the motif's order matters, and tie it when it does not.

Main study. The PRAEGNANT cohort, using the 118 static features and 196 sequential event types described by Yang et al.. Data access is the main practical risk. If access is refused, the study moves to an institutional metastatic breast cancer registry with the same structure, and the published figure serves only as context.

Metrics. We report:

  • median absolute error, to match the prior work;
  • time-dependent concordance index;
  • integrated Brier score;
  • calibration slope at 6 and 12 months;
  • coverage of weighted split-conformal 80% intervals, following Deep Kernel Survival Analysis.

Every comparison uses five repeated splits stratified by censoring status.

Robustness check. PFS dates depend on scan schedules. We re-score test patients after coarsening their progression times to 8- and 12-week scan grids. This tests whether rankings between methods survive the interval-censoring bias noted for imaging-based endpoints.

Pre-registered outcome. The project counts as a positive result only if all three of the following hold:

  • the full model beats TT-LSTM on integrated Brier score;
  • the full model beats the permuted-order version of itself;
  • summing over all alignments beats the single best alignment.

If any of the three fails, the paper reports which property of clinical event sequences made local alignment unnecessary.