Mapping What Short Reads Cannot Decide, and Spending Long Reads Only There

Standard RNA sequencing cuts each RNA molecule into fragments of 100–150 letters before reading it. A gene can splice its exons (the pieces kept in the final RNA) in many combinations. Once the molecule is fragmented, nothing records which splice choices occurred together on the same molecule. Assemblers rebuild full transcripts by treating read counts as flow through a splice graph, a directed graph whose nodes are exon segments and whose edges are observed splice junctions. They then decompose that flow into a few source-to-sink paths, each path being one transcript. The difficulty is that different sets of transcripts can produce exactly the same junction counts. For those genes, no amount of short-read depth or clever optimization can recover the true isoforms. Long reads, which sequence whole molecules, can. But the LRGASP benchmark found they are costlier and quantify rare transcripts less accurately than short reads.

This proposal uses a recent speedup to answer a question that was previously too expensive to ask. Continuous Frank-Wolfe solvers decompose a splice graph in about 0.2 ms instead of seconds. At that cost we can query the optimizer thousands of times per gene. The queries map, across the whole transcriptome, which splice-choice pairings the short-read data leave undetermined and by how much. The map has two uses. First, it becomes an uncertainty report attached to every assembled isoform. Second, it tells us where a fixed long-read budget should go: only to genes where short reads are provably ambiguous. The long reads are then folded back into the same continuous optimization as constraints, rather than used for greedy path extension.

Core Claim

The bottleneck in short-read isoform reconstruction is no longer solver speed. It is non-identifiability: the data fail to single out one answer. Cheap convex solves can measure non-identifiability directly as the range of phase, meaning how much flow can pass through paths that use both of two chosen junctions while the model still fits the reads nearly optimally. We claim three things. This phase-ambiguity interval predicts where short-read assemblies are wrong better than resampling-based uncertainty or disagreement between tools. Allocating long reads by this interval recovers more correct isoforms per long read than uniform or expression-proportional allocation. And encoding long-read subpaths as terms inside the flow-polytope objective reduces misassemblies relative to heuristic long-read path extension.

Where This Sits

Two papers supply the method. RefShannon casts genome-guided assembly as sparse flow decomposition with a parsimony principle (fewest paths that explain the counts), solved by linear programming. It uses reads spanning multiple exons as "known paths" and reports up to 22% sensitivity gains over genome-guided Trinity on HEK293T data. Efficient Sparse Flow Decomposition Methods for RNA Multi-Assembly reformulates the problem as fitting over the conic hull of the flow polytope, the set of nonnegative combinations of source-to-sink paths. It solves this with Blended Pairwise Conditional Gradient (BPCG), a Frank-Wolfe variant that never projects and adds one path per step, under least-squares or Poisson losses. It reports 0.2 ms per instance versus 3.4 s for integer programming across 81,439 DAGs, and linear convergence under quadratic growth. That paper also notes that different decompositions can yield identical flows. It then returns a single point estimate. We reuse its solver and loss functions, but treat the non-uniqueness it identifies as the object of study rather than a caveat.

Two papers motivate the gap. An isoform-resolution atlas of colorectal cancer from long-read single-cell sequencing gives the canonical four-exon example: junctions A-B, B-D, A-C and C-D cannot tell you whether B and C ever co-occur on one molecule. LRGASP shows the complementary picture. Read length decides structural identification, while short-read depth wins for quantifying lowly expressed transcripts; long-read quantifiers reach Spearman 0.74–0.87 and struggle below TPM 2. Novel isoforms supported by only one or two pipelines validate by RT-PCR at just 50–90%. Together these argue for a hybrid in which each technology does what it is good at. That requires knowing, gene by gene, where short reads fail.

Two papers constrain the design. Hybrid rnaSPAdes maps long reads onto assembly graphs and lets path extension choose several branches. This gains 8.4% more 95%-assembled genes and 13.5% more 95%-assembled isoforms on average, and 16.9% / 26.9% on MCF7 with Iso-Seq. The authors also report more misassemblies and duplication. We read that as a warning against greedy use of long reads. TransBorrow shows that agreement across assemblers is a useful reliability signal, with 44–54% more rare isoforms than StringTie2. We therefore treat tool disagreement as a serious competing ambiguity signal, not a strawman.

