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
CNRS - Centre National de la Recherche Scientifique : UMR8623, X - École polytechnique, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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 :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

https://hal.inria.fr/hal-01424452
Contributeur : Yann Ponty <>
Soumis le : lundi 2 janvier 2017 - 12:45:27
Dernière modification le : mardi 17 avril 2018 - 09:05:34
Document(s) archivé(s) le : mardi 4 avril 2017 - 00:34:29

Fichier

conf.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 1

Citation

Defne Surujon, Yann Ponty, Peter Clote. Small-world networks and RNA secondary structures. 2017. 〈hal-01424452〉

Partager

Métriques

Consultations de la notice

589

Téléchargements de fichiers

77