The Computer Science Colloquium

Saad Mneimneh
(Hunter College)

"RNA-RNA interaction: formulation, NP-completeness, and approximations"

RNA-RNA interaction is a very important mechanism in molecular biology. For instance, a small interfering RNA (known as siRNA) can be used to silence a given gene by targeting its messenger RNA: The siRNA binds to the RNA and destroys it. Although RNAs are single-stranded molecules, they usually fold. The problem of RNA folding has been studied extensively in the literature and many polynomial time algorithms for determining the optimal folding (e.g. with minimum energy or maximum number of bonds) of an RNA molecule have been developed; however, the simultaneous folding and binding of two RNAs has not been studied yet. Although siRNAs represent a special case of RNA-RNA interaction (siRNAs do not fold), other complex examples of RNA-RNA interaction exist. Therefore, the general problem (where folding and binding occur simultaneously) deserves attention. I will formulate this problem and show that optimally folding two interacting RNAs becomes NP-complete, and provide some constant approximation algorithms that are able to predict realistic structures.


Short bio: Saad Mneimneh is currently a visiting professor in the department of computer science at Hunter College of CUNY. He was an assistant professor of computer science at Southern Methodist University until he moved to New York in 2005. He receives his Ph.D. degree from the Massachusetts Institute of Technology in 2002. His research interests include algorithms for switching, routing, load balancing, and computational biology.

The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc. and Netlogic, Inc.