KIS: An automated attribute induction method for classification of DNA sequences

Biedrzycki, Rafał; Arabas, Jarosław

doi:10.2478/v10006-012-0053-2

Abstract

This paper presents an application of methods from the machine learning domain to solving the task of DNA sequence recognition. We present an algorithm that learns to recognize groups of DNA sequences sharing common features such as sequence functionality. We demonstrate application of the algorithm to find splice sites, i.e., to properly detect donor and acceptor sequences. We compare the results with those of reference methods that have been designed and tuned to detect splice sites. We also show how to use the algorithm to find a human readable model of the IRE (Iron-Responsive Element) and to find IRE sequences. The method, although universal, yields results which are of quality comparable to those obtained by reference methods. In contrast to reference methods, this approach uses models that operate on sequence patterns, which facilitates interpretation of the results by humans.

References

Baten, A.K.M.A., Chang, B.C.H., Halgamuge, S.K. and Li, J. (2006). Splice site identification using probabilistic parameters and SVMclassification, BMC Bioinformatics 7(Suppl 5): S15, DOI:10.1186/1471-2105-7-S5-S15.10.1186/1471-2105-7-S5-S15176447117254299
Search in Google Scholar
Berget, S.M., Moore, C. and Sharp, P.A. (1977). Spliced segments at the 5’ terminus of adenovirus 2 late mRNA, Proceedings of the National Academy of Sciences 74(8): 3171-3175.10.1073/pnas.74.8.3171431482269380
Search in Google Scholar
Carrasco, R.C. and Oncina, J. (1994). Learning stochastic regular grammars by means of a state merging method, ICGI’94: Proceedings of the Second International Colloquium on Grammatical Inference and Applications, Alicante, Spain, pp. 139-152.
Search in Google Scholar
Chen, T.-M., Lu, C.-C. and Li,W.-H. (2005). Prediction of splice sites with dependency graphs and their expanded Bayesian networks, Bioinformatics 21(4): 471-482.10.1093/bioinformatics/bti02515374869
Search in Google Scholar
Davis, J. and Goadrich, M. (2006). The relationship between Precision-Recall and ROC curves, ICML’06: Proceedings of the 23rd International Conference on Machine Learning, Pittsburgh, PA, USA, pp. 233-240.
Search in Google Scholar
Deshpande, M. and Karypis, G. (2002). Evaluation of techniques for classifying biological sequences, Pacific-Asia Conference on Knowledge Discovery and Data Mining, Taipei, Taiwan, pp. 417-431.
Search in Google Scholar
Diederich, J. (2008). Rule Extraction from Support Vector Machines, Studies in Computational Intelligence, Vol. 80, Springer, Berlin/Heidelberg.
Search in Google Scholar
Durbin, R., Eddy, S.R., Krogh, A. and Mitchison, G. (1998). Biological Sequence Analysis-Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press, Cambridge.10.1017/CBO9780511790492
Search in Google Scholar
Elsik, C.G., Worley, K.C., Zhang, L., Milshina, N.V., Jiang, H., Reese, J.T., Childs, K.L., Venkatraman, A., Dickens, C.M., Weinstock, G.M. and Gibbs, R.A. (2006). Community annotation: Procedures, protocols, and supporting tools, Genome Research 16(11): 1329-1333.10.1101/gr.558060617065605
Search in Google Scholar
Kashiwabara, A.Y., Vieira, D.C.G., Machado-Lima, A. and Durham, A.M. (2007). Splice site prediction using stochastic regular grammars, GMR 6(1): 105-115.
Search in Google Scholar
Michalewicz, Z. (1996). Genetic Algorithms + Data Structures = Evolution Programs, 3rd Edn., Springer-Verlag, London.
Search in Google Scholar
Oncina, J. and Garcia, P. (1992). Inferring regular languages in polynomial update time, in A. Sanfeliu, N. P´erez de la Blanca and E. Vidal (Eds.), Pattern Recognition and Image Analysis, World Scientific Publishing, Singapore, pp. 49-61.
Search in Google Scholar
Pesole, G., Grillo, G., Larizza, A. and Liuni, S. (2000). The untranslated regions of eukaryotic mRNAs: Structure, function, evolution and bioinformatic tools for their analysis, Briefings in Bioinformatics 1(3): 236-249.10.1093/bib/1.3.23611465035
Search in Google Scholar
Quinlan, J.R. (1986). Induction of decision trees, Machine Learning 1(1): 81-106.10.1007/BF00116251
Search in Google Scholar
Quinlan, J.R. (1993). C4.5: Programs for Machine Learning, Morgan Kaufmann Publishers, San Francisco, CA.
Search in Google Scholar
R¨atsch, G. and Sonnenburg, S. (2004). Accurate Splice Site Detection for Caenorhabditis Elegans, MIT Press, Cambridge, MA.
Search in Google Scholar
R¨atsch, G., Sonnenburg, S. and Sch¨olkopf, B. (2005). RASE: Recognition of alternatively spliced exons in C. elegans, Bioinformatics 21(Suppl 1): i369-i377.
Search in Google Scholar
Reese, M.G., Eeckman, F.H., Kulp, D. and Haussler, D. (1997). Improved splice site detection in Genie, Journal of Computational Biology 4(3): 311-324.10.1089/cmb.1997.4.3119278062
Search in Google Scholar
Ron, D., Singer, Y. and Tishby, N. (1996). The power of amnesia: Learning probabilistic automata with variable memory length, Machine Learning 25(2): 117-149.10.1007/BF00114008
Search in Google Scholar
Ron, D., Singer, Y. and Tishby, N. (1998). On the learnability and usage of acyclic probabilistic finite automata, Journal of Computer and System Sciences 56(2): 133-152.10.1006/jcss.1997.1555
Search in Google Scholar
Sonnenburg, S. (2009). Machine Learning for Genomic Sequence Analysis, Ph.D. thesis, Technischen Universit¨at Berlin, Berlin.
Search in Google Scholar
Sonnenburg, S., Schweikert, G., Philips, P., Behr, J. and R¨atsch, G. (2007). Accurate splice site prediction using support vector machines, BMC Bioinformatics 8(Suppl 10): S7.10.1186/1471-2105-8-S10-S7223050818269701
Search in Google Scholar
Tickle, A., Andrews, R., Golea, M. and Diederich, J. (1998). The truth will come to light: Directions and challenges in extracting the knowledge embedded within trained artificial neural networks, IEEE Transactions on Neural Networks 9(6): 1057-1068.10.1109/72.72835218255792
Search in Google Scholar

KIS: An automated attribute induction method for classification of DNA sequences

Abstract

Paradigm

My account