Effiziente Berechnung akkurater multipler struktureller RNA-Alignments mittels mathematischer Optimierung

• Applicant: Professor Dr. Gunnar Klau
• Subject Area: Bioinformatics and Theoretical Biology
• Term: from 2007 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 34979413

During the last years, the number of genes known for producing non-coding functional RNA has increased significantly, and it is assumed that many more of these ncRNA genes are still undiscovered. Yet, many functional classes of RNA show little sequence conservation, but rather a conserved secondary structure. A promising avenue to detecting new functional RNAs is thus to look for common structural features shared by a set of related sequences. With this project we intend to advance our recently developed algorithmic theory to compute reliable multiple structural alignments of potentially long RNA molecules under a reasonable consumption of computational resources. We employ methods from mathematical programming such as Lagrangian relaxation and solve the problem as an integer linear program resulting from a graph-theoretical reformulation. Our results for the case of pairwise structural alignment show that our current software prototype is among the top programs in terms of speed and alignment quality. Based on these promising preliminary successes we plan to develop a multiple structural alignment tool with different levels of abstraction for RNAs of known or unknown structure with or without pseudoknots, special versions for microRNAs and ITS2 sequences (including clustering), an RNA gene finder based on our Lagrangian approach, and a linear-programming based structural alignment method for the regular pairwise case. The resulting software will be freely available.

• DFG Programme: Research Grants