The Open Applied Informatics Journal

2010, 4 : 10-14
Published online 2010 May 13. DOI: 10.2174/1874136301004010010
Publisher ID: TOAINFOJ-4-10

Counting of a Degenerate Word in Random Sequences

Wei-Mou Zheng and Ke-Song Liu
Beijing Genomics Institute, Shenzhen (BGI-SZ), Shenzhen 518083, China

ABSTRACT

Overlap of words complicates the problem of word counting. The technique of the imbedded Markov chain (IMC) uses an enlarged state space to recover the Markovian property for the word counting problem. A degenerate word represents multiple non-degenerate words. An efficient way to decompose a degenerate word according to its overlapping pattern for implementing IMC is proposed.

Keywords:

Imbedded Markov chain, degenerate motifs, word counting..