Алгоритмы приблизительного сопоставления строк

Мы используем метод Расстояние Левенштейна для проверки дублирующихся клиентов в нашей базе данных. Работает неплохо.

Связано с расстоянием Левенштейна: вы можете нормализовать его, разделив результат на длину более длинной строки, чтобы вы всегда получали число от 0 до 1 и чтобы вы могли сравнить расстояние пары строк в значимой путь (например, выражение L (A, B)> L (A, C) не имеет смысла, если вы не нормализуете расстояние).

Хорошо, Needleman-Wunsch (NW) - классический сквозной («глобальный») выравниватель из литературы по биоинформатике. Он давно был доступен как "align" и "align0" в пакете FASTA. Разница заключалась в том, что версия с «0» не была так предвзята в отношении предотвращения разрывов, что часто позволяло легче отдавать предпочтение высококачественным внутренним совпадениям. Смит-Ватерман, я подозреваю, что вы знаете, является местным элайнером и лежит в основе BLAST. У FASTA также был собственный локальный элайнер, который немного отличался. Все это, по сути, эвристические методы для оценки расстояния Левенштейна, относящиеся к метрике оценки для отдельных пар символов (в биоинформатике, часто задаваемой Dayhoff / "PAM", Henikoff & Henikoff или другими матрицами и обычно заменяемыми чем-то более простым и более разумно отражающим замены в лингвистической морфологии слова применительно к естественному языку).

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

Теперь что касается вашей собственной проблемы: несколько лет назад мне приходилось проверять точность коротких считываний ДНК относительно контрольной последовательности, которая, как известно, является правильной, и я придумал то, что назвал «привязанное выравнивание».

Идея состоит в том, чтобы взять ваш набор ссылочных строк и «переварить» его, найдя все места, где встречается данная N-символьная подстрока. Выберите N, чтобы создаваемая вами таблица была не слишком большой, но также чтобы подстроки длины N не встречались слишком часто. Для небольших алфавитов, таких как основы ДНК, можно придумать идеальный хеш для строк из N символов, составить таблицу и связать совпадения в связанном списке из каждой ячейки. Записи списка должны идентифицировать последовательность и начальную позицию подстроки, которая сопоставляется с корзиной, в списке которой они встречаются. Это «якоря» в списке строк для поиска, в которых может быть полезно выравнивание NW.

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

Если вы выберете достаточно большую длину привязки N и разумный набор значений смещения K (они могут быть распределены по строке запроса или ограничены низкими смещениями), вы должны получить подмножество возможных выравниваний и часто будут получать более четкие победители. Обычно вы захотите использовать выравниватель NW, похожий на align0, с меньшим смещением по концам.

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

Наконец, этот метод использовался в системе с маленькими алфавитами, с ограничением K до первых 100 или около того позиций в строке запроса и со строками поиска, намного большими, чем запросы (чтения ДНК составляли около 1000 оснований, а строки поиска были на порядка 10000, поэтому я искал приблизительные совпадения подстрок, оправданные оценкой расстояния редактирования, в частности). Адаптация этой методологии к естественному языку потребует некоторой осторожной мысли: вы потеряете размер алфавита, но выиграете, если ваши строки запроса и строки поиска будут иметь одинаковую длину.

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

Надеюсь, это будет полезно или, по крайней мере, интересно.

Альтернативные алгоритмы, на которые стоит обратить внимание: соглашаться (Запись в Википедии на соглашении), Алгоритмы сопоставления биологической последовательности FASTA и BLAST. Это особые случаи приблизительное соответствие строк, также в Репозиторий алгоритма Стоуни Брук. Если вы можете указать, чем строки отличаются друг от друга, вы, вероятно, можете сосредоточиться на индивидуальном алгоритме. Например, aspell использует некоторый вариант «звукового» (soundex-metaphone) расстояния в сочетании с «клавиатурным» расстоянием, чтобы уравновесить как плохое написание, так и плохой наборщик текста.

Используйте Индекс FM с обратным отслеживанием, аналогично тому, что в нечетком выравнивателе Галстук-бабочка

Чтобы свести к минимуму несоответствия из-за небольших вариаций или орфографических ошибок, я использовал алгоритм Metaphone, а затем расстояние Левенштейна (масштабированное до 0–100 в процентах) в кодировках Metaphone для измерения близости. Похоже, это сработало довольно хорошо.

Чтобы расширить ответ Cd-MaN, похоже, вы столкнулись с проблемой нормализации. Не очевидно, как обрабатывать оценки между выравниваниями разной длины.

Учитывая то, что вас интересует, вы можете получить p-значения для вашего выравнивания. Если вы используете Needleman-Wunsch, вы можете получить эти p-значения, используя статистику Карлина-Альтшула http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html

BLAST проведет локальное выравнивание и оценит их, используя эту статистику. Если вас беспокоит скорость, это будет хороший инструмент.

Другой вариант - использовать HMMER. HMMER использует скрытые профили марковские модели для выравнивания последовательностей. Лично я считаю, что это более эффективный подход, поскольку он также предоставляет информацию о местоположении. http://hmmer.janelia.org/