Visit ShanghaiTech University | 中文 | How to find us
HOME > News and Events > Events
RNA-Seq Assembly: Fundamental Limits, Algorithms and Software
Date: 2014/10/13             Browse: 868

Speaker:Tse, David 

Time:Oct 13, 15:15-16:30

Location:Room 220,  Building 8

Extraordinary advances in sequencing technology  in the past decade have revolutionized biology and medicine. Many high-throughput sequencing based assays have been designed to make various biological measurements of interest. One of the most important assays is RNA sequencing (RNA-Seq). A key computational problem in RNA-Seq  is that of assembly: how to reconstruct from the many millions of short reads the underlying RNA transcripts? Traditionally, assembler design is viewed mainly as a software engineering project, where time and memory requirements are primary concerns while the assembly algorithms themselves  are designed based on heuristic considerations with no optimality guarantee. In this talk, we outline an alternative approach to assembly design based on information theoretic principles.  Starting with the question of when there is enough information in the reads to reconstruct, we design a near-optimal assembly algorithm that can reconstruct with  minimal amount of read information. We implemented the algorithm in a software ShannonRNA and compare its performance on both simulated and real data with state-of-the-art  software in the field.
This is joint work with Sreeram Kannan and Lior Pachter.


David Tse received the B.A.Sc. degree in systems design engineering from University of Waterloo in 1989, and the M.S. and Ph.D. degrees in electrical engineering from Massachusetts Institute of Technology in 1991 and 1994 respectively. From 1994 to 1995, he was a postdoctoral member of technical staff at A.T. & T. Bell Laboratories. From 1995 to 2014, he was on the faculty of the Department of Electrical Engineering and Computer Sciences in the University of California at Berkeley. He is currently a professor at Stanford University.

He received a 1967 NSERC graduate fellowship from the government of Canada in 1989, a NSF CAREER award in 1998, the Best Paper Awards at the Infocom conference in 1998 and 2001, the Erlang Prize in 2000 from the INFORMS Applied Probability Society, the IEEE Communications Society and Information Theory Society Joint Paper Awards in 2000 and 2013, the Information Theory Society Paper Awardin 2003, a Gilbreth Lectureship from the National Academy of Engineering in 2012, the Signal Processing Society Best Paper Award in 2012, the EURASIP Best Paper Award in 2012 and the IEEE Communications Society Stephen O. Rice Prize in 2013. For his contributions to education, he received the Outstanding Teaching Award from the Department of Electrical Engineering and Computer Sciences at U.C. Berkeley in 2008 and the Frederick Emmons Terman Award from the American Society for Engineering Education in 2009. He is a coauthor, with Pramod Viswanath, of the text Fundamentals of Wireless Communication, which has been used in over 60 institutions around the world. He is the inventor of the proportional-fair scheduling algorithm used in all third and fourth-generation cellular systems.

He was an Associate Editor of the IEEE Transactions on Information Theory from 2001 to 2003, the Technical Program co-chair in 2004 and the General co-chair of the International Symposium on Information Theory in 2015. He served on the Board of Governors of the IEEE Information Theory Society from 2003 to 2008 and from 2010 to 2013. He was the plenary speaker for many international conferences and workshops, including the IEEE International Symposium on Information Theory in 2009, the ACM International Conference on Mobile Computing and Networking (MobiCom) in 2007 and the IEEE International Conference on Acoustics, Speech and Signal Processing in 2006.

His research interests are in information theory and its applications in various fields, including wireless communication, energy and computational biology.

                                                                                                                  SIST-Seminar 14030