Accurate Flow Decomposition via Robust Integer Linear Programming

Abstract

Minimum flow decomposition (MFD) is a common problem across various fields of Computer Science, where a flow is decomposed into a minimum set of weighted paths. However, in Bioinformatics applications, such as RNA transcript or quasi-species assembly, the flow is erroneous, since is obtained from noisy read coverages. Typical generalizations of the MFD problem to handle errors are based on least-squares formulations, or on modeling the erroneous flow values as ranges. All of these are thus focused on error-handling at the level of individual edges. Interpreting the flow decomposition problem as a robust optimization problem, we lift error-handling from individual edges to solution paths. As such, we introduce a new minimum path-error flow decomposition problem, for which we give an efficient Integer Linear Programming formulation. Our experimental results reveal that our formulation can account for errors with an accuracy significantly surpassing that of previous error-handling formulations, with computational requirements that remain practical.