本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
離散物件的排列可以在非常一般的設定中建構為超級對象，透過投影從中恢復組成物件。在這裡，我們關注接觸圖，即具有有序頂點集的無向圖。這些作為 RNA 和蛋白質結構的自然離散化。在一般情況下，頂點有序圖的對齊問題是 NP 完全的。然而，在 RNA 二級結構的特殊情況下，即無交叉匹配，比對具有遞歸結構。然後可以透過桑科夫演算法的變體在多項式時間內解決對齊問題。此外，RNA二級結構的樹或森林排列可以理解為有序邊緣集的排列。