title: Counting of oligomers in sequences generated by markov chains for DNA motif discovery.
abstract: By means of the technique of the imbedded Markov chain, an efficient algorithm is proposed to exactly calculate first, second moments of word counts and the probability for a word to occur at least once in random texts generated by a Markov chain. A generating function is introduced directly from the imbedded Markov chain to derive asymptotic approximations for the problem. Two Z-scores, one based on the number of sequences with hits and the other on the total number of word hits in a set of sequences, are examined for discovery of motifs on a set of promoter sequences extracted from A. thaliana genome. Source code is available at http://www.itp.ac.cn/zheng/oligo.c.
authors.affiliation: Beijing Genomics Institute, Shenzhen (BGI-SZ), Shenzhen 518083, China.
authors.forename: Gao
authors.initials: G
authors.lastname: Shan
authors.forename: Wei-Mou
authors.initials: WM
authors.lastname: Zheng
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D016384:Consensus Sequence / Q000235:genetics*; D004247:DNA / Q000235:genetics*; D003627:Data Interpretation, Statistical; D008390:Markov Chains; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*
chemical_list: D004247:DNA