文章基本信息

标题：Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding
本地全文：下载
作者：Niko Kiirala ; Leena Salmela ; Alexandru I. Tomescu 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：128
页码：1-16
DOI：10.4230/LIPIcs.CPM.2019.8
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Many bioinformatics problems admit a large number of solutions, with no way of distinguishing the correct one among them. One approach of coping with this issue is to look at the partial solutions common to all solutions. Such partial solutions have been called safe, and an algorithm outputting all safe solutions has been called safe and complete. In this paper we develop a general technique that automatically provides a safe and complete algorithm to problems solvable by dynamic programming. We illustrate it by applying it to the bioinformatics problem of RNA folding, assuming the simplistic folding model maximizing the number of paired bases. Our safe and complete algorithm has time complexity O(n^3M(n)) and space complexity O(n^3) where n is the length of the RNA sequence and M(n) in Omega(n) is the time complexity of arithmetic operations on O(n)-bit integers. We also implement this algorithm and show that, despite an exponential number of optimal solutions, our algorithm is efficient in practice.
关键词：RNA secondary structure; RNA folding; Safe solution; Safe and complete algorithm; Counting problem