Combinatorial algorithms for pattern discovery in RNA sequences

近年来，已知的RNA家族数量迅速增加。 其中很大一部分的作用机制尚不清楚。它们的特征结合了结构和序列信息。在大多数情况下，很难单独从序列中识别它们。 识别RNA基序的传统方法寻求在比对序列的集合中找到具有最小自由能的保守结构。 通常，由于在没有关于结构的先验信息的情况下难以建立可靠的对准，因此对准不容易获得。因此，比较分析主要是手工进行，迭代，从最保守的序列开始。我们最近开发了两个原型软件系统，用于三个RNA序列的同时比对和结构预测（eXtended Dynalign），以及RNA二级结构/序列基序的推断（Seed）。 我们的研究表明，使用几个输入序列可以规避最近邻自由能模型的限制-随着输入序列数量的增加，它们同时折叠成一个坏的自由能最小值的可能性变得更小。 我们表明，使用三个输入序列大大提高了准确性相比，从一个或两个输入序列的预测。 我们还表明，支持和排除约束是足够强大的，允许我们的组合算法，以穷举所有保守的图案的搜索空间。我们提出了几个扩展的软件系统eXtended Dynalign和种子。我们的主要研究目标是开发和比较新的目标函数排名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.