Ответ 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, чтобы подчеркнуть, что ваши привязки в основном не повреждены во время выравнивания, используя штрафную модификацию во время выполнение алгоритма.
Надеюсь, это полезно или, по крайней мере, интересно.