Motifs Finding Algorithm Based On 3^rd Order Markov Model And Max Flow

DNA motif finding is one of the core problems in bioinformatics. There are abundant vital character informations in motif. The starting point of motif finding technology is to find out the similar fragments from the sequences, through which the rule of gene regulation can be discovered so that mystery of life is revealed.First of all, this paper introduces the status quo about motif finding including two classes of motif-finding methods:Enumeration-based method and local search-based approach, PSSM model and the score criteria of motif. All of them have a built-in assumption that the probability of each nucleotide at each position in the motif is independent of the nucleotide at other position. However, there are already evidences that have proved the dependence between the bases. Aiming at it, this paper uses the 3rd order Morkov Model which expresses the dependence between the bases. Firstly, the algorithm converts the input sequences to graph, and then finds out the maximum density subgraph of graph with max-flow algorithm, for short MDS, and shows the motif with MDS with a polynomial time solution.