Statistical Algorithm for DNA Repeats Frequency Based on Finite State Automaton
Xin De-dongb · Jisuanji gongcheng · 2011
The existing statistical algorithms for DNA repeats frequency have some defects on efficiency,flexibility and so on.Based on Finite State Automaton(FSA) for string multiple patterns matching,this paper constructs a DNA subsequence comparative automaton,and optimizes the automaton's state transition based on the idea of Knuth-Morris-Pratt(KMP).By on-line scanning DNA database,it can achieve all DNA subsequence's statistics in the whole database,including the frequency statistics of overlapped or nonoverlapped repeats and the longest common subsequence in a designated DNA sequence set.Experimental results show that the algorithm has advantages of efficiency,precise matching,flexible information acquisition,supporting on-line operation and so on.