License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2022.17
URN: urn:nbn:de:0030-drops-170516
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17051/
Gibney, Daniel ;
Thankachan, Sharma V. ;
Aluru, Srinivas
Feasibility of Flow Decomposition with Subpath Constraints in Linear Time
Abstract
The decomposition of flow-networks 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 polynomial-time o(log |V|)-approximation algorithm and (ii) does not admit a polynomial-time 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:1--17:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-243-3},
ISSN = {1868-8969},
year = {2022},
volume = {242},
editor = {Boucher, Christina and Rahmann, Sven},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17051},
URN = {urn:nbn:de:0030-drops-170516},
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 |
