{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"institution":[{"name":"bioRxiv"}],"indexed":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T14:23:00Z","timestamp":1783347780691,"version":"3.54.6"},"posted":{"date-parts":[[2025,12,12]]},"group-title":"Bioinformatics","reference-count":29,"publisher":"openRxiv","license":[{"start":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T00:00:00Z","timestamp":1765497600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["2145171"],"award-info":[{"award-number":["2145171"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000002","name":"US National Institutes of Health","doi-asserted-by":"crossref","award":["R01HG011065"],"award-info":[{"award-number":["R01HG011065"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2026,7,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                <jats:p>\n                  The minimum flow decomposition problem abstracts a set of key tasks in bioinformatics, including metagenome and transcriptome assembly. These tasks, collectively known as multi-assembly, aim to reconstruct multiple genomic sequences from reads obtained from mixed samples. The reads are first organized into a directed graph (e.g., overlap graph, splice graph), where each edge has an integer weight representing the number of supporting reads. By viewing the graph as a flow network, the underlying sequences and their abundances can be extracted through decomposition into a minimum number of weighted paths. Although this problem is NP-hard, prior work has proposed an efficient heuristic that transforms the graph by identifying nontrivial equations in the flow values. However, for graphs with complex structures, many equations cannot be fully resolved by existing mechanisms, leading to suboptimal decompositions. In this study, we revisit the theoretical framework of the flow decomposition problem and extend the equation-resolving mechanisms to jointly model all equations in the graph, enabling safe merge operations that iteratively simplify the graph. Experimental results demonstrate that our new algorithm substantially improves decomposition quality over existing heuristics, achieving near-optimal solutions for complex graphs, while running several orders of magnitude faster than the ILP formulation. Source code of our algorithm is available at\n                  <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/Shao-Group\/catfish-LP\">https:\/\/github.com\/Shao-Group\/catfish-LP<\/jats:ext-link>\n                  .\n                <\/jats:p>","DOI":"10.64898\/2025.12.11.693570","type":"posted-content","created":{"date-parts":[[2025,12,13]],"date-time":"2025-12-13T07:00:22Z","timestamp":1765609222000},"source":"Crossref","is-referenced-by-count":0,"title":["Minimum flow decomposition guided by saturating subflows"],"prefix":"10.64898","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5470-6621","authenticated-orcid":false,"given":"Ke","family":"Chen","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University, PA 16803, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abhishek","family":"Talesara","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University, PA 16803, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-8910-0920","authenticated-orcid":false,"given":"Sanchal","family":"Thakkar","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University, PA 16803, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6112-5139","authenticated-orcid":false,"given":"Mingfu","family":"Shao","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, The Pennsylvania State University, PA 16803, USA"},{"name":"Huck Institutes of the Life Sciences, The Pennsylvania State University, PA 16803, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"54368","reference":[{"key":"2026070606250746000_2025.12.11.693570v3.1","doi-asserted-by":"crossref","unstructured":"Jasmijn A Baaijens , Leen Stougie , and Alexander Sch\u00f6nhuth. Strain-aware assembly of genomes from mixed samples using flow variation graphs. In International Conference on Research in Computational Molecular Biology, pages 221\u2013222. Springer, 2020.","DOI":"10.1007\/978-3-030-45257-5_14"},{"issue":"2","key":"2026070606250746000_2025.12.11.693570v3.2","first-page":"1","article-title":"Width helps and hinders splitting flows","volume":"20","year":"2024","journal-title":"ACM Transactions on Algorithms"},{"issue":"11","key":"2026070606250746000_2025.12.11.693570v3.3","doi-asserted-by":"crossref","first-page":"btad640","DOI":"10.1093\/bioinformatics\/btad640","article-title":"A safety framework for flow decomposition problems via integer linear programming","volume":"39","year":"2023","journal-title":"Bioinformatics"},{"key":"2026070606250746000_2025.12.11.693570v3.4","unstructured":"Fernando HC Dias and Alexandru I Tomescu . Accurate flow decomposition via robust integer linear programming. IEEE\/ACM Transactions on Computational Biology and Bioinformatics, 2024."},{"issue":"11","key":"2026070606250746000_2025.12.11.693570v3.5","doi-asserted-by":"crossref","first-page":"1252","DOI":"10.1089\/cmb.2022.0257","article-title":"Efficient minimum flow decomposition via integer linear programming","volume":"29","year":"2022","journal-title":"Journal of Computational Biology"},{"key":"2026070606250746000_2025.12.11.693570v3.6","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1007\/s10898-025-01556-8","article-title":"Minimum flow decomposition in graphs with cycles using integer linear programming","volume":"93","year":"2025","journal-title":"Journal of Global Optimization"},{"key":"2026070606250746000_2025.12.11.693570v3.7","unstructured":"Daniel Gibney , V Sharma , Srinivas Aluru , et al. Feasibility of flow decomposition with subpath constraints in linear time. In 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022), 2022."},{"key":"2026070606250746000_2025.12.11.693570v3.8","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gks666"},{"key":"2026070606250746000_2025.12.11.693570v3.9","unstructured":"Andreas Grigorjew , Fernando HC Dias , Andrea Cracco , Romeo Rizzi , and Alexandru I Tomescu . Accelerating ILP solvers for minimum flow decompositions through search space and dimensionality reductions. In 22nd International Symposium on Experimental Algorithms (SEA 2024), pages 14\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 2024."},{"key":"2026070606250746000_2025.12.11.693570v3.10","unstructured":"Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024."},{"key":"2026070606250746000_2025.12.11.693570v3.11","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.1633"},{"key":"2026070606250746000_2025.12.11.693570v3.12","doi-asserted-by":"crossref","unstructured":"Tzvika Hartman , Avinatan Hassidim , Haim Kaplan , Danny Raz , and Michal Segalov . How to split a flow? In 2012 Proceedings IEEE INFOCOM, pages 828\u2013836. IEEE, 2012.","DOI":"10.1109\/INFCOM.2012.6195830"},{"issue":"12","key":"2026070606250746000_2025.12.11.693570v3.13","doi-asserted-by":"crossref","first-page":"1270","DOI":"10.1089\/cmb.2022.0261","article-title":"Improving RNA assembly via safety and completeness in flow decompositions","volume":"29","year":"2022","journal-title":"Journal of Computational Biology"},{"key":"2026070606250746000_2025.12.11.693570v3.14","doi-asserted-by":"crossref","unstructured":"Kyle Kloster , Philipp Kuinke , Michael P O\u2019Brien , Felix Reidl , Fernando S\u00e1nchez Villaamil , Blair D Sullivan , and Andrew van der Poel . A practical FPT algorithm for flow decomposition and transcript assembly. In 2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 75\u201386. SIAM, 2018.","DOI":"10.1137\/1.9781611975055.7"},{"key":"2026070606250746000_2025.12.11.693570v3.15","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-019-1727-y"},{"key":"2026070606250746000_2025.12.11.693570v3.16","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-015-0866-z"},{"issue":"4","key":"2026070606250746000_2025.12.11.693570v3.17","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1038\/nmeth.4197","article-title":"Salmon provides fast and bias-aware quantification of transcript expression","volume":"14","year":"2017","journal-title":"Nature methods"},{"key":"2026070606250746000_2025.12.11.693570v3.18","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.3122"},{"key":"2026070606250746000_2025.12.11.693570v3.19","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.4020"},{"issue":"2","key":"2026070606250746000_2025.12.11.693570v3.20","first-page":"658","article-title":"Theory and a heuristic for the minimum path flow decomposition problem","volume":"16","year":"2017","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"2026070606250746000_2025.12.11.693570v3.21","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btae252"},{"key":"2026070606250746000_2025.12.11.693570v3.22","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkw158"},{"key":"2026070606250746000_2025.12.11.693570v3.23","doi-asserted-by":"crossref","unstructured":"Alexandru I Tomescu , Anna Kuosmanen , Romeo Rizzi , and Veli M\u00e4kinen . A novel min-cost flow method for estimating transcript expression with RNA-Seq. In BMC Bioinformatics, volume 14, pages 1\u201310. Springer, 2013.","DOI":"10.1186\/1471-2105-14-S5-S15"},{"key":"2026070606250746000_2025.12.11.693570v3.24","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.1621"},{"key":"2026070606250746000_2025.12.11.693570v3.25","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-019-1727-y"},{"issue":"3","key":"2026070606250746000_2025.12.11.693570v3.26","doi-asserted-by":"crossref","first-page":"1390","DOI":"10.1016\/j.ejor.2006.05.043","article-title":"Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths","volume":"185","year":"2008","journal-title":"Euro-pean Journal of Operational Research"},{"key":"2026070606250746000_2025.12.11.693570v3.27","doi-asserted-by":"crossref","unstructured":"Lucia Williams , Gillian Reynolds , and Brendan Mumey . Rna transcript assembly using inexact flows. In 2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 1907\u20131914. IEEE, 2019.","DOI":"10.1109\/BIBM47256.2019.8983180"},{"issue":"1","key":"2026070606250746000_2025.12.11.693570v3.28","first-page":"360","article-title":"Flow decomposition with sub-path constraints","volume":"20","year":"2022","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"issue":"3","key":"2026070606250746000_2025.12.11.693570v3.29","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1038\/s43588-022-00216-1","article-title":"Accurate assembly of multi-end RNA-Seq data with Scallop2","volume":"2","year":"2022","journal-title":"Nature Computational Science"}],"container-title":[],"original-title":[],"link":[{"URL":"https:\/\/syndication.highwire.org\/content\/doi\/10.64898\/2025.12.11.693570","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T13:27:34Z","timestamp":1783344454000},"score":1,"resource":{"primary":{"URL":"http:\/\/biorxiv.org\/lookup\/doi\/10.64898\/2025.12.11.693570"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,12]]},"references-count":29,"URL":"https:\/\/doi.org\/10.64898\/2025.12.11.693570","relation":{},"subject":[],"published":{"date-parts":[[2025,12,12]]},"subtype":"preprint"}}