2026-08-27T21:19:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27535 2026-08-27T06:04:08Z ddc:004 open_access

Minimum Flow Decomposition Guided by Saturating Subflows (Extended Abstract) Chen, Ke Talesara, Abhishek Thakkar, Sanchal Shao, Mingfu flow decomposition RNA assembly linear programming optimality gap - Introduction. The minimum flow decomposition (MFD) problem asks to decompose a directed acyclic flow network (G,f) with a unique source s and a unique sink t into the fewest weighted s-t paths whose combined contributions exactly reproduce f. MFD underlies a broad class of multi-assembly tasks in bioinformatics: reference-based RNA assembly from splice graphs [Trapnell et al., 2010; Guttman et al., 2010; Tomescu et al., 2013; Song et al., 2016; Liu et al., 2016; Pertea et al., 2015; Kovaka et al., 2019; Shao and Kingsford, 2017; Zhang et al., 2022; Tung et al., 2019], metagenomic assembly [Shaw et al., 2024], and viral quasi-species inference [Baaijens et al., 2020]. MFD is strongly NP-hard [Vatinlen et al., 2008] and hard to approximate within some fixed constant factor [Hartman et al., 2012]. Exact solvers include an FPT algorithm whose runtime grows exponentially in the solution size [Kloster et al., 2018] and a family of integer linear programming (ILP) formulations [Dias et al., 2022; Grigorjew et al., 2024] capable of handling extensions such as inexact flows [Williams et al., 2019; Dias and Tomescu, 2024], safety and subpath constraints [Williams et al., 2022; Gibney et al., 2022; Khan et al., 2022; Dias et al., 2023], and graphs with cycles [Dias et al., 2025]. However, ILP remains unscalable on large practical instances. The widely used greedy-width heuristic [Vatinlen et al., 2008] is very efficient but can be exponentially worse than optimal in the worst case [Cáceres et al., 2024]. The state-of-the-art heuristic, catfish [Shao and Kingsford, 2017], substantially improves this efficiency-performance tradeoff by identifying linear equations among edge flow values - structural constraints implied by any optimal decomposition - and resolving them via safe graph transformations. On simpler instances catfish is highly effective, but three interrelated limitations degrade its performance on complex graphs: (1) it cannot distinguish good equations (arising from a true optimal decomposition) from superficial ones that distort the graph when resolved; (2) many good equations cannot be fully resolved due to the absence of suitable closed subgraphs, so catfish discards their information entirely; and (3) when no equation is resolvable catfish falls back to greedy-width, which performs poorly on entangled graphs. - Method. We introduce catfish-LP, which augments catfish with a lightweight linear programming (LP) formulation based on saturating subflows. For each edge e ∈ E we define continuous variables {x_e(a) : a ∈ E} modeling a valid s-t subflow that saturates e; intuitively, x_e(a) represents the amount of flow on e that must passes through edge a. Five base constraints enforce saturation, symmetry, flow validity, and flow conservation. Two additional equation constraints require that the aggregate subflow through the left-hand-side edges of an equation equals that through the right-hand-side edges. The full LP is polynomial-time solvable, adding only modest overhead over catfish. The LP plays three complementary roles within a single unified framework: (1) equation filtering: if adding a candidate equation renders the LP infeasible, that equation cannot arise from any minimum decomposition and is discarded, preventing structurally invalid graph transformations; (2) safe edge merging: a feasible LP solution reveals pairs of edges that must carry identical subflow and can therefore be safely contracted; (3) informed greedy extraction: when no further simplification is possible, rather than invoking greedy-width blindly, catfish-LP extracts from the LP solution the heaviest simple path consistent with all surviving equations, deferring the error-prone greedy step as long as possible. - Experimental Results. We compare catfish-LP against greedy-width, catfish, and the optimized ILP solver [Grigorjew et al., 2024] on two benchmarks, using Gurobi [{Gurobi Optimization, 2024] as the underlying LP/ILP engine. Table 1 reports decomposition quality on four datasets of biologically derived splice graphs, with abundances estimated by Salmon [Patro et al., 2017] or simulated with the Flux-Simulator [Griebel et al., 2012]. Catfish-LP achieves the smallest excess among heuristics on the Salmon dataset and negative excess on the remaining three, matching ILP quality while being orders of magnitude faster. Figure 1 summarizes results on 1,440 simulated graphs spanning 72 complexity configurations. Catfish-LP consistently produces the smallest decompositions and recovers the most ground-truth paths among all heuristics, achieving near-ILP quality in a fraction of its runtime - including a threefold improvement over catfish on the hardest 498 instances where ILP times out on every instance. - Conclusion. Catfish-LP demonstrates that incorporating a polynomial-time LP oracle into a combinatorial heuristic yields substantial gains in decomposition quality with negligible scalability cost, addressing each of catfish’s core limitations in a unified manner. Future directions include strengthened LP formulations, domain-specific constraints for transcriptome assembly, and probabilistic interpretations of LP-guided decompositions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ke Chen and Abhishek Talesara and Sanchal Thakkar and Mingfu Shao 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.31 urn:nbn:de:0030-drops-275350 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.31 eng https://creativecommons.org/licenses/by/4.0/legalcode