Skip to Main content Skip to Navigation
Journal articles

Exact distribution of a pattern in a set of random sequences generated by a Markov source: applications to biological data.

Abstract : BACKGROUND: In bioinformatics it is common to search for a pattern of interest in a potentially large set of rather short sequences (upstream gene regions, proteins, exons, etc.). Although many methodological approaches allow practitioners to compute the distribution of a pattern count in a random sequence generated by a Markov source, no specific developments have taken into account the counting of occurrences in a set of independent sequences. We aim to address this problem by deriving efficient approaches and algorithms to perform these computations both for low and high complexity patterns in the framework of homogeneous or heterogeneous Markov models. RESULTS: The latest advances in the field allowed us to use a technique of optimal Markov chain embedding based on deterministic finite automata to introduce three innovative algorithms. Algorithm 1 is the only one able to deal with heterogeneous models. It also permits to avoid any product of convolution of the pattern distribution in individual sequences. When working with homogeneous models, Algorithm 2 yields a dramatic reduction in the complexity by taking advantage of previous computations to obtain moment generating functions efficiently. In the particular case of low or moderate complexity patterns, Algorithm 3 exploits power computation and binary decomposition to further reduce the time complexity to a logarithmic scale. All these algorithms and their relative interest in comparison with existing ones were then tested and discussed on a toy-example and three biological data sets: structural patterns in protein loop structures, PROSITE signatures in a bacterial proteome, and transcription factors in upstream gene regions. On these data sets, we also compared our exact approaches to the tempting approximation that consists in concatenating the sequences in the data set into a single sequence. CONCLUSIONS: Our algorithms prove to be effective and able to handle real data sets with multiple sequences, as well as biological patterns of interest, even when the latter display a high complexity (PROSITE signatures for example). In addition, these exact algorithms allow us to avoid the edge effect observed under the single sequence approximation, which leads to erroneous results, especially when the marginal distribution of the model displays a slow convergence toward the stationary distribution. We end up with a discussion on our method and on its potential improvements.
Document type :
Journal articles
Complete list of metadata

Cited literature [54 references]  Display  Hide  Download
Contributor : Ed. BMC Connect in order to contact the contributor
Submitted on : Friday, January 27, 2012 - 1:03:44 PM
Last modification on : Wednesday, May 18, 2022 - 3:40:27 AM
Long-term archiving on: : Monday, November 19, 2012 - 2:55:16 PM


Publisher files allowed on an open archive


Distributed under a Creative Commons Attribution 4.0 International License



Gregory Nuel, Leslie Regad, Juliette Martin, Anne-Claude Camproux. Exact distribution of a pattern in a set of random sequences generated by a Markov source: applications to biological data.. Algorithms for Molecular Biology, BioMed Central, 2010, 5 (1), pp.15. ⟨10.1186/1748-7188-5-15⟩. ⟨inserm-00663534⟩



Record views


Files downloads