Isoform reconstruction using short RNA-Seq reads by maximum likelihood is NP-hard

NP-hardIsoform reconstruction is a key step in RNA-Seq analysis. Tools such as CEM, iReckon, NSMAP, and MonteBello use maximum likelihood for isoform reconstruction. The maximum likelihood approach has been observed to be computationally expensive. Here, researchers from Tsinghua University, China show that isoform reconstruction using short RNA-Seq reads by maximum likelihood is NP-hard.

  • Li T, Jiang R, Zhang X. (203) Isoform reconstruction using short RNA-Seq reads by maximum likelihood is NP-hard. arXiv:1305.0916 [q-bio.QM]. [article]