Comparing RNA Structures: Towards an Intermediate Model Between the Edit and the Lapcs Problems

摘要

In the recent past, RNA structure comparison has appeared as an important field of bioinformatics. In this paper, we introduce a new and general intermediate model for comparing RNA structures: the Maximum Arc-Preserving Common Subsequence problem (or Mapcs). This new model lies between two well-known problems - namely the Longest Arc-Preserving Common Subsequence (Lapcs) and the Edit distance. After showing the relationship between Mapcs, Lapcs, Edit, and also the Maximum Linear Graph problem, we will investigate the computational complexity landscape of Mapcs, depending on the RNA structure complexity.