Abstract
The decomposition of flownetworks is an essential part of many transcriptome assembly algorithms used in Computational Biology. The addition of subpath constraints to this decomposition appeared recently as an effective way to incorporate longer, already known, portions of the transcript. The problem is defined as follows: given a weakly connected directed acyclic flow network G = (V, E, f) and a set ℛ of subpaths in G, find a flow decomposition so that every subpath in ℛ is included in some flow in the decomposition [Williams et al., WABI 2021]. The authors of that work presented an exponential time algorithm for determining the feasibility of such a flow decomposition, and more recently presented an O(E + L+ℛ³) time algorithm, where L is the sum of the path lengths in ℛ [Williams et al., TCBB 2022]. Our work provides an improved, linear O(E + L) time algorithm for determining the feasibility of such a flow decomposition. We also introduce two natural optimization variants of the feasibility problem: (i) determining the minimum sized subset of ℛ that must be removed to make a flow decomposition feasible, and (ii) determining the maximum sized subset of ℛ that can be maintained while making a flow decomposition feasible. We show that, under the assumption P ≠ NP, (i) does not admit a polynomialtime o(log V)approximation algorithm and (ii) does not admit a polynomialtime O(V^{1/2ε} + ℛ^{1ε})approximation algorithm for any constant ε > 0.
BibTeX  Entry
@InProceedings{gibney_et_al:LIPIcs.WABI.2022.17,
author = {Gibney, Daniel and Thankachan, Sharma V. and Aluru, Srinivas},
title = {{Feasibility of Flow Decomposition with Subpath Constraints in Linear Time}},
booktitle = {22nd International Workshop on Algorithms in Bioinformatics (WABI 2022)},
pages = {17:117:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772433},
ISSN = {18688969},
year = {2022},
volume = {242},
editor = {Boucher, Christina and Rahmann, Sven},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17051},
URN = {urn:nbn:de:0030drops170516},
doi = {10.4230/LIPIcs.WABI.2022.17},
annote = {Keywords: Flow networks, flow decomposition, subpath constraints}
}
Keywords: 

Flow networks, flow decomposition, subpath constraints 
Collection: 

22nd International Workshop on Algorithms in Bioinformatics (WABI 2022) 
Issue Date: 

2022 
Date of publication: 

26.08.2022 