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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы расширить ответ 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/