ELLIPSIS enforces flow conservation when estimating splicing ratios in single cells. It is adjacent but local: it quantifies inclusion ratios for individual splicing events, not phase between distant junctions. Finally, the budget-allocation framing borrows from the network resource-allocation literature in direction 2, which jointly optimizes a physical estimation layer and a scarce-resource layer. We take only the framing from that literature, not its algorithms.

Research Program

Phase-ambiguity intervals. For a gene with splice graph $G$, let $w$ be nonnegative weights on source-to-sink paths, $L(w)$ the Poisson (or least-squares) misfit to the observed edge counts, and $L^*$ its minimum. For two junctions $a$ and $b$ that no single read spans jointly, define the co-phased flow as

$$\phi_{ab}(w) = \sum_{p \ni a,\, b} w_p,$$

the total abundance of transcripts that use both junctions. The phase interval is $[\min \phi_{ab}, \max \phi_{ab}]$ over the near-optimal set $\{w : L(w) \le (1+\epsilon) L^*\}$. We normalize its width by the gene's total flow to obtain an ambiguity score.

The Frank-Wolfe machinery extends to this setting without new theory. Each Frank-Wolfe step needs a "linear oracle" that returns the single best path to add. For the penalized objective $L(w) \mp \lambda \phi_{ab}(w)$, that oracle is a shortest path in $G$ augmented with a two-bit state recording whether $a$ and $b$ have been visited. That is still a linear-time DAG search. We sweep $\lambda$ to trace the interval endpoints.

The cost scales with the number of unspanned junction pairs times the solves per sweep. This is the step that only became affordable at millisecond solve times. We will restrict attention to pairs separated by more than one fragment length, and report the actual per-gene cost.

Long reads as objective terms. A long read, after alignment, yields a chain of junctions, i.e. a subpath $s$ of $G$ with an observed count $c_s$. We add a Poisson misfit term between $c_s$ and $\sum_{p \supseteq s} w_p$, scaled by a length-dependent capture efficiency. The linear oracle again becomes a shortest path on $G$ augmented with a small automaton that tracks progress along each subpath. This is exact for a handful of subpaths per gene; beyond that we cap the state space and measure what is lost. Unlike rnaSPAdes' extension step, long reads here reweight a global fit and never force a branch.

Budgeted allocation. Given a long-read budget $B$, we choose which genes receive long-read coverage. The goal is to maximize the expected reduction in total ambiguity score, with gains discounted as reads accumulate on the same gene. We compare this against simpler allocation rules. In real experiments the selection would correspond to targeted capture panels; here we simulate it in silico by subsampling existing long-read data, as described below.

Baselines

The naive reference point is the short-read-only BPCG decomposition from Efficient Sparse Flow Decomposition Methods for RNA Multi-Assembly, run on the same splice graphs with the same loss and stopping tolerance, and reporting a single point estimate. That paper reports 0.2 ms average per DAG versus 3.4 s for integer programming. For accuracy it states only that it is "highly competitive"; we found no reported isoform-recovery number for it on Lacuna. We will therefore measure its accuracy ourselves on each dataset. Any method must beat it on isoform recovery once long reads are added. For the ambiguity scores alone, the question is whether they rank its errors correctly.

The strongest existing hybrid method is hybrid rnaSPAdes. It reports 16.9% more 95%-assembled genes and 26.9% more 95%-assembled isoforms on MCF7 with Iso-Seq, measured by rnaQUAST against short-read-only assembly. We run it on the same MCF7, GM12878 and siNT_48 data with the same long-read subsets. Beating it means reaching at least its 95%-assembled isoform count, measured with rnaQUAST, while using the same or a smaller long-read budget, and with a lower misassembly rate.

Because our method is genome-guided while rnaSPAdes is de novo, we add a second hybrid baseline. It uses our own splice graphs, but applies long reads by filtering candidate paths to those consistent with long-read chains before running BPCG. This isolates the effect of placing long reads inside the objective rather than using them as a hard pre-filter. Our in-objective version must outperform the filter on isoforms discovered solely by short reads, which the filter would discard.

