Effiziente Berechnung akkurater multipler struktureller RNA-Alignments mittels mathematischer Optimierung

在过去的几年里，已知的产生非编码功能RNA的基因数量显著增加，据推测，还有更多的这些ncRNA基因仍未被发现。然而，许多RNA功能类显示出很少的序列保守性，而是一种保守的二级结构。因此，检测新的功能RNA的一个有希望的途径是寻找一组相关序列所共有的共同结构特征。通过这个项目，我们打算推进我们最近开发的算法理论，在合理消耗计算资源的情况下计算潜在的长RNA分子的可靠的多重结构比对。我们使用拉格朗日松弛等数学规划的方法，将问题作为一个整数线性规划来求解，这是图论重新表述的结果。对于两两结构对齐的情况，我们的结果表明我们当前的软件原型在速度和对齐质量方面都是最好的程序之一。基于这些有希望的初步成功，我们计划开发一个对已知或未知结构的RNA进行不同程度抽象的多结构比对工具，针对microRNAs和ITS2序列的特殊版本(包括聚类)，基于我们的拉格朗日方法的RNA基因搜索器，以及针对常规配对情况的基于线性规划的结构比对方法。由此产生的软件将免费提供。

During the last years, the number of genes known for producing non-coding functional RNA has increased significantly, and it is assumed that many more of these ncRNA genes are still undiscovered. Yet, many functional classes of RNA show little sequence conservation, but rather a conserved secondary structure. A promising avenue to detecting new functional RNAs is thus to look for common structural features shared by a set of related sequences. With this project we intend to advance our recently developed algorithmic theory to compute reliable multiple structural alignments of potentially long RNA molecules under a reasonable consumption of computational resources. We employ methods from mathematical programming such as Lagrangian relaxation and solve the problem as an integer linear program resulting from a graph-theoretical reformulation. Our results for the case of pairwise structural alignment show that our current software prototype is among the top programs in terms of speed and alignment quality. Based on these promising preliminary successes we plan to develop a multiple structural alignment tool with different levels of abstraction for RNAs of known or unknown structure with or without pseudoknots, special versions for microRNAs and ITS2 sequences (including clustering), an RNA gene finder based on our Lagrangian approach, and a linear-programming based structural alignment method for the regular pairwise case. The resulting software will be freely available.