  Applying machine learning to biological sequences - DNA, RNA and protein -
has enormous potential to advance human health, environmental sustainability,
and fundamental biological understanding. However, many existing machine
learning methods are ineffective or unreliable in this problem domain. We study
these challenges theoretically, through the lens of kernels. Methods based on
kernels are ubiquitous: they are used to predict molecular phenotypes, design
novel proteins, compare sequence distributions, and more. Many methods that do
not use kernels explicitly still rely on them implicitly, including a wide
variety of both deep learning and physics-based techniques. While kernels for
other types of data are well-studied theoretically, the structure of biological
sequence space (discrete, variable length sequences), as well as biological
notions of sequence similarity, present unique mathematical challenges. We
formally analyze how well kernels for biological sequences can approximate
arbitrary functions on sequence space and how well they can distinguish
different sequence distributions. In particular, we establish conditions under
which biological sequence kernels are universal, characteristic and metrize the
space of distributions. We show that a large number of existing kernel-based
machine learning methods for biological sequences fail to meet our conditions
and can as a consequence fail severely. We develop straightforward and
computationally tractable ways of modifying existing kernels to satisfy our
conditions, imbuing them with strong guarantees on accuracy and reliability.
Our proof techniques build on and extend the theory of kernels with discrete
masses. We illustrate our theoretical results in simulation and on real
biological data sets.
