Flexible approach for novel transcript reconstruction from RNA-seq data using maximum likelihood integer programming

In this paper, we propose a novel, intuitive and flexible approach for transcriptome reconstruction from single RNA-Seq reads, called "Maximum Likelihood Integer Programming" (MLIP) method. MLIP creates a splice graph based on aligned RNA-Seq reads and enumerates all maximal paths corresponding to putative transcripts. The problem of selecting true transcripts is formulated as an integer program which minimizes the number of selected candidate transcripts. Our method purpose is to predict the minimum number of transcripts explaining the set of input reads with the highest quantification accuracy. This is achieved by coupling a integer programming formulation with an expectation maximization model for transcript expression estimation. MLIP has the advantage of offering different levels of stringency that would gear the results towards higher precision or higher sensitivity, according to the user preference. We test MLIP method on simulated and real data, and we show that MLIP outperforms both Cufflinks and IsoLasso.