CSAIL Event Calendar: Previous Series

Pairwise RNA secondary structures alignment

Speaker: Claire Herrbach , Universite Paris-Sud (France)
Date: January 23 2008
Time: 12:00PM to 1:00PM
Location: 32-G575
Host: Bonnie Berger & Peter Clote, MIT - BC

Contact: Patrice Macaluso, 617-253-3037, macaluso@csail.mit.edu
Relevant URL: http://www.lri.fr/bio/Herrbach/index.php?lg=fr

We studied the problem of pairwise alignment of RNA secondary structures without pseudoknots. Our method is dynamic programming-based, and uses a set of biologically-relevant operations on non-paired bases or base-pairs. We describe a polynomial-time and space algorithm, which has a worst-case complexity on the order of n4 and an average complexity on the order of n2. This algorithm makes a global comparison of two structures. We also give two variants to perform local comparison (pairwise comparison of substructures) and a small-in-large comparison (alignment of a small structure or a motif against a substructure of another structure).
Pairwise RNA alignment has natural applications in the prediction of RNA secondary structures and the classification of RNAs into functional families.

See other events that are part of Bioinformatics Seminar Series 2008

See other events happening in January 2008