A new fast fuzzy Cocke-Younger-Kasami algorithm for DNA strings analysis

In this paper we present a variation of the Cocke-Younger-Kasami algorithm (CYK algorithm) for the analysis of fuzzy free context languages applied to DNA strings. We propose a variation of the original CYK algorithm where we prove that the computational order of the new CYK algorithm is O(n). We prove that the new algorithm only uses O(2n) memory locations. The fuzzy context-free grammar (FCFG) is obtained from the DNA. The algorithm can be used to find regulatory motifs among other applications. In order to demonstrate the applications of the proposed algorithm, we present two examples. In the first example, we prove that it is possible to define a fuzzy grammar for a prototype DNA sequence and then find the membership grade of any arbitrary sequence against this specific pattern. As a second example, we construct a fuzzy grammar from the alignment of promoters obtained by a logo sequence algorithm for the Escherichia coli K12 DNA string, and then show how the proposed method can be used for discovery of the regulatory motifs.