Combinatorial algorithms for pattern discovery in RNA sequences

点击翻译按钮获取中文摘要

In recent years, we have seen a rapid growth of the number of known RNA families.  For a significant fraction of them, the mechanisms of action remain unclear. Their signature combines structure and sequence information. In most cases, they are difficult to identify from sequence alone.  Traditional approaches to identify RNA motifs seek to find conserved structures with minimum free energy in an ensemble of aligned sequences.  Often, an alignment is not readily available because of the difficulty to build a reliable alignment without prior information about the structure. Accordingly, comparative analyses are mostly done by hand, iteratively, starting with the most conserved sequences. We recently developed two prototype software systems for the simultaneous alignment and structure prediction of three RNA sequences (eXtended Dynalign), as well as for the inference of RNA secondary structure/sequence motifs (Seed).  Our research suggests that using several input sequences allows to circumvent limitations of the nearest neighbour free energy model --- as the number of input sequences increases it becomes less likely that all of them simultaneously fold into a bad free-energy minimum.  We showed that the use of three input sequences greatly improves the accuracy compared to predictions made from one or two input sequences.  We have also shown that support and exclusion constraints are sufficiently powerful to allow for our combinatorial algorithm to enumerate exhaustively the search space of all conserved motifs. We propose several extensions to the software systems eXtended Dynalign and Seed. Our primary research objective is to develop and compare new objective functions for ranking RNA secondary structure motifs.  Our work on eXtended Dynalign suggests that the accuracy of the nearest neighbour model improves as the number of input sequences increases.  Accordingly, we will explore schemes that are based on this model. In parallel to this work, we will also develop objective functions inspired from models that have been successful for the discovery of sequence patterns. In particular, we will develop objective functions based on the minimum description length encoding principle.