基于结构序列表示与SERNA距离的高效假结RNA二级结构比对方法及开源工具SERNAlign

《BMC Bioinformatics》：Alignment of RNA secondary structures with arbitrary pseudoknots using structural sequences

　　

摘要

背景

RNA二级结构的比较对于RNA分类、基序分析和进化研究至关重要。虽然存在用于无假结结构的高效方法，但具有任意假结的RNA二级结构的比较在计算上仍然具有挑战性。本研究旨在引入一种新颖的基于序列的表示方法以及一种相关的比对距离，以高效比较具有任意假结的RNA二级结构。

结果

我们提出了一种基于整数序列的具有任意假结的RNA二级结构的新颖表示方法，称为结构序列。在该表示方法上，我们定义了SERNA距离，这是经典编辑距离的扩展，并加入了结构正确性约束，并证明它是一个度量。我们提出了SERNAlign，一个使用动态规划计算SERNA距离的开源工具，其时间复杂度为二次。为了评估所提出的距离，我们在基于聚类的评估框架中进行了两项互补的实验：分类实验验证的假结基序，这直接针对SERNA的设计目标，以及核糖体RNA的系统发育聚类作为对现有结构距离的鲁棒性检查。在两项任务中，SERNA相对于最先进的比较方法展示了具有竞争力的聚类性能，同时在复杂基序设置中提供了更好的判别能力，并且与基于结构的方法相比，计算成本显著降低。