Bioinformatics Vol. 17 no. 10 2001
Pages 927-934
© 2001 Oxford University Press
Markovian domain fingerprinting: statistical segmentation of protein sequences
1 School of Computer Science &
Engineering, The Hebrew University, Jerusalem 91904, Israel
2 Department of Molecular Genetics &
Biotechnology, Hadassah Medical School, The Hebrew University, POB
12272, Jerusalem 91120, Israel
Received on April 20, 2001
; revised on July 9, 2001
; accepted on July 9, 2001
Motivation: Characterization of a protein family by its distinct sequence domains is crucial for functional annotation and correct classification of newly discovered proteins. Conventional Multiple Sequence Alignment (MSA) based methods find difficulties when faced with heterogeneous groups of proteins. However, even many families of proteins that do share a common domain contain instances of several other domains, without any common underlying linear ordering. Ignoring this modularity may lead to poor or even false classification results. An automated method that can analyze a group of proteins into the sequence domains it contains is therefore highly desirable.
Results: We apply a novel method to the problem of protein domain detection. The method takes as input an unaligned group of protein sequences. It segments them and clusters the segments into groups sharing the same underlying statistics. A Variable Memory Markov (VMM) model is built using a Prediction Suffix Tree (PST) data structure for each group of segments. Refinement is achieved by letting the PSTs compete over the segments, and a deterministic annealing framework infers the number of underlying PST models while avoiding many inferior solutions. We show that regions of similar statistics correlate well with protein sequence domains, by matching a unique signature to each domain. This is done in a fully automated manner, and does not require or attempt an MSA. Several representative cases are analyzed. We identify a protein fusion event, refine an HMM superfamily classification into the underlying families the HMM cannot separate, and detect all 12 instances of a short domain in a group of 396 sequences.
Contact: jill{at}cs.huji.ac.il; tishby{at}cs.huji.ac.il
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  L. Gueguen Sarment: Python modules for HMM analysis and partitioning of sequences Bioinformatics, August 15, 2005; 21(16): 3427 - 3428. [Abstract] [Full Text] [PDF]
|
|