EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Median and small parsimony problems on RNA trees

Bertrand Marchand, Yoann Anselmetti, Manuel Lafond, Aïda Ouangraoua iD

Bioinformatics · 2024

DOI: 10.1093/bioinformatics/btae229 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bioinformatics, 2024. Verfasst von Bertrand Marchand und 3 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, University of Sherbrooke, Sherbrooke, QC J1K 2R1, Canada. Hauptthemen laut MEDLINE: RNA, Untranslated, Nucleic Acid Conformation. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 36 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Canada Research Chair, Natural Sciences and Engineering Research Council of Canada, NSERC.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivation Noncoding RNAs (ncRNAs) express their functions by adopting molecular structures. Specifically, RNA secondary structures serve as a relatively stable intermediate step before tertiary structures, offering a reliable signature of molecular function. Consequently, within an RNA functional family, secondary structures are generally more evolutionarily conserved than sequences. Conversely, homologous RNA families grouped within an RNA clan share ancestors but typically exhibit structural differences. Inferring the evolution of RNA structures within RNA families and clans is crucial for gaining insights into functional adaptations over time and providing clues about the Ancient RNA World Hypothesis. Results We introduce the median problem and the small parsimony problem for ncRNA families, where secondary structures are represented as leaf-labeled trees. We utilize the Robinson-Foulds (RF) tree distance, which corresponds to a specific edit distance between RNA trees, and a new metric called the Internal-Leafset (IL) distance. While the RF tree distance compares sets of leaves descending from internal nodes of two RNA trees, the IL distance compares the collection of leaf-children of internal nodes. The latter is better at capturing differences in structural elements of RNAs than the RF distance, which is more focused on base pairs. We also consider a more general tree edit distance that allows the mapping of base pairs that are not perfectly aligned. We study the theoretical complexity of the median problem and the small parsimony problem under the three distance metrics and various biologically relevant constraints, and we present polynomial-time maximum parsimony algorithms for solving some versions of the problems. Our algorithms are applied to ncRNA families from the RFAM database, illustrating their practical utility. Availability and implementation https://github.com/bmarchand/rna\_small\_parsimony.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

RNA, UntranslatedNucleic Acid ConformationAlgorithmsEvolution, MolecularSequence Analysis, RNAComputational Biology

Substanzen

RNA, Untranslated

Autor:innen und Institutionen

  • Department of Computer Science, University of Sherbrooke, Sherbrooke, QC J1K 2R1, Canada.

ORCID-Profile: Aïda Ouangraoua

Förderung

  • Canada Research Chair
  • Natural Sciences and Engineering Research Council of Canada
  • NSERC
  • BME Student International Experience
  • Institut Polytechnique de Paris
  • Agence Nationale de la Recherche

Zitieren

APA

Marchand, B., Anselmetti, Y., Lafond, M., & Ouangraoua, A. (2024). Median and small parsimony problems on RNA trees. Bioinformatics. https://doi.org/10.1093/bioinformatics/btae229

Vancouver

Marchand B, Anselmetti Y, Lafond M, Ouangraoua A. Median and small parsimony problems on RNA trees. Bioinformatics. 2024. doi:10.1093/bioinformatics/btae229

BibTeX
@article{Marchand2024,
  author = {Marchand, Bertrand and Anselmetti, Yoann and Lafond, Manuel and Ouangraoua, Aïda},
  title = {Median and small parsimony problems on RNA trees},
  journal = {Bioinformatics},
  year = {2024},
  doi = {10.1093/bioinformatics/btae229}
}
Kostenlos starten →