Median and small parsimony problems on RNA trees

Area of Science:

• Computational Biology
• Bioinformatics
• Molecular Evolution

Background:

• Noncoding RNAs (ncRNAs) perform functions through specific molecular structures.
• RNA secondary structures are conserved within functional families, while tertiary structures can differ within RNA clans.
• Understanding RNA structural evolution is key to deciphering functional adaptations and the Ancient RNA World Hypothesis.

Purpose of the Study:

• To introduce and analyze tree distance metrics for inferring the evolution of noncoding RNA structures.
• To address the median and small parsimony problems for ncRNA families using novel and existing tree distances.
• To develop efficient algorithms for reconstructing RNA evolutionary histories.

Main Methods:

• Representation of ncRNA secondary structures as leaf-labeled trees.
• Utilizing the Robinson-Foulds (RF) tree distance and introducing the Internal-Leafset (IL) distance.
• Considering a generalized tree edit distance for non-perfectly aligned base pairs.
• Analyzing the theoretical complexity and developing polynomial-time maximum parsimony algorithms.

Main Results:

• The IL distance better captures differences in RNA structural elements compared to the RF distance.
• Theoretical complexity of median and small parsimony problems was studied under different distance metrics.
• Polynomial-time maximum parsimony algorithms were developed and applied to ncRNA families.
• Practical utility demonstrated through application to RFAM database ncRNA families.

Conclusions:

• Novel tree distance metrics provide valuable tools for studying ncRNA structural evolution.
• Efficient algorithms facilitate the reconstruction of evolutionary histories for RNA families and clans.
• The study enhances our understanding of RNA functional adaptation and evolutionary processes.