Ближайшая строка - Closest string

В теоретическая информатика, то ближайшая строка является NP-жесткий вычислительная проблема,^[1] который пытается найти геометрический центр набора входных строк.

Чтобы понять слово «центр», необходимо определить расстояние между двумя струнами. Обычно эту проблему исследуют с помощью Расстояние Хэмминга в уме.

Формальное определение

Более формально, учитывая п длина-м струны s₁, s₂, ..., s_п, ближайшая проблема строки ищет новую длину -м нить s такой, что d(s,s_я) ≤ k для всех я, куда d обозначает Расстояние Хэмминга, и где k как можно меньше.^[2] А проблема решения версия ближайшей строковой задачи, которая НП-полный, вместо этого берет k как еще один ввод и вопросы, есть ли строка в пределах расстояния Хэмминга k всех входных строк.^[1]

Ближайшую строковую проблему можно рассматривать как частный случай универсального 1-центровая проблема в котором расстояния между элементами измеряются с использованием расстояния Хэмминга.

Мотивация

В биоинформатика проблема ближайшей струны - это интенсивно исследуемая грань проблемы поиска сигналов в ДНК.

Упрощения и сокращение данных

Экземпляры ближайшей строки могут содержать информацию, которая не является существенной для проблемы. В некотором смысле обычный ввод ближайшей строки содержит информацию, не усложняющую задачу. Например, если некоторые строки содержат символ а, но ни один из них не содержит символа z, заменив все аs с zs даст по существу эквивалентный экземпляр, то есть: из решения модифицированного экземпляра исходное решение может быть восстановлено, и наоборот.

Нормализация ввода

Когда все входные строки одинаковой длины записываются друг на друга, они образуют матрицу. Некоторые типы строк по существу имеют одинаковые последствия для решения. Например, замена столбца записями (а, а, б) с другим столбцом (Икс, Икс, у) может привести к другой строке решения, но не может повлиять на разрешимость, поскольку оба столбца выражают одну и ту же структуру, а именно. первые две записи равны, но отличаются от третьей.

Экземпляр ввода может быть нормализованный путем замены в каждом столбце наиболее часто встречающегося символа на а, символ, который встречается вторым по частоте с б, и так далее. Учитывая решение нормализованного экземпляра, исходный экземпляр можно найти, переназначив символы решения его исходной версии в каждом столбце.

Порядок расположения столбцов не усугубляет проблему. Это означает, что если мы переставим все входные строки в соответствии с определенной перестановкой π и получим строку решения s к этому измененному экземпляру, то π⁻¹(s) будет решением оригинального экземпляра.

Пример

Найдите место для нормализованной проблемы. Центральная строка аааа и аааб приводит к расстояниям Хэмминга 1,2,1 и 2,1,1 соответственно.

Учитывая экземпляр с тремя входными строками uvwx, xuwv, и xvwu. Это можно было бы записать в виде такой матрицы:

ты	v	ш	Икс
Икс	ты	ш	v
Икс	v	ш	ты

Первый столбец содержит значения (ты, Икс, Икс). В качестве Икс является наиболее часто встречающимся символом, мы заменяем его на а, и мы заменяем ты, второй по частоте персонаж, по б, получив новый первый столбец (б, а, а). Второй столбец содержит значения (v, ты, v). Что касается первого столбца, v заменяется на а и ты заменяется на б, получив новый второй столбец (а, б, а). То же самое со всеми столбцами дает нормализованный экземпляр

б	а	а	а
а	б	а	б
а	а	а	c

Сокращение данных, полученных при нормализации

Нормализация ввода уменьшает размер алфавита до максимального количества входных строк. Это может быть полезно для алгоритмов, время работы которых зависит от размера алфавита.

Аппроксимируемость

Ли и др. развил схема полиномиальной аппроксимации^[3] который практически непригоден для использования из-за больших скрытых констант.

Управляемость с фиксированными параметрами

Ближайшая строка может быть решена в ${displaystyle O (kL + kdcdot d ^ {d})}$ , куда k количество входных строк, L - длина всех строк и d - желаемое максимальное расстояние от строки решения до любой входной строки.^[4]

Отношение к другим проблемам

Ближайшая строка - это частный случай более общего ближайшая подстрока проблема, которая строго сложнее. В то время как ближайшая строка оказывается управляемый с фиксированными параметрами во многих отношениях ближайшая подстрока W [1] -жесткий что касается этих параметров.