Generalized Hierarchical Markov Models for the Discovery of Length-Constrained Sequence Features from Genome Tiling Arrays

ABSTRACT

Summary .   A generalized hierarchical Markov model for sequences that contain length-restricted features is introduced. This model is motivated by the recent development of high-density tiling array data for determining genomic elements of functional importance. Due to length constraints on certain features of interest, as well as variability in probe behavior, usual hidden Markov-type models are not always applicable. A robust Bayesian framework that can incorporate length constraints, probe variability, and bias is developed. Moreover, a novel recursion-based Monte Carlo algorithm is proposed to estimate the parameters and impute hidden states under length constraints. Application of this methodology to yeast chromosomal arrays demonstrate substantial improvement over currently existing methods in terms of sensitivity as well as biological interpretability.