CSAIL Event Calendar: Previous Series
Pairwise RNA secondary structures alignment
Speaker: Claire Herrbach , Universite Paris-Sud (France)
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).