Новый подход к поиску строковой медианы и визуализация строковых кластеров

Рассматривается следующая задача о поиске медианы набора строк:
$$ c=\mathrm{argmin}_{a\in U}\sum_{b\in D}d(a,b), $$
где $D\subset G^{*}$ — конечный набор строк над алфавитом $G$, $U\subseteq G^{*}$, $d$ — редакционное расстояние Левенштейна. Эта задача имеет важные приложения, например в биоинформатике при анализе белковых последовательностей. Однако известно, что в общем случае для $U=G^{*}$ задача о медиане является NP-сложной. Поэтому для приближенного решения были предложены эвристические алгоритмы, в частности, жадный алгоритм. Мы предлагаем новый гибкий подход, базирующийся на гладкой аппроксимации расстояния Левенштейна $\tilde{d}$. В его основе лежит стохастическое кодирование символьных последовательностей и следующая формула для редакционного расстояния:
$$ d(X_{1},X_{2})=\min_{(X_{1}',X_{2}'')_{e}\subseteq X_{1}\times X_{2}} \Bigl\{\frac{1}{2}\,\|X_{1}'-X_{2}''\|_{1}+|X_{1}|-|X_{1}'|+ |X_{2}|-|X_{2}''|\Bigr\}, $$
где минимум берется по всем подпоследовательностям $(X_{1}',X_{2}'')_{e}$ равной длины. С одной стороны, стохастическое кодирование расширяет класс, на котором ищется экстремум. Однако наш основной результат показывает, что медиана не меняется. С другой стороны, теперь мы можем воспользоваться гладкими методами оптимизации, если заменить минимум в определении выше его гладким приближением. Мы приводим детали реализации на основе градиентного спуска, включая рекуррентные формулы расчета $\tilde{d}$. Эффективный расчет приближенной медианы позволяет, например, применить метод $k$-средних для кластеризации строк. Мы даем способ визуализации этих кластеров на основе метода стохастического вложения соседей tSNE.