Rxivist logo

Rxivist combines preprints from bioRxiv with data from Twitter to help you find the papers being discussed in your field. Currently indexing 70,170 bioRxiv papers from 306,408 authors.

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 659 times
  • Download rankings, all-time:
    • Site-wide: 15,397 out of 70,177
    • In bioinformatics: 2,406 out of 6,878
  • Year to date:
    • Site-wide: 42,150 out of 70,177
  • Since beginning of last month:
    • Site-wide: 24,679 out of 70,177

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


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