User Tools

Site Tools



This shows you the differences between two versions of the page.

Link to this comparison view

fundamental_limits_and_optimal_algorithms_for_rna_transcriptome_assembly [2016/09/01 19:15] (current)
Line 1: Line 1:
 +Title: "​Fundamental limits and Optimal algorithms for RNA Transcriptome Assembly."​
 +Abstract: High throughput sequencing of RNA transcripts has emerged in
 +the last few years as a powerful method that enables discovery of
 +novel transcripts and alternatively spliced isoforms of genes, along
 +with accurate estimates of gene expression. In this paper, we study
 +the fundamental limits of de novo transcriptome assembly using RNA
 +shotgun-sequencing,​ where short reads are obtained from the RNA
 +transscripts. We propose a new polynomial-time algorithm for
 +transcriptome assembly and derive sufficient conditions on the length
 +of reads under which the algorithm will succeed. We then compare them
 +with necessary conditions that we derive for reconstruction by any
 +algorithm, and show that the proposed algorithm is near-optimal on a
 +real data set. Along the way, we study a problem of deducing
 +end-to-end network flows using link-level observations,​ and prove new
 +results for this model. In particular, we show that while the problem
 +is NP-hard in general, the instances we encounter from the biological
 +problem can be solved in near-linear time.
 +Bio: Sreeram Kannan is a postdoctoral researcher at the University of
 +California, Berkeley. He received his Ph.D. in Electrical Engineering
 +and M.S. in mathematics from the University of Illinois Urbana-
 +Champaign. He is a co-recipient of the Van Valkenburg research award
 +from UIUC,  Qualcomm Roberto Padovani Scholarship,​ the first prize in
 +Qualcomm Cognitive Radio Contest, the S.V.C. Aiya medal from the
 +Indian Institute of Science, and Intel India Student Research Contest
 +first prize. His research interests include applications of
 +information theory and approximation algorithms to wireless networks
 +and, more recently, to computational biology. Website:
fundamental_limits_and_optimal_algorithms_for_rna_transcriptome_assembly.txt ยท Last modified: 2016/09/01 19:15 (external edit)