TY - JOUR
T1 - A new fast fuzzy Cocke-Younger-Kasami algorithm for DNA strings analysis
AU - Molina-Lozano, Heron
N1 - Funding Information:
This work was supported by the Instituto de Ciencia y Tecnologia del Distrito Federal (ICyTDF) under project No. PICCT08-22. We also thank the support of the IPN (SIP-IPN, COFFA-IPN and PIFI-IPN). Any opinions, findings and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the sponsoring agency.
PY - 2011/9
Y1 - 2011/9
N2 - 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.
AB - 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.
KW - Cocke-Younger-Kasami algorithm
KW - DNA
KW - Fuzzy logic
KW - Pattern recognition
UR - http://www.scopus.com/inward/record.url?scp=80052125306&partnerID=8YFLogxK
U2 - 10.1007/s13042-011-0042-z
DO - 10.1007/s13042-011-0042-z
M3 - Artículo
SN - 1868-8071
VL - 2
SP - 209
EP - 218
JO - International Journal of Machine Learning and Cybernetics
JF - International Journal of Machine Learning and Cybernetics
IS - 3
ER -