RNA Secondary Structure Prediction - Notion of Algorithm

Introduction

• First lecture of a series covered online
• Topic: Algorithm for RNA secondary structure prediction
• Review and start from the beginning

RNA Secondary Structures

• Different types of RNA secondary structures
• Various methods for RNA secondary structure prediction

Notion of Algorithm (Base Pair Maximization)

• Method for predicting tRNA secondary structure developed by Ruthgers and Nussinov.
• Objective: Maximize RNA base pairs
• More base pairs -> Lower minimum free energy -> More stable structure

Dynamic Programming Algorithms

• Similar to Smith-Waterman (local alignment) and Needleman-Wunsch (global alignment)
• Difference lies in the specified methodology
• Consider a matrix with sequence on both x-axis and y-axis
• Use scoring schemes to fill matrix

Complexity and Pseudoknots

• RNA secondary structures can be complex and include pseudoknots
• Current algorithm does not predict pseudoknots

Approach

• Finding intra-molecular base-pairing
• Compare RNA sequence with itself
• Scoring: Complementary bases get 1, non-complementary 0
• GC and AU base pair (Watson-Crick), also consider GU wobble base pair
• Example of matrix creation with RNA strand

Matrix Initialization and Filling

• Initialize matrix with zeros on main diagonal and lower half
• Filling the matrix by examining base pairs:
  • If complementary: Use the score from lower left diagonal + 1
  • If non-complementary: Use the highest score from neighboring cells
• Fill matrix step-by-step example:
  • Comparison of various base pairs e.g., A-U (1), G-C (1), etc.

Traceback Step

• Start from top left with highest score and trace back to lowest score
• Mark the RNA secondary structure
• Example of traceback resulting in structure prediction

Important Points

1. RNA structure prediction remains challenging.
2. Algorithm does not predict pseudoknots.

Summary of Methods

• Dot plot (visual method)
• Minimum Free Energy Method (realistic, stable structures)
• Covariance Analysis (used in evolutionary studies)
• Base Pair Maximization (considers all possibilities, multiple structures)

Assignment

• Fill the matrix yourself and predict RNA secondary structure
• Discuss solution in the next interactive session

Conclusion

• Study another topic next time
• Lecture slides will be shared
• Allah Hafiz