.png){kind=icon}
返回
Flow Decomposition With Subpath Constraints
.png){kind=icon}
OA
AI
DOI：10.1109/TCBB.2022.3147697.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 FPTalgorithm. 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.
Keyword:
Flow decomposition
subpath constraints
RNA-Seq
期刊
I
IF:
3.4
论文数:
3.3K
被引数:
6.4K
机构
引用论文
分享收藏分享收藏TransBorrow: genome-guided transcriptome assembly by borrowing assemblies from different assemblers.png)
GENOME RESEARCH
OAAI
GENOME RESEARCHIF5.5
OAAI分享收藏Accurate assembly of transcripts through phase-preserving graph decompositionNATURE BIOTECHNOLOGYOAAI
NATURE BIOTECHNOLOGYIF41.7
OAAI分享收藏
查看更多内容