Rxivist logo

Efficient Heuristic for Decomposing a Flow with Minimum Number of Paths

By Mingfu Shao, Carl Kingsford

Posted 16 Nov 2016
bioRxiv DOI: 10.1101/087759

Motivated by transcript assembly and multiple genome assembly problems, in this paper, we study the following minimum path flow decomposition problem: given a directed acyclic graph G=(V, E) with source s and sink t and a flow f, compute a set of s-t paths P and assign weight w(p) for p ∈ P such that f(e) = Σp∈P:e∈pw(p), ∀e ∈ E, and |P| is minimized. We propose an efficient pseudo-polynomial-time heuristic for this problem based on novel insights. Our heuristic gives a framework that consists of several components, providing a roadmap for continuing development of better heuristics. Through experimental studies on both simulated and transcript assembly instances, we show that our algorithm significantly improves the previous state-of-the-art algorithm. Implementation of our algorithm is available at https://github.com/Kingsford-Group/catfish.

Download data

  • Downloaded 725 times
  • Download rankings, all-time:
    • Site-wide: 19,655 out of 92,758
    • In bioinformatics: 2,903 out of 8,685
  • Year to date:
    • Site-wide: 65,102 out of 92,758
  • Since beginning of last month:
    • Site-wide: 29,437 out of 92,758

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)