A generalization of the PST algorithm: modeling the sparse nature of protein sequences.
BACKGROUND
A central problem in genomics is to determine the function of a protein using the information contained in its amino acid sequence. Variable length Markov chains (VLMC) are a promising class of models that can effectively classify proteins into families and they can be estimated in linear time and space.


RESULTS
We introduce a new algorithm, called Sparse Probabilistic Suffix Trees (SPST), that identifies equivalence between the contexts of a VLMC. We show that, in many cases, the identification of these equivalence can improve the classification rate of the classical Probabilistic Suffix Trees (PST) algorithm. We also show that better classification can be achieved by identifying representative fingerprints in the amino acid chains, and this variation in the SPST algorithm is called F-SPST.
Leonardi
Florencia G
FG
Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, CEP 05508-090, São Paulo, Brazil. leonardi@ime.usp.br
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D023281:Genomics / Q000379:methods; D020407:Internet; D008390:Markov Chains; D015233:Models, Statistical; D011336:Probability; D016415:Sequence Alignment; D020539:Sequence Analysis, Protein / Q000379:methods*; D012984:Software