A safety framework for flow decomposition problems via integer linear programming.

ABSTRACT:

Motivation

Many important problems in Bioinformatics (e.g. assembly or multiassembly) admit multiple solutions, while the final objective is to report only one. A common approach to deal with this uncertainty is finding "safe" partial solutions (e.g. contigs) which are common to all solutions. Previous research on safety has focused on polynomially time solvable problems, whereas many successful and natural models are NP-hard to solve, leaving a lack of "safety tools" for such problems. We propose the first method for computing all safe solutions for an NP-hard problem, "minimum flow decomposition" (MFD). We obtain our results by developing a "safety test" for paths based on a general integer linear programming (ILP) formulation. Moreover, we provide implementations with practical

SUBMITTER: Dias FHC 

PROVIDER: S-EPMC10628435 | biostudies-literature | 2023 Nov

REPOSITORIES: biostudies-literature