We introduce Markov models for segmentation of symbolic sequences, extending a 
segmentation procedure based on the Jensen-Shannon divergence that has been 
introduced earlier. Higher-order Markov models are more sensitive to the details 
of local patterns and in application to genome analysis, this makes it possible 
to segment a sequence at positions that are biologically meaningful. We show the 
advantage of higher-order Markov-model-based segmentation procedures in 
detecting compositional inhomogeneity in chimeric DNA sequences constructed from 
genomes of diverse species, and in application to the E. coli K12 genome, 
boundaries of genomic islands, cryptic prophages, and horizontally acquired 
regions are accurately identified.