Institute Homepage DE Sign In

Back

Empirical Inference Conference Paper 2001

Unsupervised Segmentation and Classification of Mixtures of Markovian Sources

no image
Empirical Inference
Yevgeny Seldin

We describe a novel algorithm for unsupervised segmentation of sequences into alternating Variable Memory Markov sources, first presented in [SBT01]. The algorithm is based on competitive learning between Markov models, when implemented as Prediction Suffix Trees [RST96] using the MDL principle. By applying a model clustering procedure, based on rate distortion theory combined with deterministic annealing, we obtain a hierarchical segmentation of sequences between alternating Markov sources. The method is applied successfully to unsupervised segmentation of multilingual texts into languages where it is able to infer correctly both the number of languages and the language switching points. When applied to protein sequence families (results of the [BSMT01] work), we demonstrate the method‘s ability to identify biologically meaningful sub-sequences within the proteins, which correspond to signatures of important functional sub-units called domains. Our approach to proteins classification (through the obtained signatures) is shown to have both conceptual and practical advantages over the currently used methods.

Author(s): Seldin, Y. and Bejerano, G. and Tishby, N.
Journal: The 33rd Symposium on the Interface of Computing Science and Statistics (Interface 2001 - Frontiers in Data Mining and Bioinformatics)
Pages: 1-15
Year: 2001
Day: 0
Bibtex Type: Conference Paper (inproceedings)
Event Name: 33rd Symposium on the Interface of Computing Science and Statistics (Interface 2001 - Frontiers in Data Mining and Bioinformatics)
Digital: 0
Electronic Archiving: grant_archive
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik
Links:

BibTex 

@inproceedings{6586,
  title = {Unsupervised Segmentation and Classification of Mixtures of Markovian Sources},
  journal = {The 33rd Symposium on the Interface of Computing Science and Statistics (Interface 2001 - Frontiers in Data Mining and Bioinformatics)},
  abstract = {We describe a novel algorithm for unsupervised segmentation of sequences into alternating Variable Memory Markov sources, first presented in [SBT01]. The algorithm is based on competitive learning between Markov models, when
  implemented as Prediction Suffix Trees [RST96] using the MDL principle. By applying a model clustering procedure, based on rate distortion theory combined with deterministic annealing, we obtain a hierarchical segmentation of
  sequences between alternating Markov sources. The method is applied successfully to unsupervised segmentation of multilingual texts into languages
  where it is able to infer correctly both the number of languages and the language switching points. When applied to protein sequence families (results of the [BSMT01] work), we demonstrate the method‘s ability to identify biologically meaningful sub-sequences within the proteins, which correspond to
  signatures of important functional sub-units called domains. Our approach to proteins classification (through the obtained signatures) is shown to have both conceptual and practical advantages over the currently used methods.},
  pages = {1-15},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  year = {2001},
  slug = {6586},
  author = {Seldin, Y. and Bejerano, G. and Tishby, N.}
}