{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,3]],"date-time":"2026-11-03T01:27:36Z","timestamp":1793669256394,"version":"4.5.1"},"reference-count":56,"publisher":"SAGE Publications","issue":"11-12","license":[{"start":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T00:00:00Z","timestamp":1789689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"name":"Research Council of Finland","award":["346968"],"award-info":[{"award-number":["346968"]}],"id":[{"id":"https:\/\/ror.org\/05k73zm37","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Research Council of Finland","award":["358744"],"award-info":[{"award-number":["358744"]}],"id":[{"id":"https:\/\/ror.org\/05k73zm37","id-type":"ROR","asserted-by":"crossref"}]},{"name":"European Research Council","award":["101169716"],"award-info":[{"award-number":["101169716"]}],"id":[{"id":"https:\/\/ror.org\/0472cxd90","id-type":"ROR","asserted-by":"crossref"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computational Biology"],"published-print":{"date-parts":[[2026,12,1]]},"abstract":"<jats:p>\n                    Multi-assembly methods rely at their core on a flow decomposition problem, namely, decomposing a weighted graph into weighted paths or walks. However, most results over the past decade have focused on decompositions over directed acyclic graphs (DAGs). This limitation has led to either purely heuristic methods or, in applications, transforming a graph with cycles into a DAG via preprocessing heuristics. In this article, we show that flow decomposition problems can also be solved in practice on general graphs with cycles via a framework that yields fast and flexible mixed-integer linear programming (MILP) formulations. Our key technique relies on the graph-theoretical notion of a\n                    <jats:italic toggle=\"yes\">dominator tree<\/jats:italic>\n                    , which we use to find all\n                    <jats:italic toggle=\"yes\">safe sequences of edges<\/jats:italic>\n                    that are guaranteed to appear in some walk of any flow decomposition. We generalize previous results from DAGs to cyclic graphs by showing that maximal safe sequences correspond to extensions of common leaves of two dominator trees, and that all such sequences can be found in time linear in their size. Using these, we can accelerate MILPs for\n                    <jats:italic toggle=\"yes\">any<\/jats:italic>\n                    flow decomposition into walks in general graphs by setting suitable variables encoding solution walks to (at least) 1 and by setting to 0 other walk variables that are nonreachable to and from safe sequences. This reduces model size and eliminates costly linearizations of MILP variable products. We experiment with three decomposition models (minimum flow decomposition, least absolute errors, and minimum path error) on four bacterial datasets. Our preprocessing enables up to 1000-fold speedups and solves many instances that would otherwise time out in under 30 seconds. We thus hope that our dominator-based MILP simplification framework, together with the accompanying software library, can serve as building blocks for multi-assembly applications.\n                  <\/jats:p>","DOI":"10.1177\/15578666261486472","type":"journal-article","created":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T17:12:06Z","timestamp":1789751526000},"page":"1134-1155","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast and Flexible Flow Decompositions in General Graphs via Dominators"],"prefix":"10.1177","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3508-4473","authenticated-orcid":false,"given":"FRANCISCO","family":"SENA","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5747-8350","authenticated-orcid":false,"given":"ALEXANDRU I.","family":"TOMESCU","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2026,9,18]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","unstructured":"Alanko JN. 3682 E. coli assemblies from NCBI 2022; doi: 10.5281\/zenodo.6577997","DOI":"10.5281\/zenodo.6577997"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797317263"},{"key":"e_1_3_3_4_1","doi-asserted-by":"crossref","unstructured":"Baaijens JA Stougie L Sch\u00f6nhuth A. Strain-aware assembly of genomes from mixed samples using flow variation graphs. In International Conference on Research in Computational Molecular Biology. Springer 2020; pp. 221\u2013222.","DOI":"10.1007\/978-3-030-45257-5_14"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz443"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/COMJNL\/BXU116"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu317"},{"key":"e_1_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3641820"},{"issue":"7","key":"e_1_3_3_9_1","first-page":"1198","article-title":"Extremely fast construction and querying of compacted and colored de Bruijn graphs with GGCAT","volume":"33","author":"Cracco A","year":"2023","unstructured":"Cracco A, , Tomescu AI. Extremely fast construction and querying of compacted and colored de Bruijn graphs with GGCAT. Genome Res 2023;33(7):1198\u20131207.","journal-title":"Genome Res"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2024.3433523"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btad640"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-04749-7_14"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-025-01556-8"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2010.0243"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2022.3190282"},{"key":"e_1_3_3_16_1","first-page":"15","article-title":"Dominators in directed graphs: A survey of recent results, applications, and open problems","volume":"13","author":"Georgiadis L","year":"2013","unstructured":"Georgiadis L, , Parotsidis N. Dominators in directed graphs: A survey of recent results, applications, and open problems. Proc of ISCIM 2013;13:15\u201320.","journal-title":"Proc of ISCIM"},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.SEA.2024.14"},{"key":"e_1_3_3_18_1","unstructured":"Grigorjew A Jiamjitrak W Mumey B et al. Parameterised approximation and complexity of minimum flow decompositions 2024. 2409. 20278. Available from: https:\/\/arxiv.org\/abs\/2409.20278"},{"key":"e_1_3_3_19_1","doi-asserted-by":"crossref","unstructured":"Hartman T Hassidim A Kaplan H et al. How to split a flow? In 2012 Proceedings IEEE INFOCOM. IEEE 2012; pp. 828\u2013836.","DOI":"10.1109\/INFCOM.2012.6195830"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.suppl_1.S181"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-017-0130-5"},{"key":"e_1_3_3_22_1","doi-asserted-by":"crossref","unstructured":"Kloster K Kuinke P O\u2019Brien MP et al. A practical FPT algorithm for flow decomposition and transcript assembly. In ALENEX 2018 \u2013 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments. SIAM 2018; pp. 75\u201386.","DOI":"10.1137\/1.9781611975055.7"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-020-00971-x"},{"key":"e_1_3_3_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv033"},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33122-0_14"},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-019-1690-7"},{"key":"e_1_3_3_27_1","doi-asserted-by":"crossref","unstructured":"Luo R Lin Y. Vstrains: De novo reconstruction of viral strains via iterative path extraction from assembly graphs. In International Conference on Research in Computational Molecular Biology. Springer 2023; pp. 3\u201320.","DOI":"10.1007\/978-3-031-29119-7_1"},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-021-02587-6"},{"key":"e_1_3_3_29_1","first-page":"41","volume-title":"Graphs and Order: the role of graphs in the theory of ordered sets and its applications","author":"M\u00f6hring R","year":"1984","unstructured":"M\u00f6hring R. Algorithmic aspects of comparability graphs and interval graphs. In Rival I. (ed.) Graphs and Order: the role of graphs in the theory of ordered sets and its applications. D. Reidel Publishing Company; 1984; pp. 41\u2013101."},{"key":"e_1_3_3_30_1","doi-asserted-by":"crossref","unstructured":"Mumey B Shahmohammadi S McManus K et al. Parity balancing path flow decomposition and routing. In 2015 IEEE Globecom Workshops (GC Wkshps). IEEE 2015; pp. 1\u20136.","DOI":"10.1109\/GLOCOMW.2015.7414053"},{"key":"e_1_3_3_31_1","doi-asserted-by":"crossref","unstructured":"Namiki T Hachiya T Tanaka H et al. Metavelvet: An extension of velvet assembler to de novo metagenome assembly from short sequence reads. In Proceedings of the 2nd ACM conference on bioinformatics computational biology and biomedicine. 2011; pp. 116\u2013124.","DOI":"10.1145\/2147805.2147818"},{"key":"e_1_3_3_32_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.213959.116"},{"key":"e_1_3_3_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btr216"},{"key":"e_1_3_3_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btad264"},{"key":"e_1_3_3_35_1","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbp026"},{"key":"e_1_3_3_36_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41587-022-01565-y"},{"key":"e_1_3_3_37_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-S9-S5"},{"key":"e_1_3_3_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ygeno.2013.10.003"},{"key":"e_1_3_3_39_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-021-26944-y"},{"key":"e_1_3_3_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.isci.2024.111208"},{"key":"e_1_3_3_41_1","unstructured":"Sena F Rizzi R Tomescu AI. Safe sequences via dominators in DAGs for path-covering problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). 2025 Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik pp. 55\u20131."},{"key":"e_1_3_3_42_1","doi-asserted-by":"publisher","DOI":"10.3389\/fmicb.2022.981458"},{"key":"e_1_3_3_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2017.2779509"},{"key":"e_1_3_3_44_1","doi-asserted-by":"publisher","DOI":"10.1038\/sdata.2016.81"},{"key":"e_1_3_3_45_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkw158"},{"key":"e_1_3_3_46_1","unstructured":"Stinzend\u00f6rfer M Schiewe P Oliveira F. A robust optimization approach to flow decomposition. arXiv Preprint 2024arXiv:241021140"},{"key":"e_1_3_3_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_3_48_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-025-06045-z"},{"key":"e_1_3_3_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2015.2418753"},{"key":"e_1_3_3_50_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-S5-S15"},{"key":"e_1_3_3_51_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1003515"},{"key":"e_1_3_3_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.05.043"},{"key":"e_1_3_3_53_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-021-24515-9"},{"key":"e_1_3_3_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2022.3147697"},{"key":"e_1_3_3_55_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-12-162"},{"key":"e_1_3_3_56_1","doi-asserted-by":"publisher","DOI":"10.1038\/s43588-022-00216-1"},{"key":"e_1_3_3_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2021.3083277"}],"container-title":["Journal of Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666261486472","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/15578666261486472","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666261486472","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,11,3]],"date-time":"2026-11-03T00:46:33Z","timestamp":1793666793000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/15578666261486472"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9,18]]},"references-count":56,"journal-issue":{"issue":"11-12","published-print":{"date-parts":[[2026,12,1]]}},"alternative-id":["10.1177\/15578666261486472"],"URL":"https:\/\/doi.org\/10.1177\/15578666261486472","relation":{},"ISSN":["1066-5277","1557-8666"],"issn-type":[{"value":"1066-5277","type":"print"},{"value":"1557-8666","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,9,18]]}}}