A Flexible and Efficient System for the Detection of RNA Sequence/Structure Motifs

非编码rna （ncRNAs）参与细胞的许多调控过程。绝大多数的ncrna是通过全转录组分析（下一代测序（NGS））发现的，其中大多数没有注释。ncRNA的功能分析在很大程度上依赖于序列结构相似性。然而，由于计算复杂度高，寻找序列结构相似性的工具目前尚未用于注释新鉴定的ncRNA。目前的全基因组计算ncRNA分析通常消耗巨大的计算资源（10到数百个计算机年）。我们的目标是建立一个用于分析和注释ncrna的系统，该系统由一组用于检测序列结构相似性的有效算法和工具组成。我们将提供一个易于使用的基于web的界面，允许生物学家执行ncRNA注释任务，并使用个性化的基因组浏览器轨迹在其基因组背景下分析ncRNA。合并后的系统将允许执行两项主要任务：在其他NGS数据或ncRNA数据库中搜索与新检测到的ncRNA具有结构相似性的注释ncRNA或ncRNA转录本。我们将考虑结构小的ncrna和长链非编码rna (lncRNA)，其中全局保守的结构尚未被发现。2)。对一组新的非编码rna进行聚类，以确定其结构类，这是对新的ncRNA类进行功能标注的前提。特别是，这涉及到完整转录本的全局聚类。我们还将研究基于局部序列的局部聚类问题，以找到嵌入到较长的转录本中的调控基序（例如，顺式调控元件，如IRE（铁反应元件），IRES（内部核糖体进入位点）等）。这个问题目前很难用自动化工具来解决。我们的第一个主要目标是通过使用先进的算法技术直接提高序列结构比对方法的效率和质量。目前，最精确的算法方法对于常规扫描数百个（如果不是数千个）ncrna（通常在转录组数据中发现）还不够有效。为了使我们的工具在实践中适用，从而满足我们合作伙伴的需求，我们必须设计快速和敏感的过滤器，以显着减少昂贵的序列结构比较次数。以前的方法使用基于序列的过滤。显然，这种过滤只适用于序列相似性高的ncrna。然而，众所周知，保守的ncrna可能具有非常低的序列保守性。因此，我们的第二个主要目标是基于高效的图核方法开发快速的基于序列结构的过滤方法。

Non-coding RNAs (ncRNAs) are involved in many regulatory processes of a cell. An overwhelming number of ncRNAs is found by whole transcriptome analyses (next-generation-sequencing (NGS)), most of which are not annotated. The functional analysis of ncRNA relies heavily on sequence-structure similarities. Due to the high computational complexity, however, tools for finding sequence-structure similarities are currently not used for annotating newly identified ncRNA. Current computational genome-wide ncRNA analysis often consumes enormous computing resources (ten to hundreds of computer years). Our goal is to setup a system for analyzing and annotating ncRNAs that consists of a set of efficient algorithms and tools for detecting sequence-structure similarity. We will provide an easy-to-use web-based interface to allow biologists to perform ncRNA annotation tasks, and to analyze the ncRNA in its genomic context using personalized genome browser tracks. The combined system will allow two major tasks to be performed: 1.) To search for annotated ncRNAs or ncRNA transcripts in other NGS data or in ncRNA databases that have structural similarity for a newly detected ncRNAs. We will consider both structured small ncRNAs as well as long non-coding RNAs (lncRNA), where globally conserved structure has not been found yet. 2.) To cluster a set of new non-coding RNAs in order to determine structural classes, which is a prerequisite for functional annotation of new ncRNA classes. In particular, this involves a global clustering of complete transcripts. We will also work on the problem of local clustering, based on local alignments, to find regulatory motifs that are embedded into longer transcripts (e.g., cis-regulatory elements like the IRE (iron response element), IRES (internal ribosome entry site) etc.). This problem is currently hard to solve using automated tools. Our first major objective is to directly improve the efficiency and quality of our sequence-structure alignment approach by using advanced algorithmic techniques. Currently, the best exact algorithmic approaches are not efficient enough for routinely scanning for hundreds (if not thousands) of ncRNAs, typically found in transcriptome data. To make our tools applicable in practice, and thus to fullfill the needs of our cooperation partners, we have to design fast and sensitive filters in order to significantly reduce the number of expensive sequencestructure comparisons. Previous approaches used sequence-based filtering. Obviously, this filtering only works for ncRNAs with high sequence similarities. It is known, however, that conserved ncRNAs may have a very low sequence conservation. Therefore, our second major objective is to develop fast sequencestructure-based filtering methods based on our efficient graph-kernel approach.