Small-world networks and RNA secondary structures

* Corresponding author
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
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.
Document type :
Preprints, Working Papers, ...

https://hal.inria.fr/hal-01424452
Contributor : Yann Ponty <>
Submitted on : Monday, January 2, 2017 - 12:45:27 PM
Last modification on : Wednesday, September 16, 2020 - 5:11:59 PM
Long-term archiving on: : Tuesday, April 4, 2017 - 12:34:29 AM

File

conf.pdf
Files produced by the author(s)

Identifiers

• HAL Id : hal-01424452, version 1

Citation

Defne Surujon, Yann Ponty, Peter Clote. Small-world networks and RNA secondary structures. 2017. ⟨hal-01424452v1⟩

Record views