Events Calendar

Fundamental Limits and Optimal Algorithms for RNA Transcriptome Assembly

Speaker: Sreeram Kannan, University of California, Berkeley

Talk 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.

Biography: 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.

Host: Giuseppe Caire, caire@usc.edu EEB 540, x04683

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos