Обучение cтроковых ядер с использованием адаптивного сжатия переменной длины

На данный момент в биоинформатике существует несколько подходов к классификации белковых последовательностей и один из таких подходов основан на мерах расстояния/сходства, применительно к строковым данным. В данной работе представлен новый подход – LZW-ядро, основанное на технике сжатия информации Лемпеля-Зива-Велча. Необходимость в новом подходе произрастает из того, что на данный момент существует сильная взаимосвязь между вычислительной сложностью алгоритма, определяющего расстояние/сходство между строками и дальнейшим качеством полученной меры, для использования ее в алгоритмах машинного обучения – более вычислительно емкие методы дают более качественные меры. Задача состоит в сокращении разрыва между качеством метода и его вычислительной сложностью. Лидером в области качества на данный момент является алгоритм Смита-Ватермана, однако он также является кубическим по вычислительной сложности, что делает его неприменимым к большим объемам данных. LZW-ядро было протестировано в двух методах классификации – метод опорных векторов и метод ближайших соседей, где было рассмотрено разное их число. В данной работе удалось получить лучшее качество классификации, по сравнению с другими методами, квадратичными по времени выполнения, однако не удалось превзойти по качеству алгоритм Смита-Ватермана.