Combinatorial algorithms for pattern discovery in RNA sequences

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

• 批准号: 250909-2006
• 负责人: Turcotte, Marcel
• 金额: $ 1.02万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=362572
• 关键词: 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序列的同时比对和结构预测的原型软件系统(扩展的动态对齐)，以及对RNA二级结构/序列基序(SEED)的推断。我们的研究表明，使用几个输入序列允许绕过最近邻自由能模型的限制-随着输入序列数量的增加，所有这些序列同时折叠成糟糕的自由能最小值的可能性变得更小。我们表明，与由一个或两个输入序列做出的预测相比，使用三个输入序列极大地提高了精度。*我们还证明了支持和排除约束足够强大，使得我们的组合算法能够穷尽地列举所有保守基序的搜索空间。我们提出了对软件系统的几个扩展，扩展了动态对齐和种子。我们的主要研究目标是开发和比较新的目标函数来对RNA二级结构基序进行排序。我们在Extended DyAlign上的工作表明，最近邻模型的精度随着输入序列数量的增加而提高。因此，我们将探索基于该模型的方案。在这项工作的同时，我们还将开发目标函数，这些函数的灵感来自于成功发现序列模式的模型。特别是，我们将基于最小描述长度编码原则来开发目标函数。