Shuffling biological sequences with motif constraints. - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Discrete Algorithms Année : 2007

Shuffling biological sequences with motif constraints.

Résumé

We study the following problem: given a biological sequence S, a multiset Click to view the MathML source of motifs and an integer k, generate uniformly random sequences which contain the given motifs and have exactly the same frequencies of occurrence of k-lets (i.e. factors of length k) of S. We notably prove that the problem of deciding whether a sequence respects the given motif constraints is NP-complete. Nevertheless, we give a random generation algorithm which turns out to be experimentally efficient.

Dates et versions

inria-00187827 , version 1 (15-11-2007)

Identifiants

Citer

Dominique Barth, Johanne Cohen, Alain Denise, Romain Rivière. Shuffling biological sequences with motif constraints.. Journal of Discrete Algorithms, 2007, ⟨10.1016/j.jda.2007.06.001⟩. ⟨inria-00187827⟩
135 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More