Combinatorial models for RNA structures, with or without pseudoknots and application to structures comparison
type: Dataset
description: This thesis proposes a model of RNA secondary structures with or without pseudoknots. According to a combinatorial approach, we design different models of these structures which we study according to two aspects. In one hand, we define random generation models which allow us to define a measure allowing a better recognition of biological structures. On the other hand, greatings to appropriated encodings and bijections to languages represented by non-contextual grammars, we count the structures composing the space of exact secondary structure prediction algorithms with pseudoknots. The first part deals with random models of RNA structures without pseudoknots. We show that these structures are a relevant source of random noise when determining whether the structures comparison softwares attribute a better comparison score between structures from the same family than alignments between real and random structures. We then compare the sensitivity and spcificity of RNAdistance, a structures comparison software, depending on the use of the "raw" score or on the Z-value. We compute several Z-values according to different models of random structures. We show that the Z-value computed from a Markov model improves the detection of large RNA while the Z-value computed from a model based on weighted grammars improves the detection of small RNA. We then consider, in the other hand, pseudoknotted secondary structure prediction algorithms. First we complete the Condon it et al. classification by describing the structures by their consistancy graph and we also characterize the planar restriction of the class of Rivas and Eddy. Then, we investigate the tradeoff between the complexity of existing algorithms and the size of their prediction space. We count the structures by coding them with words of algebraic languages. Then, we deduce asymptotic formulas count. We also show a bijection between the class of Lyngso and Pedersen and planar maps and a bijection between the class of undiff…
issued: 2026-05-14T11:46:18.839509
language: fr
modified: 2026-05-14T11:46:18.839514
contact point: Organization
  fn: CCSD
keyword: algorithmes
keyword: algorithms
keyword: arn
keyword: complexite
keyword: complexity
keyword: infoeu-reposemanticsdoctoralthesis
keyword: infoinfo-bicomputer-science-csbioinformatics-q-bioqm
keyword: prediction
keyword: pseudoknots
keyword: pseudonoeuds
keyword: rna
keyword: sdvbibslife-sciences-q-bioquantitative-methods-q-bioqm
keyword: structure
keyword: theses
landing page: https://theses.hal.science/tel-00788467

Combinatorial models for RNA structures, with or without pseudoknots and application to structures comparison
type: Distribution
format: HTML
issued: 2026-05-14T11:46:18.845558
modified: 2026-05-14T11:46:18.807748
access URL: https://theses.hal.science/tel-00788467

test_moissonnage_selune
type: Agent