Combinatorial algorithms for pattern discovery in RNA sequences

近年来，我们看到了已知RNA家族数量的快速增长。其中很大一部分的作用机制尚不清楚。它们的特征结合了结构信息和序列信息。在大多数情况下，它们很难单独从序列中识别出来。鉴定RNA基序的传统方法寻求在排列序列的集合中寻找具有最小自由能的保守结构。通常，由于在没有关于结构的事先信息的情况下很难建立可靠的校准，因此校准并不容易获得。因此，比较分析大多是手工的，迭代的，从最保守的序列开始。我们最近开发了两个原型软件系统，用于三个RNA序列的同时比对和结构预测（eXtended Dynalign），以及RNA二级结构/序列基序推断（Seed）。我们的研究表明，使用几个输入序列可以规避最近邻自由能模型的限制——随着输入序列数量的增加，所有输入序列同时折叠成一个坏的自由能最小值的可能性变得更小。我们表明，与使用一个或两个输入序列进行预测相比，使用三个输入序列大大提高了准确性。我们还证明了支持和排除约束是足够强大的，以允许我们的组合算法详尽地枚举所有保守基元的搜索空间。我们提出了对软件系统eXtended dynamalign和Seed的几个扩展。我们的主要研究目标是开发和比较用于排序RNA二级结构基序的新目标函数。我们在eXtended Dynalign上的工作表明，随着输入序列数量的增加，最近邻模型的准确性也会提高。因此，我们将探索基于此模型的方案。在这项工作的同时，我们还将开发目标函数，灵感来自于已经成功发现序列模式的模型。特别是，我们将基于最小描述长度编码原则开发目标函数。

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.