Extending the range of Markov models for biological sequence analysis

While having already successfully helped at solving various bioinformatics tasks, Markov chains are still challenging state-of-the-art statistics when optimal choices of the order of the chain are sought. This problem is actually two-fold, involving the choice of a set of models under consideration as well as the definition of an optimality criterion. This talk will first introduce increasingly refined variants of Markov models that have been introduced in the past, which allow the modeler to draw a finer-grained compromise between model complexity and the amount of information carried by the data. Bayesian model selection is a privileged framework to achieve such a compromise, yet the choice of priors is hindering its practical implementation: principled solutions ensuring that models are compared on an equal footing are indeed still missing. A solution to this issue that is currently investigated in collaboration with the group of I. Grosse (Halle-Wittenberg university) will be presented.