Ближайшая строка
В теоретической информатике ближайшая строка — это NP-сложная вычислительная задача, [1] который пытается найти геометрический центр набора входных строк.
Чтобы понять слово «центр», необходимо определить расстояние между двумя струнами. Обычно эта проблема изучается с расстояния Хэмминга учетом .
Формальное определение
[ редактировать ]Более формально, учитывая n строк s 1 , s 2 , ..., s n длины m , ближайшая строковая задача ищет новую строку s длины m такую, что d ( s , s i ) ≤ k для всех i , где d — расстояние Хэмминга , где k минимально возможно. [2] Версия проблемы решения проблемы ближайшей строки, которая является NP-полной , вместо этого принимает k в качестве еще одного входного параметра и задается вопросом, существует ли строка на расстоянии Хэмминга k от всех входных строк. [1]
Задачу о ближайшей струне можно рассматривать как частный случай общей задачи с 1 центром , в которой расстояния между элементами измеряются с использованием расстояния Хэмминга.
Мотивация
[ редактировать ]В биоинформатике ближайшей проблемой струн является интенсивно изучаемая грань проблемы поиска сигналов в ДНК .
Упрощения и сокращение данных
[ редактировать ]Экземпляры ближайшей строки могут содержать информацию, не являющуюся существенной для проблемы. В каком-то смысле обычный ввод ближайшей строки содержит информацию, которая не увеличивает сложность задачи. Например, если некоторые строки содержат символ a , но ни одна не содержит символ z , замена всех a на z даст по существу эквивалентный экземпляр, то есть: из решения измененного экземпляра можно восстановить исходное решение, и наоборот.
Нормализация ввода
[ редактировать ]Когда все входные строки одинаковой длины записываются друг на друга, они образуют матрицу. Определенные типы строк имеют по существу одинаковые последствия для решения. Например, замена столбца с записями ( a , a , b ) другим столбцом ( x , x , y ) может привести к другой строке решения, но не может повлиять на разрешимость, поскольку оба столбца выражают одну и ту же структуру, а именно. первые две записи равны, но отличаются от третьей.
Экземпляр ввода можно нормализовать , заменив в каждом столбце наиболее часто встречающийся символ на a , второй по частоте символ на b и т. д. Учитывая решение нормализованного экземпляра, исходный экземпляр можно найти, пересопоставив символы решения в его исходную версию в каждом столбце.
Порядок столбцов не влияет на сложность задачи. Это означает, что если мы переставим все входные строки в соответствии с определенной перестановкой π и получим строку решения s для этого измененного экземпляра, то π −1 ( s ) будет решением исходного экземпляра.
Пример
[ редактировать ]
Дан экземпляр с тремя входными строками uvwx , xuwv и xvwu . Это можно записать в виде матрицы следующим образом:
| в | v | В | х |
| х | в | В | v |
| х | v | В | в |
В первом столбце указаны значения ( 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]
Связь с другими проблемами
[ редактировать ]Ближайшая строка — это частный случай более общей проблемы ближайшей подстроки , которая, строго говоря, более сложна. В то время как ближайшая строка оказывается управляемой с фиксированными параметрами во многих отношениях, ближайшая подстрока является W[1]-трудной по отношению к этим параметрам.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Ланкто, Дж. Кевин; Ли, Мин; Ма, Бин; Ван, Шаоцзю; Чжан, Лусинь (2003), «Выявление проблем выбора строк», Information and Computation , 185 (1): 41–55, doi : 10.1016/S0890-5401(03)00057-9 , MR 1994748
- ^ Бин Ма; Сяминг Сунь (2008). «Более эффективные алгоритмы для решения задач о ближайших строках и подстроках» (PDF) . Исследования в области вычислительной молекулярной биологии . 12-я Энн. Межд. Конф. по исследованиям в области вычислительной молекулярной биологии (RECOMB). ЛНКС . Том. 4955. Спрингер. стр. 396–409. дои : 10.1007/978-3-540-78839-3_33 . ISBN 978-3-540-78838-6 .
- ^ М. Ли; Б. Ма; Л. Ван. (2002), «О задачах о ближайших строках и подстроках». (PDF) , Журнал ACM , 49 (2): 157–171, arXiv : cs/0002012 , doi : 10.1145/506147.506150 , S2CID 965332
- ^ Йенс Грамм; Рольф Нидермайер ; Питер Россманит (2003), «Алгоритмы с фиксированными параметрами для решения ближайших строк и связанных с ними задач», Algorithmica , 37 : 25–42, CiteSeerX 10.1.1.61.736 , doi : 10.1007/s00453-003-1028-3 , S2CID 8206021