Open AccessEfficient Minimum Flow Decomposition via Integer Linear Programming
Author(s) -
Fernando H. C. Dias,
Lucia Williams,
Brendan Mumey,
Alexandru I. Tomescu
Publication year - 2022
Publication title -
journal of computational biology
Language(s) - Uncategorized
Resource type - Journals
SCImago Journal Rank - 0.585
H-Index - 95
eISSN - 1557-8666
pISSN - 1066-5277
DOI - 10.1089/cmb.2022.0257
Subject(s) - heuristics , integer programming , solver , heuristic , flow (mathematics) , flow network , mathematical optimization , set (abstract data type) , linear programming , integer (computer science) , computer science , decomposition , multi commodity flow problem , maximum flow problem , minimum cut , quadratic equation , mathematics , algorithm , ecology , geometry , biology , programming language
Minimum flow decomposition (MFD) is an NP-hard problem asking to decompose a network flow into a minimum set of paths (together with associated weights). Variants of it are powerful models in multiassembly problems in Bioinformatics, such as RNA assembly. Owing to its hardness, practical multiassembly tools either use heuristics or solve simpler, polynomial time-solvable versions of the problem, which may yield solutions that are not minimal or do not perfectly decompose the flow. Here, we provide the first fast and exact solver for MFD on acyclic flow networks, based on Integer Linear Programming (ILP). Key to our approach is an encoding of all the exponentially many solution paths using only a quadratic number of variables. We also extend our ILP formulation to many practical variants, such as incorporating longer or paired-end reads, or minimizing flow errors. On both simulated and real-flow splicing graphs, our approach solves any instance in <13 seconds. We hope that our formulations can lie at the core of future practical RNA assembly tools. Our implementations are freely available on Github.