QM Logo ATI Logo Fabrizio

Mebomine Logo

POKer: a Partial Order Kernel for comparing strings with alternative substrings

  1. Abdollahyan and F. Smeraldi, in Proceedings of the European Symposium on Artificial Neural Networks (ESANN), pp 263-268, 2017


We introduce a Partial Order Kernel (POKer) on the weighted sum of local alignment scores that can be used for comparison and classification of strings containing alternative substrings of variable length. POKer is defined over the product of two directed acyclic graphs, each representing a string with alternative substrings, and is computed efficiently using dynamic programming. We evaluate the performance of POKer with Support Vector Machines on a dataset of strings generated by detecting overlapping motifs in a set of simulated DNA sequences. Compared to a generalization of a state-of-the-art string kernel, POKer achieves a higher classification accuracy.

(Full text and Python code)

Backlinks: Home , Publications