Combinatorial algorithms for pattern discovery in RNA sequences

RNA 序列模式发现的组合算法

• 批准号: 250909-2006
• 负责人: Turcotte, Marcel
• 金额: $ 1.02万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=394830
• 关键词: Combinatorial; algorithms; pattern; discovery; RNA

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.

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