Abstract
Decomposing a flow on a Directed Acyclic Graph (DAG) into a weighted sum of a small number of paths is an essential task in operations research and bioinformatics. This problem, referred to as Sparse Flow Decomposition (SFD), has gained significant interest, in particular for its application in RNA transcript multi-assembly, the identification of the multiple transcripts corresponding to a given gene and their relative abundance. Several recent approaches cast SFD variants as integer optimization problems, motivated by the NP-hardness of the formulations they consider. We propose an alternative formulation of SFD as a fitting problem on the conic hull of the flow polytope. By reformulating the problem on the flow polytope for compactness and solving it using specific variants of the Frank-Wolfe algorithm, we obtain a method converging rapidly to the minimizer of the chosen loss function while producing a parsimonious decomposition. Our approach subsumes previous formulations of SFD with exact and inexact flows and can model different priors on the error distributions. Computational experiments show that our method outperforms recent integer optimization approaches in runtime, but is also highly competitive in terms of reconstruction of the underlying transcripts, despite not explicitly minimizing the solution cardinality.
Introduction
In transcriptomics, a single gene can produce multiple distinct RNA molecules (transcripts) through alternative splicing. To understand this biological complexity, researchers use splice graphs, where nodes represent exons and edges represent their connections. The observable data in these experiments is the "flow"—the abundance of sequencing reads—along the edges of the graph. The challenge of RNA transcript multi-assembly lies in decomposing this total flow into a weighted sum of a small number of paths, where each path corresponds to a specific transcript and its weight reflects its abundance.
The Sparse Flow Decomposition (SFD) Problem
Historically, SFD has been treated as a minimum path problem, typically solved using Integer Programming (IP). However, IP-based methods are computationally expensive (NP-hard) and often struggle with the "inexact" data common in real-world biological measurements due to sequencing noise.
As shown in the figure above, a single flow can often be decomposed in multiple ways. The goal is to find a decomposition that is both biologically plausible (parsimonious) and statistically consistent with the observed data.
Methodology: A Continuous Optimization Approach
This paper proposes a shift from discrete integer constraints to a continuous data-fitting framework. By treating sparsity as a byproduct of the optimization process rather than a hard constraint, the authors leverage the efficiency of first-order methods.
- Convex Reformulation: The problem is formulated as a minimization over the flow polytope. The authors explore two primary loss functions: Least-squares (for Gaussian noise) and Poisson log-likelihood (optimized for count-based sequencing data).
- Frank-Wolfe (FW) Algorithms: The researchers utilize the Blended Pairwise Conditional Gradient (BPCG) variant of the Frank-Wolfe algorithm. FW methods are inherently "projection-free" and naturally produce sparse solutions because they construct the result as a convex combination of a few vertices (paths) at a time.
- Algorithmic Sparsity: A key insight is that explicit cardinality minimization is not strictly necessary. The FW algorithm's tendency to select few vertices effectively identifies the "active set" of transcripts needed to explain the data.
Experimental Evaluation
The proposed methods were evaluated on a massive benchmark of 81,439 Directed Acyclic Graphs derived from human, zebrafish, salmon, and mouse genomes. This dataset includes "inexact" instances to simulate real-world sequencing errors.
Key Results
- Speed: The FW-based methods achieved a massive speedup. On average, the FW approach required only 0.2 milliseconds per instance, compared to 3.4 seconds for traditional IP models—a difference of four orders of magnitude.
- Accuracy and Robustness: Despite the lack of explicit cardinality minimization, the FW methods were highly competitive in transcript reconstruction. Furthermore, they handled noisy, inconsistent data much more gracefully than IP models, which frequently failed to find solutions when flow conservation was violated.
- Convergence: The authors proved that the least-squares formulation satisfies a quadratic growth property, ensuring fast linear convergence despite the objective function not being strongly convex.
Conclusion
By reframing Sparse Flow Decomposition as a continuous fitting problem on the flow polytope, this work demonstrates that first-order optimization can replace expensive integer programming for RNA multi-assembly. The Frank-Wolfe framework provides a robust, scalable, and biologically accurate solution that is ready for the demands of modern high-throughput transcriptomics.
Summary updated