ОК, Needleman-Wunsch (NW) - классический комплексный («глобальный») выравниватель из литературы по биоинформатике. Это было давно доступно как "align" и "align0" в пакете FASTA. Разница заключалась в том, что версия «0» не была настолько предвзятой, чтобы избегать пробелов в конце, что часто позволяло предпочтение высококачественных внутренних совпадений. Смит-Уотерман, я подозреваю, что вы знаете, является локальным специалистом и является оригинальной основой BLAST. У FASTA был свой собственный локальный выравниватель, который немного отличался. Все это по существу эвристические методы для оценки расстояния Левенштейна, относящегося к метрике оценки для отдельных пар символов (в биоинформатике, часто предоставляемой Dayhoff / "PAM", Henikoff & Henikoff или другими матрицами и обычно заменяемой чем-то более простым и более разумно отражающим замены в морфологии лингвистического слова применительно к естественному языку).
Давайте не будем ценить метки: расстояние Левенштейна, на которое ссылаются, по крайней мере, на практике, в основном, является расстоянием редактирования, и вы должны его оценить, потому что его вообще невозможно вычислить, и точно вычислить дорого даже в особых особых случаях вода там быстро проникает глубоко, и поэтому у нас есть эвристические методы длинной и хорошей репутации.
Теперь что касается вашей собственной проблемы: несколько лет назад мне пришлось проверять точность коротких чтений ДНК по эталонной последовательности, которая, как известно, была правильной, и я придумал что-то, что я назвал «привязанными привязками».
Идея состоит в том, чтобы взять набор ссылочных строк и «переварить» его, найдя все места, где встречается заданная N-символьная подстрока. Выберите N, чтобы создаваемая таблица была не слишком большой, но и чтобы подстроки длины N были не слишком распространены. Для небольших алфавитов, таких как основы ДНК, можно создать идеальный хэш для строк из N символов, составить таблицу и объединить в цепочке совпадения из каждого списка. Записи списка должны идентифицировать последовательность и начальную позицию подстроки, которая отображается в корзину, в список которой они входят. Это «якоря» в списке искомых строк, для которых может оказаться полезным выравнивание NW.
При обработке строки запроса вы берете N символов, начинающихся со смещения K в строке запроса, хешируете их, ищите их корзину, и если список для этой корзины не пуст, вы просматриваете все записи списка и выполнить выравнивание между строкой запроса и строкой поиска, указанной в записи. При выполнении этих выравниваний вы выстраиваете строку запроса и строку поиска в привязке и извлекаете подстроку строки поиска, которая имеет ту же длину, что и строка запроса, и которая содержит эту привязку с тем же смещением К.
Если вы выберете достаточно большую длину привязки N и разумный набор значений смещения K (они могут быть распределены по строке запроса или ограничены низкими смещениями), вы должны получить подмножество возможных выравниваний и часто получим более четкие победители. Как правило, вы захотите использовать выравнивающий NW выравниватель с меньшим смещением на конце.
Этот метод пытается немного увеличить NW, ограничивая его ввод, и это дает выигрыш в производительности, потому что вы делаете меньше выравниваний, и они чаще между похожими последовательностями. Еще одна хорошая вещь, которую нужно сделать с вашим NW-выравнивателем, - дать ему возможность сдаться после того, как произойдет некоторый или длительный разрыв, чтобы сократить расходы, особенно если вы знаете, что не собираетесь видеть или заинтересованы в матчах среднего качества.
Наконец, этот метод использовался в системе с маленькими алфавитами, где K ограничивался первыми 100 или около того позициями в строке запроса, а строки поиска были намного больше, чем запросы (чтения ДНК составляли около 1000 оснований, а поиск Строки были порядка 10000, поэтому я искал приблизительные совпадения подстрок, специально рассчитанные для оценки расстояния редактирования). Адаптация этой методологии к естественному языку потребует тщательного осмысления: вы теряете размер алфавита, но выигрываете, если строки вашего запроса и строки поиска имеют одинаковую длину.
В любом случае, одновременное использование нескольких якорей с разных концов строки запроса может быть полезным для дальнейшей фильтрации данных, подаваемых в NW. Если вы сделаете это, будьте готовы послать перекрывающие строки, каждая из которых содержит один из двух якорей, в выравниватель, а затем согласовать выравнивания ... или, возможно, дополнительно изменить NW, чтобы подчеркнуть сохранение в основном ваших якорей во время выравнивания, используя модификацию штрафа во время выполнение алгоритма.
Надеюсь, это полезно или хотя бы интересно.