  We consider the analysis of sets of categorical sequences consisting of
piecewise homogeneous Markov segments. The sequences are assumed to be governed
by a common underlying process with segments occurring in the same order for
each sequence. Segments are defined by a set of unobserved changepoints where
the positions and number of changepoints can vary from sequence to sequence. We
propose a Bayesian framework for analyzing such data, placing priors on the
locations of the changepoints and on the transition matrices and using Markov
chain Monte Carlo (MCMC) techniques to obtain posterior samples given the data.
Experimental results using simulated data illustrates how the methodology can
be used for inference of posterior distributions for parameters and
changepoints, as well as the ability to handle considerable variability in the
locations of the changepoints across different sequences. We also investigate
the application of the approach to sequential data from two applications
involving monsoonal rainfall patterns and branching patterns in trees.
