The flow decomposition problem asks to decompose a flow in a graph into weighted paths. In Bioinformatics, this has applications in multiassembly problems (of RNA transcripts or viral quasispecies, e.g., HIV, or SARS-CoV-2). The state-of-the-art around this problem is lacking both in theory, and in practice, with Bioinformatics multiassembly software having a precision of just 50% on some datasets. This project aims to develop the algorithmic theory around this problem, that could provide practitioners with solid algorithmic building blocks usable by future multiassembly methods. By also implementing the best of our algorithms, we aim to develop practical Bioinformatics software with a significantly improved precision arising from our new exact algorithms, from incorporating all the available information, and from properly handling the issue of multiple optimal multiassembly solutions.

2022

2026