Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-02403517
Contributor : Yann Ponty <>
Submitted on : Wednesday, December 11, 2019 - 10:47:35 AM
Last modification on : Saturday, February 1, 2020 - 1:53:31 AM
Document(s) archivé(s) le : Thursday, March 12, 2020 - 1:26:09 PM

File

Design_Connectivity_Maher_2019...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02403517, version 1

Citation

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⟩

Share

Metrics

Record views

24

Files downloads

311