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

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

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

Более формально, если заданы n строк s ₁ , s ₂ , ..., s _n длины m , то задача поиска ближайшей строки ищет новую строку s длины m такую, что d ( s , si ₎ ≤ k для всех i , где d — расстояние Хэмминга , а k — как можно меньше. ^[2] Версия задачи поиска ближайшей строки, которая является NP-полной , вместо этого принимает k в качестве другого входного значения и спрашивает, есть ли строка в пределах расстояния Хэмминга k всех входных строк. ^[1]

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

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

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

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

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

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

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

Первый столбец имеет значения ( u , x , x ). Поскольку x — это символ, который встречается чаще всего, мы заменяем его на a , а u , второй по частоте символ, заменяем на b , получая новый первый столбец ( b , a , a ). Второй столбец имеет значения ( v , u , v ). Что касается первого столбца, v заменяется на a , а u заменяется на b , получая новый второй столбец ( a , b , a ). Проделав то же самое со всеми столбцами, мы получим нормализованный экземпляр

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

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

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

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