Institute of Computing Science, Poznan University of Technology, 60-965 Poznan, Poland.
Department of Structural Bioinformatics, Institute of Bioorganic Chemistry, Polish Academy of Sciences, 61-704 Poznan, Poland.
Bioinformatics. 2023 May 4;39(5). doi: 10.1093/bioinformatics/btad315.
Tertiary structure alignment is one of the main challenges in the computer-aided comparative study of molecular structures. Its aim is to optimally overlay the 3D shapes of two or more molecules in space to find the correspondence between their nucleotides. Alignment is the starting point for most algorithms that assess structural similarity or find common substructures. Thus, it has applications in solving a variety of bioinformatics problems, e.g. in the search for structural patterns, structure clustering, identifying structural redundancy, and evaluating the prediction accuracy of 3D models. To date, several tools have been developed to align 3D structures of RNA. However, most of them are not applicable to arbitrarily large structures and do not allow users to parameterize the optimization algorithm.
We present two customizable heuristics for flexible alignment of 3D RNA structures, geometric search (GEOS), and genetic algorithm (GENS). They work in sequence-dependent/independent mode and find the suboptimal alignment of expected quality (below a predefined RMSD threshold). We compare their performance with those of state-of-the-art methods for aligning RNA structures. We show the results of quantitative and qualitative tests run for all of these algorithms on benchmark sets of RNA structures.
Source codes for both heuristics are hosted at https://github.com/RNApolis/rnahugs.
三级结构比对是计算机辅助分子结构比较研究的主要挑战之一。其目的是在空间中最佳地叠加两个或多个分子的 3D 形状，以找到它们的核苷酸之间的对应关系。比对是评估结构相似性或查找公共子结构的大多数算法的起点。因此，它在解决各种生物信息学问题方面具有应用，例如在搜索结构模式、结构聚类、识别结构冗余和评估 3D 模型的预测准确性方面。迄今为止，已经开发了几种工具来对齐 RNA 的 3D 结构。然而，它们中的大多数不适用于任意大的结构，并且不允许用户对优化算法进行参数化。
我们提出了两种可定制的启发式方法，用于灵活对齐 3D RNA 结构，即几何搜索（GEOS）和遗传算法（GENS）。它们以序列相关/独立模式工作，并找到预期质量（低于预定义 RMSD 阈值）的次优对齐。我们将它们的性能与用于对齐 RNA 结构的最先进方法进行了比较。我们展示了针对所有这些算法在 RNA 结构基准集上运行的定量和定性测试的结果。
两种启发式方法的源代码托管在 https://github.com/RNApolis/rnahugs 上。
