Efficient Minimum Flow Decomposition via Integer Linear Programming

Journal of computational biology: A journal of computational molecular cell biology

article

Fernando H.C. Dias¹  Lucia Williams²  Brendan Mumey²  Alexandru I. Tomescu¹ 

[1] Department of Computer Science, University of Helsinki;School of Computing, Montana State University

关键词: flow decomposition;    integer linear programming;    multiassembly and RNA assembly;    network flow;   

DOI  :  10.1089/cmb.2022.0257

学科分类：生物科学（综合）

来源: Mary Ann Liebert, Inc. Publishers

【 摘 要 】

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.

【 授权许可】

Unknown