Parallel algorithms for finding a near-maximum independent set of a circle graph

Area of Science:

• Computational Biology
• Graph Theory
• Bioinformatics

Background:

• Predicting ribonucleic acid (RNA) secondary structures is crucial for understanding RNA function.
• Identifying maximum independent sets in graphs is a computationally challenging problem.
• Existing methods for RNA structure prediction have limitations in accuracy and efficiency.

Purpose of the Study:

• To develop a novel parallel algorithm for finding near-maximum independent sets in circle graphs.
• To adapt this algorithm for predicting RNA secondary structures.
• To identify more stable RNA structures compared to existing predictions.

Main Methods:

• A parallel algorithm was designed to find near-maximum independent sets in circle graphs.
• The algorithm was modified using an n neural network array for RNA secondary structure prediction.
• The system was tested on a 359-base sequence from the potato spindle tuber viroid.

Main Results:

• The algorithm efficiently generates near-maximum independent sets.
• The neural network system accurately predicts RNA secondary structures within hundreds of iteration steps.
• Several more stable RNA structures were discovered for the potato spindle tuber viroid sequence.

Conclusions:

• The developed parallel algorithm and its neural network adaptation offer an efficient approach for RNA secondary structure prediction.
• This method can identify novel and more stable RNA structures.
• The findings have implications for understanding RNA function and disease mechanisms.