Приближенные алгоритмы сопоставления строк

Ответ 1

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

Ответ 3

Альтернативные алгоритмы для поиска: agrep (Википедия в agrep), FASTA и BLAST алгоритмы согласования биологической последовательности. Это особые случаи приблизительное соответствие строк, также в репозиторий алгоритма Stony Brook. Если вы можете указать, как строки отличаются друг от друга, вы, вероятно, можете сосредоточиться на индивидуальном алгоритме. Например, Aspell использует некоторый вариант "звукового" (soundex-metaphone) расстояния в сочетании с "клавиатурным" расстоянием для размещения плохих заклинателей и плохих типов.

Ответ 4

Мы используем метод Levenshtein distance для проверки дубликатов клиентов в нашей базе данных. Он работает достаточно хорошо.

Ответ 5

Используйте FM-указатель с Backtracking, похожим на Bowtie fuzzy aligner

Ответ 6

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

Ответ 7

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

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

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

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

Ответ 8

Раньше я работал с некоторыми из самых грязных данных, которые вы когда-либо найдете. В среднем около 5000 строк данных (эквивалентно сотням тысяч долларов), требующих сопоставления, были полностью утомительными. Моим первым опытом с нечетким сопоставлением был алгоритм из Mr Excel, написанный на VBA. У него были определенные проблемы с согласованностью в том, что то, что я ожидал равным 0%, было не совсем 0%, процентное сходство, которое казалось около 60%, выглядело скорее как 90% и т.д. Итак, я перешел в Левенштейн/Дамерау-Левенштейн. Это было серьезное улучшение, но довольно медленное в Excel. Затем я перешел к Джаро-Винклеру, но вскоре после этого быстро бросил его. Наконец, в 2016 году я написал свой собственный (похожий на n-грамм) и усовершенствовал его в течение следующих 2 лет. Сегодня это дополнение под названием Flookup; Вы можете получить его на Google Sheets и посмотреть, как оно работает.