A novel min-cost flow method for estimating transcript expression with RNA-Seq.
A novel min-cost flow method for estimating transcript expression with RNA-Seq.
复制标题
DOI：
10.1186/1471-2105-14-s5-s15
复制
发表时间：
2013
影响因子：
3
通讯作者：
Mäkinen V
中科院分区：
文献类型：
--
作者：
Tomescu AI;Kuosmanen A;Rizzi R;Mäkinen V
通过转录和选择性剪接，基因可以转录成不同的RNA序列（同种型），这取决于个体、细胞所在的组织或对某些刺激的反应。最近的RNA-Seq技术允许用于基于短读段的异构体鉴定和定量的新的高通量方法，并且已经针对这个重要问题提出了各种方法。在本文中，我们提出了一种新的完全不同的方法的基础上最小成本的网络流。这有两个方面的优势：一方面，它将问题转化为网络流领域中的一个既定问题，可以在多项式时间内使用不同的现有求解器解决;另一方面，它足够通用，可以包含许多以前的最小平方和模型下的建议。我们的方法如下：为了找到在给定的适应度模型下最好地解释由RNA-Seq实验产生的剪接图的转录本，我们在等效成本模型下找到偏移流网络中的最小成本流。在适应度模型的非常弱的假设下，可以在多项式时间内计算出最优流。用网络流理论中的任何一种解析法和近似法，都可以把流简单地分解成几个路径副本。在本实现中，我们选择了简单的策略，反复删除最重的路径。我们提出了一个新的非常通用的方法，基于网络流的多组装问题所产生的异构体识别和定量与RNA-Seq。预测精度的实验结果表明，我们的方法是非常有竞争力的流行的工具，如Cufflinks和IsoLasso。我们的工具名为TAPK（GRAPH中的转录），可在http://www.cs.helsinki.fi/gsa/traph/上获得。
Through transcription and alternative splicing, a gene can be transcribed into different RNA sequences (isoforms), depending on the individual, on the tissue the cell is in, or in response to some stimuli. Recent RNA-Seq technology allows for new high-throughput ways for isoform identification and quantification based on short reads, and various methods have been put forward for this non-trivial problem. In this paper we propose a novel radically different method based on minimum-cost network flows. This has a two-fold advantage: on the one hand, it translates the problem as an established one in the field of network flows, which can be solved in polynomial time, with different existing solvers; on the other hand, it is general enough to encompass many of the previous proposals under the least sum of squares model. Our method works as follows: in order to find the transcripts which best explain, under a given fitness model, a splicing graph resulting from an RNA-Seq experiment, we find a min-cost flow in an offset flow network, under an equivalent cost model. Under very weak assumptions on the fitness model, the optimal flow can be computed in polynomial time. Parsimoniously splitting the flow back into few path transcripts can be done with any of the heuristics and approximations available from the theory of network flows. In the present implementation, we choose the simple strategy of repeatedly removing the heaviest path. We proposed a new very general method based on network flows for a multiassembly problem arising from isoform identification and quantification with RNA-Seq. Experimental results on prediction accuracy show that our method is very competitive with popular tools such as Cufflinks and IsoLasso. Our tool, called Traph (Transcrips in gRAPHs), is available at: http://www.cs.helsinki.fi/gsa/traph/.