Exact distribution of a pattern in a set of random sequences generated by a Markov source: applications to biological data. - Archive ouverte HAL Access content directly
Journal Articles Algorithms for Molecular Biology Year : 2010

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

(1, 2) , (3, 4) , (3, 5, 6) , (3, 4)
1
2
3
4
5
6

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.
Fichier principal
Vignette du fichier
1748-7188-5-15.pdf (671.64 Ko) Télécharger le fichier
Vignette du fichier
1748-7188-5-15.xml (187.04 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Format : Other
Loading...

Dates and versions

inserm-00663534 , version 1 (27-01-2012)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

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, 2010, 5 (1), pp.15. ⟨10.1186/1748-7188-5-15⟩. ⟨inserm-00663534⟩
288 View
189 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More