Computing the likelihood of sequence segmentation under Markov modelling

2009/11/16 by Laurent Guéguen, Guéguen, Laurent
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Bayesian Methods and Mixture Models #FOS: Biological sciences #Genome Rearrangement Algorithms #Genomics (q-bio.GN) #Quantitative Methods (q-bio.QM)

paper · pdf · doi:10.48550/arxiv.0911.3070

openalex publication_date 2009/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

I tackle the problem of partitioning a sequence into homogeneous segments, where homogeneity is defined by a set of Markov models. The problem is to study the likelihood that a sequence is divided into a given number of segments. Here, the moments of this likelihood are computed through an efficient algorithm. Unlike methods involving Hidden Markov Models, this algorithm does not require probability transitions between the models. Among many possible usages of the likelihood, I present a maximum a posteriori probability criterion to predict the number of homogeneous segments into which a sequence can be divided, and an application of this method to find CpG islands.

Citations

• A tutorial on hidden Markov models and selected applications in speech recognition
• Biological sequence analysis

Related

• Hybrid classifiers of pairwise Markov models
• Composite likelihood inference in a discrete latent variable model for\n two-way "clustering-by-segmentation" problems
• A model selection approach for multiple sequence segmentation and\n dimensionality reduction
• MAP segmentation in Bayesian hidden Markov models: a case study
• Bayesian Blocks in Two or More Dimensions: Image Segmentation and Cluster Analysis