Small-world networks and RNA secondary structures

Defne Surujon 1 Yann Ponty 2, 3, 4 Peter Clote 1, *
* Auteur correspondant
4 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Let $S_n$ denote the network of all RNA secondary structures of length $n$, in which undirected edges exist between structures $s$, $t$ such that $t$ is obtained from $s$ by the addition, removal or shift of a single base pair. Using context-free grammars, generating functions and complex analysis, we show that the asymptotic average degree is $O(n)$ and that the asymptotic clustering coefficient is $O(1/n)$, from which it follows that the family $S_n$, $n = 1, 2, 3,\ldots$ of secondary structure networks is not small-world.
Type de document :
Article dans une revue
Journal of computational biology : a journal of computational molecular cell biology, Mary Ann Liebert 2018
Liste complète des métadonnées

https://hal.inria.fr/hal-01424452
Contributeur : Yann Ponty <>
Soumis le : mardi 11 septembre 2018 - 15:25:51
Dernière modification le : jeudi 13 septembre 2018 - 14:02:32

Fichier

main2018.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01424452, version 2

Citation

Defne Surujon, Yann Ponty, Peter Clote. Small-world networks and RNA secondary structures. Journal of computational biology : a journal of computational molecular cell biology, Mary Ann Liebert 2018. 〈hal-01424452v2〉

Partager

Métriques

Consultations de la notice

271

Téléchargements de fichiers

22