On the approximation of optimal structures for RNA-RNA interaction

Area of Science:

• Computational Biology
• Bioinformatics
• Molecular Biology

Background:

• RNA-RNA interactions are fundamental to numerous biological processes.
• Predictive algorithms for RNA complex structures are of significant interest.
• Existing algorithms often rely on dynamic programming but may not yield optimal structures due to the NP-complete nature of the problem.

Purpose of the Study:

• To characterize the suboptimality of RNA-RNA interaction structure prediction algorithms.
• To develop and analyze approximation algorithms for RNA-RNA interaction structure prediction.

Main Methods:

• Demonstration of constant factor approximation algorithms based on dynamic programming.
• Development of specific 1/2 and 2/3 factor approximation algorithms.
• Definition of an 'entangler' to analyze algorithm performance.

Main Results:

• Established the existence of constant factor approximation algorithms for RNA-RNA interaction structure prediction.
• Presented 1/2 and 2/3 factor approximation algorithms.
• Proved that 2/3 is a theoretical upper bound for approximation factor in entangler-free solutions.

Conclusions:

• Dynamic programming algorithms for RNA-RNA interaction structure prediction are suboptimal.
• Approximation algorithms offer a viable approach to address this suboptimality.
• The concept of an entangler provides theoretical bounds for algorithm performance.