Chapman-Kolmogorov Relation Based Median String Algorithm for DNA Consensus Classification

Abstract

Consensus string is the most frequent common pattern in a set of string. Consensus string is an important feature of DNA sequence. Many algorithm have been introduced to discover consensus string. Among them, median string algorithm is the most popular one. Basically, that is a brute force algorithm.DNA sequence is composed of a series of four letter alphabet Σ={a,c,g,t}. If the size of the consensus string is l, then the algorithm generates all the 4l number of l length strings called motifs or l-mer. Then try to fit the motifs one by one with the sequence. In this paper we have discovered a way to reduce the search space using chapman kolmogorov relation. We found that, the proposed system can find the same consensus string within a shorter period of time than the time taken by the median string algorithm. As the l-mer size increases, the proposed system takes much less time than the median string algorithm. For l-mer size 7, we found the proposed system is 47 times faster than the median string algorithm.