Motif based sequence classification

E. P. Ofitserov

Čebyševskij sbornik, Tome 19 (2018) no. 1, pp. 187-199.

Résumé

Sequence classification problems often arise in such areas as bioinformatics and natural language processing. In the last few year best results in this field were achieved by the deep learning methods, especially by architectures based on recurrent neural networks (RNN). However, the common problem of such models is a lack of interpretability, i.e., extraction of key features from data that affect the most the model's decision. Meanwhile, using of less complicated neural network leads to decreasing predictive performance thus limiting usage of state-of-art machine learning methods in many subject areas. In this work we propose a novel interpretable deep learning architecture based on extraction of principal sets of short substrings — sequence motifs. The presence of extracted motif in the input sequence is a marker for a certain class. The key component of proposed solution is differential alignment algorithm developed by us, which provides a smooth analog of classical string comparison methods such as Levenshtein edit distance, and Smith–Waterman local alignment. Unlike previous works devoted to the motif based classification, which used CNN for shift-invariant searching, ours model provide a way to shift and gap invariant extraction of motifs.

Détail

Keywords: sequence classification, machine learning, neural network, motif extraction.

Bibliographie

[1] Hochreiter S., Schmidhuber J., “Long short-term memory”, Neural computation, 9:8 (1997), 1735–1780 | DOI

[2] K. Cho et al., Learning phrase representations using RNN encoder-decoder for statistical machine translation, 2014, arXiv: 1406.1078

[3] J. Chung et al., Empirical evaluation of gated recurrent neural networks on sequence modeling, 2014, arXiv: 1412.3555

[4] Karpathy A., Johnson J., Fei-Fei L., Visualizing and understanding recurrent networks, 2015, arXiv: 1506.02078

[5] H. Strobelt et al., “Lstmvis: A tool for visual analysis of hidden state dynamics in recurrent neural networks”, IEEE transactions on visualization and computer graphics, 24:1 (2018), 667–676 | DOI

[6] H. Zeng et al., “Convolutional neural network architectures for predicting DNA-protein binding”, Bioinformatics, 32:12 (2016), i121–i127 | DOI

[7] Zhou J., Troyanskaya O. G., “Predicting effects of noncoding variants with deep learning-based sequence model”, Nature methods, 12:10 (2015), 931 | DOI

[8] J. Lanchantin et al., Deep motif: Visualizing genomic sequence classifications, 2016, arXiv: 1605.01133

[9] Quang D., Xie X., “DanQ: a hybrid convolutional and recurrent deep neural network for quantifying the function of DNA sequences”, Nucleic acids research, 44:11 (2016), e107–e107 | DOI

[10] Levenshtein V. I., “Binary codes with correction of fallouts, inserts and notes”, Reports of the Academy of Sciences, 163:4 (1965), 845–848 (in Russian) | Zbl

[11] Smith T. F., Waterman M. S., “Comparison of biosequences”, Advances in applied mathematics, 2:4 (1981), 482–489 | DOI | MR | Zbl

[12] Gotoh O., “An improved algorithm for matching biological sequences”, Journal of molecular biology, 162:3 (1982), 705–708 | DOI

[13] Manavski S. A., Valle G., “CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment”, BMC bioinformatics, 9:2 (2008), S10 | DOI

[14] Ioffe S., Szegedy C., Batch normalization: Accelerating deep network training by reducing internal covariate shift, 2015, arXiv: 1502.03167

[15] Hahnloser R. H. R. et al., “Digital selection and analogue amplification coexist in a cortex-inspired silicon circuit”, Nature, 405:6789 (2000), 947 | DOI