Skip to Main content Skip to Navigation
New interface
Conference papers

Forbidden substrings and the connectivity of the Hamming graph of RNA sequences: Partial disconnectivity tests

Maher Mallem 1 Alain Denise 1 Yann Ponty 2 
2 AMIBIO - Algorithms and Models for Integrative BIOlogy
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : RNA structure design methods have grown in complexity to cover an increasing scope of application. Recent approaches combine an initial random generation with a local optimization step, and consider both a user-specified secondary structure and sets of mandatory and forbidden substrings. Although these additional constraints lead to better design results, they may interfere with the local optimization phase. Indeed, forbidden substrings may disrupt the connectivity of their underlying search space, a key property for the success of the local search. A naive connectivity test would explore the whole graph of candidate sequences, leading to an exponential time connectivity test. In this work, we propose two partial algorithms based on compact graph structures-the De Bruijn graphs and the Aho-Corasick automaton-allowing the detection of disconnectivity in time independent from the length of RNA sequence. Tested on random instances, our tests were able to detect the disconnectivity with sensitivity ranging between 35% and 55%, motivating further research.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Yann Ponty Connect in order to contact the contributor
Submitted on : Wednesday, December 11, 2019 - 10:47:35 AM
Last modification on : Saturday, June 25, 2022 - 10:42:46 PM
Long-term archiving on: : Thursday, March 12, 2020 - 1:26:09 PM


Files produced by the author(s)


  • HAL Id : hal-02403517, version 1


Maher Mallem, Alain Denise, Yann Ponty. Forbidden substrings and the connectivity of the Hamming graph of RNA sequences: Partial disconnectivity tests. SEQBIM 2019 - Séquences en Bioinformatique, Informatique et Mathématiques, Dec 2019, Marne-la-Vallée, France. ⟨hal-02403517⟩



Record views


Files downloads