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.2021.16
URN: urn:nbn:de:0030-drops-143695
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14369/
Go to the corresponding LIPIcs Volume Portal

Williams, Lucia ; Tomescu, Alexandru I. ; Mumey, Brendan

Flow Decomposition with Subpath Constraints

pdf-format:
LIPIcs-WABI-2021-16.pdf (0.7 MB)

Abstract

Flow network decomposition is a natural model for problems where we are given a flow network arising from superimposing a set of weighted paths and would like to recover the underlying data, i.e., decompose the flow into the original paths and their weights. Thus, variations on flow decomposition are often used as subroutines in multiassembly problems such as RNA transcript assembly. In practice, we frequently have access to information beyond flow values in the form of subpaths, and many tools incorporate these heuristically. But despite acknowledging their utility in practice, previous work has not formally addressed the effect of subpath constraints on the accuracy of flow network decomposition approaches. We formalize the flow decomposition with subpath constraints problem, give the first algorithms for it, and study its usefulness for recovering ground truth decompositions. For finding a minimum decomposition, we propose both a heuristic and an FPT algorithm. Experiments on RNA transcript datasets show that for instances with larger solution path sets, the addition of subpath constraints finds 13% more ground truth solutions when minimal decompositions are found exactly, and 30% more ground truth solutions when minimal decompositions are found heuristically.

BibTeX - Entry

@InProceedings{williams_et_al:LIPIcs.WABI.2021.16,
  author =	{Williams, Lucia and Tomescu, Alexandru I. and Mumey, Brendan},
  title =	{{Flow Decomposition with Subpath Constraints}},
  booktitle =	{21st International Workshop on Algorithms in Bioinformatics (WABI 2021)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-200-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{201},
  editor =	{Carbone, Alessandra and El-Kebir, Mohammed},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14369},
  URN =		{urn:nbn:de:0030-drops-143695},
  doi =		{10.4230/LIPIcs.WABI.2021.16},
  annote =	{Keywords: Flow decomposition, subpath constraints, RNA-Seq}
}

Keywords: Flow decomposition, subpath constraints, RNA-Seq
Collection: 21st International Workshop on Algorithms in Bioinformatics (WABI 2021)
Issue Date: 2021
Date of publication: 22.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI