Designing Secondary Structure Profiles for Fast ncRNA Identification

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering
Department of Chemical Engineering (CENG)
Human Language Technology Center

		JOINT SEMINAR
-----------------------------------------------------------------
Speaker:	Yanni SUN
		Washington University

Title:		"Designing Secondary Structure Profiles for Fast
		 ncRNA Identification"

Date:		Friday, 21 December 2007

Time:		4:00pm - 5:00pm

Venue:		Lecture Theater F
		(Leung Yat Sing Lecture Theater, near lift 25/26)
		HKUST

Abstract:

Recent biological studies revealed more and more functions of non-coding
RNAs (ncRNAs) in many biological processes such as tRNAs, riboswitches,
and RNA interference. Annotating ncRNAs in gnome databases for biological
function analysis is thus becoming increasingly important. The most widely
used tool for describing ncRNA families is based on the stochastic
context-free grammar (SCFG). However, the use of SCFG incurs a high
computational cost, which creates a major challenge for searching ncRNAs
in large-scale gnome databases.

A promising approach to speed up SCFG based ncRNA search is to use filters
to exclude a large portion of the database that is unlikely to contain the
ncRNA of interest. In this talk, I will present a systematic framework to
utilize a new filter called the secondary structure profile (SSP) that can
be efficiently scanned against large databases. We use dynamic programming
to estimate an SSP's sensitivity and false positive rate, which leads to
an efficient and fully automated filter design algorithm. Experiments
demonstrate that our SSP-based filters can achieve high sensitivity,
specificity, and an average of 200x speedup for a majority of known ncRNA
families.


******************
Biography:

Yanni SUN is a Ph.D. candidate in the Department of Computer Science and
Engineering at Washington University in St. Louis, USA. She received her
BS and MS degrees in Computer Science from Xi'an Jiao Tong University,
China, in 1998 and 2001 respectively. Her research interests include
Bioinformatics/computational biology, pattern design, pattern search,
similarity search in large-scale database. Her work has been published in
prestigious academic journals including Journal of Computational Biology
and BMC Bioinformatics, as well as in top Bioinformatics conferences
including RECOMB and ECCB.