For the allocation question, the competitors are uniform allocation across multi-isoform genes and expression-proportional allocation. The strongest competitor is disagreement-based allocation, which targets genes where StringTie2, Scallop and Cufflinks disagree. It is motivated by the consensus results of TransBorrow and LRGASP. All allocation rules receive identical budgets and the same downstream solver. Our rule wins if its curve of correct isoforms recovered against long-read budget lies above all three at budgets below 20% of the full long-read set. It must also reach the full-data isoform count with a smaller fraction of the reads.

The key ablation replaces the phase interval with resampling uncertainty: the spread of BPCG solutions across read-level resampling of the short reads. If resampling spread performs as well as the phase interval in either the error-ranking or the allocation test, the phase interval is unnecessary.

Why not just…?

Why not just sequence everything with long reads? LRGASP reports that long-read quantification degrades below TPM 2, and that novel-isoform calls from one or two pipelines validate at only 50–90%. So long reads alone do not settle both structure and abundance. Still, a uniform hybrid might match targeted allocation if ambiguity is spread across nearly every gene. The budget curves settle this. If the ambiguity-targeted curve converges to the uniform curve, targeting has no value and we will report that.

Why not just bootstrap a standard assembler to get uncertainty? Resampling reads perturbs the counts, but it cannot reveal decompositions that fit the counts equally well. In the four-exon example every resample returns the same paths, so the reported spread is near zero exactly where the answer is least determined. We expect resampling to capture sampling noise at low coverage and to miss phase ambiguity at high coverage. The ablation tests this directly, stratified by coverage. If resampling matches the phase interval at all coverage levels, the prediction fails.

Why not just use disagreement between assemblers as the ambiguity signal? This is the real threat, because it is cheap and it clearly predicts validation failure in LRGASP. Tools can, however, agree wrongly: heuristics that all favor high-coverage paths will make the same phase choice. Disagreement also costs several full assembler runs. We compare the two signals head-to-head on error ranking and allocation, and we also test their combination. If disagreement wins, the contribution shrinks to the in-objective long-read formulation.

Why not just unfold the solver into a neural network for speed, as in wireless beamforming? UPGANet learns step sizes for unrolled gradient ascent. It cuts runtime by up to 65% and improves sum rate by 33.5% over successive convex approximation. Here, though, solves already take milliseconds, so speed is not the bottleneck. Learned step sizes also cannot create information that the fragmented data never contained. Unfolding would at most make the interval sweep cheaper, which is an optional optimization, not the scientific question.

Proposed Experiments

We first validate calibration where ground truth exists. On simulated reads from the 81,439-DAG benchmark (human, mouse, zebrafish, salmon), true paths are known. On the Lexogen SIRV-Set 4 spike-ins in the LRGASP corpus, the synthetic spike-in isoforms are known by design. Two checks follow. The first asks whether the true co-phased flow falls inside the phase interval at the nominal rate as $\epsilon$ varies. The second asks whether interval width, compared with resampling spread and tool disagreement, better ranks genes by the reconstruction error of the short-read-only point estimate. We score ranking by area under the precision-recall curve for detecting genes with at least one wrong isoform.

Second, we run budgeted allocation on real hybrid data: MCF7, GM12878 and siNT_48 with Illumina plus PacBio or ONT reads. The full-long-read assembly, cross-checked with SQANTI3 against annotation, serves as reference. We simulate targeting by keeping long reads only for selected genes, up to a budget of 1%, 5%, 10% and 20% of the full set. For each budget we plot 95%-assembled isoforms (rnaQUAST), misassembly rate, and short-read-quantified abundance error for transcripts below TPM 2. The decisive check has two parts. At a 10% budget, ambiguity-targeted allocation with in-objective long-read terms should recover a majority of the isoform gain that the full long-read set gives over short-read-only BPCG. It should also do so with fewer misassemblies than hybrid rnaSPAdes. If disagreement-based allocation does as well, or if the gain requires most of the budget, the central claim is false.

Third, we report the cost of the transcriptome-wide ambiguity map on a full sample. This establishes whether the thousands of solves per gene are practical. If they are not, that result would be the one place where learned acceleration, including unfolding, becomes worth revisiting.