Shuffling biological sequences with motif constraints.

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

https://hal.inria.fr/inria-00187827
Contributor : Johanne Cohen Épouse Bournez <>
Submitted on : Thursday, November 15, 2007 - 12:41:13 PM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM

Links full text

Identifiers

Citation

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

Share

Metrics

Record views

320